파이썬과 함께하는 자료구조 5장 탐색트리 두번째

지난번에 마무리 못했던 탐색트리 뒷 이야기. 

1. AVL 트리

2. 2-3트리, 레드블랙트리

3.B-트리 등

복습

이진탐색트리

- 이진 탐색 개념을 트리 형태에 접목시킨 자료구조.

- 삽입, 삭제 역시 이진 탐색을 바탕으로 진행된다.

(왼쪽, 오른쪽으로 들어가기만 하면 된다)

1. AVL 트리

- 이진탐색트리를 발전 시킨 개념이다.

- 기존의 이진탐색은 값을 나누기만 할뿐 모양에 대한 고려가 없다. 즉 한쪽으로 치우치는 트릭 나올 수 있음

- 그렇기에 AVL 트리는 balence를 통해 트리의 균형을 잡는다.

- 정의 : 임의의 노드 n에 대하여 n의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리.

- 위의 조건 때문에 AVL 트리의 높이는 피보나치 점화식으로 계산 가능.

- 균형을 위해 회전 연산을 한다.

위는 오른쪽으로 균형을 맞추는 코드의 예시

def rotate_right(self, n):

x = n.left

n.left = x.right

x.right = n

n.height = max(self.height(n.left), self.height(n.right)) + 1

x.height = max(self.height(n.left), self.height(x.right)) + 1

return x

위 그림에서는 return x를 표시 안했는데 무조건 return x를 해줘야 루트가 x로 바뀐다.

- left도 마찬가지..

- AVL 트리는 삽입 후 서브트리의 차를 바탕으로 1보다 크면 왼쪽으로 회전을, 1보다 작으면 오른쪽으로 회전을 시켜준다

2. 2-3트리, 레드블랙트리

2.1) 2-3트리

- 차수(자식)이 2인 노드가 2-노드, 차수가 3인 노드가 3-노드 라 부른다

- 모든 이파리가 동일한 층에 있어야 한다.

- 그렇기에 2-3트리는 포화이진트리이다

2.2) 레드블랙트리

- 노드의 색을 부여해서 트리의 균형을 유지한다.

- AVL 트리의 경우 알고리즘을 통해 규형을 유지한다면 레드블랙은 이러한 알고리즘을 색이라는 제약조건을 통해 구현한다.

- 책에 나와있는 것은 좌편향 레드블랙트리(좀더 단순화된 버젼인듯)

- 루트와 None은 블랙

- 루트로부터 각 None 까지 2개의 연속된 레드 link는 없다

- 루트로부터 각 None까지의 경로에 있는 블랙 link 수는 모두 같다

- 레드 link는 왼쪽으로 기울어져있다

- 이러한 조건을 통해 균형을 유지한다.

3. B-트리

- 다방향 탐색이 가능한 완전 균형 트리..

- 다양한 DBMS 시스템의 기본 자료구조로 활용된다고 한다..

- 어렵다...