알고리즘 공부 - 트리

안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 트리(tree)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘

트리 (Tree)

트리는 계층 구조를 표현하는 자료구조입니다.

트리에서 사용하는 용어는 다음과 같습니다.

• 노드 (node)
• 링크 (link)
• 루트 (root)
• 부모 (parent)
• 자식 (child)
• 형제 (sibling)
• 리프 (leaf)
• 조상 (ancestor)
• 자손 (descendant)
• 부트리 (subtree)
• 레벨 (level)
• 높이 (height)

이진트리 (Binary Tree)

이진트리는 자식 노드가 최대 2개인 트리를 말합니다. 이진트리의 종류에는 full binary tree 와 complete binary tree가 있습니다.

이진트리는 순회하는 방식에 따라 다음과 같은 종류를 가집니다.

• 중순위(inorder) 순회
• 선순위(preorder) 순회
• 후순위(postorder) 순회
• 레벨오더(level-order) 순회

Dynamic Set

검색트리 를 사용하는 이유는 dynamic set 관리하기 위해서 인데요. 트리의 형태로 구현하는 방식입니다.

즉, 여러 개의 키(key)를 다루어 키를 탐색하거나, 새로운 키를 삽입하거나, 키를 제거하기 위해 사용하는데요.

검색트리 를 구현하기 위해서는 배열이나 링크드 리스트 를 사용할 수 있습니다. 이 경우 Insert, Delete, Search 연산 중 적어도 하나는 O(n)의 속도를 가지는 특성이 있습니다.

이 후 나오는 예시들은 dynamic set 을 Insert, Delete, Search 연산함에 있어서 O(n)보다 효율적으로 사용할 수 있는 지에 대한 고민의 결과들입니다.

일반적으로 검색트리는 Insert, Delete, Search 연산이 트리의 높이(height)에 비례하는 시간복잡도를 가지는 특성이 있습니다.

이진검색트리 (Binary Search Tree)

이진검색트리 는 이진트리이면서 특정 노드에 대해 왼쪽 부트리에 있는 키들은 작거나 같고, 오른쪽 부트리에 있는 키들은 크거나 같은 특징을 가지고 있습니다.

이전에 알고리즘 공부 - sort에서 힙 정렬을 다루면서 heap에 대해 언급한 부분이 있는데요.

Heap 과 이진검색트리는 트리의 구성부터 키의 정렬기준까지 다르므로 같다고 오해하지 않도록 주의할 필요가 있습니다.

이진검색트리에서 최소값은 항상 왼쪽에 존재하고, 최대값은 항상 오른쪽에 존재합니다. 이러한 특성으로 successor와 predecessor를 찾을 수 있습니다. 이러한 특성은 특정 노드를 삭제할 때 유용하게 사용할 수 있습니다.

Insert, Delete, Search 연산 모두 O(h)를 가지고, 최악의 경우에는 O(n)의 시간복잡도를 가집니다.

Red-Black Tree

Red-Black Tree 는 이진검색트리의 일종입니다.

차이점이 있다면 balanced tree 로써 시간복잡도가 항상 O(logn)을 유지할 수 있도록 해준다는 것입니다. (Insert, Delete, Search 연산 모두)

기본 규칙은 이렇습니다.

• 루트 노드의 부모와 모든 리프 노드는 NIL 노드로 간주한다.
• NIL 노드는 black이다.
• 모든 노드는 red 아니면 black 이다.
• 루트 노드는 black 이다.
• red 노드는 경로상 연속할 수 없다.
• 모든 노드의 경로에 대해서 동일한 갯수의 black 노드가 존재한다.

Red-Black Tree를 구현하기 위해서는 부모-자식 노드간 위치를 변경하는 Left Rotation, Right Rotation에 대한 방식을 알아둘 필요가 있습니다.

Insert 연산의 경우 이진검색트리와 같이 노드 삽입 후 아래 6가지 경우에 대해 대응하도록 처리해야 합니다.

case 1. 내 부모 노드가 할아버지 노드의 왼쪽 자식 노드이면서, 부모 노드와 삼촌 노드가 모두 red 이면, 부모와 삼촌 노드를 black 으로 변경하고 할아버지 노드를 red로 변경합니다. (할아버지 노드를 기준으로 red 정합성 확인 반복)

case 2. 내 부모 노드가 할아버지 노드의 왼쪽 자식 노드이면서, 부모 노드는 red이고 삼촌 노드는 black이면서, 내가 부모 노드의 오른쪽 자식이면, 부모 노드 기준으로 left rotation을 수행합니다.

case 3. 내 부모 노드가 할아버지 노드의 왼쪽 자식 노드이면서, 부모 노드는 red이고 삼촌 노드는 black이면서, 내가 부모 노드의 왼쪽 자식이면, 할아버지 노드 기준으로 right rotation을 수행합니다.

case 4. 내 부모 노드가 할아버지 노드의 오른쪽 자식 노드이면서, 부모 노드와 삼촌 노드가 모두 red 이면, 부모와 삼촌 노드를 black 으로 변경하고 할아버지 노드를 red로 변경합니다. (할아버지 노드를 기준으로 red 정합성 확인 반복)

case 5. 내 부모 노드가 할아버지 노드의 오른쪽 자식 노드이면서, 부모 노드는 red이고 삼촌 노드는 black이면서, 내가 부모 노드의 왼쪽 자식이면, 부모 노드 기준으로 right rotation을 수행합니다.

case 6. 내 부모 노드가 할아버지 노드의 오른쪽 자식 노드이면서, 부모 노드는 red이고 삼촌 노드는 black이면서, 내가 부모 노드의 오른쪽 자식이면, 할아버지 노드 기준으로 left rotation을 수행합니다.

Delete 연산의 경우도 이진검색트리와 같이 노드 삭제 후 아래 8가지 경우에 대해 대응하도록 처리해야 합니다.

case 1. 내가 부모 노드의 왼쪽 자식 노드이면서, 형제 노드가 red 이면, 부모 노드를 red로 형제 노드를 black으로 변환 후 부모 노드를 대상으로 left rotation 합니다. (내가 double black 노드이므로 계속)

case 2. 내가 부모 노드의 왼쪽 자식 노드이면서, 형제 노드가 black 이고 형제 노드의 자식 노드들이 black 이면, 부모 노드를 black 으로 형제 노드를 red 로 변환 후 부모 노드를 나로 변경합니다. (내가 double black 노드면 계속)

case 3. 내가 부모 노드의 왼쪽 자식 노드이면서, 형제 노드가 black 이고 형제 노드의 오른쪽 자식 노드만 black 이면, 형제 노드를 red 로 형제 노드의 왼쪽 자식 노드를 black 으로 변환 후 형제 노드를 대상으로 'right-rotation` 합니다. (내가 double black 노드이므로 계속)

case 4. 내가 부모 노드의 왼쪽 자식 노드이면서, 형제 노드가 black 이고 형제 노드의 오른쪽 자식 노드가 red 이면, 형제 노드의 색상을 부모 노드의 색상과 동일하게 변경 후 부모 노드와 형제 노드의 오른쪽 자식 노드 black으로 변경 후 부모 노드를 대상으로 'left-rotation` 합니다. (내가 double black 노드가 아니므로 종료)

case 5. 내가 부모 노드의 오른쪽 자식 노드이면서, 형제 노드가 red 이면, 부모 노드를 red로 형제 노드를 black으로 변환 후 부모 노드를 대상으로 right rotation 합니다. (내가 double black 노드이므로 계속)

case 6. 내가 부모 노드의 오른쪽 자식 노드이면서, 형제 노드가 black 이고 형제 노드의 자식 노드들이 black 이면, 부모 노드를 black 으로 형제 노드를 red 로 변환 후 부모 노드를 나로 변경합니다. (내가 double black 노드면 계속)

case 7. 내가 부모 노드의 오른쪽 자식 노드이면서, 형제 노드가 black 이고 형제 노드의 왼쪽 자식 노드만 black 이면, 형제 노드를 red 로 형제 노드의 오른쪽 자식 노드를 black 으로 변환 후 형제 노드를 대상으로 'left-rotation` 합니다. (내가 double black 노드이므로 계속)

case 8. 내가 부모 노드의 오른쪽 자식 노드이면서, 형제 노드가 black 이고 형제 노드의 왼쪽 자식 노드가 red 이면, 형제 노드의 색상을 부모 노드의 색상과 동일하게 변경 후 부모 노드와 형제 노드의 왼쪽 자식 노드 black으로 변경 후 부모 노드를 대상으로 'right-rotation` 합니다. (내가 double black 노드가 아니므로 종료)

관련 강의

• [알고리즘] 제10강 트리와 이진트리
• [알고리즘] 제11-1강 이진검색트리(Binary Search Tree)
• [알고리즘] 제11-2강 이진검색트리(계속)
• [알고리즘] 제11-3강 이진검색트리
• [알고리즘] 제12-1강 red black tree1
• [알고리즘] 제12-2강 red black tree2
• [알고리즘] 제12-3강 red black tree3

관련 글

• 알고리즘 공부 - sort
• 알고리즘 공부 - recursion
• 알고리즘을 공부해야하는 이유