Tree
트리(Tree)도 루트(Root) 노드에서 시작해서 여러 개의 하위 노드로 이어집니다. 이런 구조는 데이터를 계층적이고 효율적으로 관리할 수 있습니다.
트리 용어 정리
기본 용어
- 노드(Node): 트리를 구성하는 기본 단위. 데이터와 다른 노드를 가리키는 포인터를 포함합니다.
- 루트(Root): 트리의 최상위 노드입니다. 이 노드에서 모든 트리 순회가 시작됩니다.
- 리프(Leaf): 자식 노드가 없는 노드를 의미합니다. Tree가 나무라면 리프 노드는 나뭇잎입니다.
- 레벨(Level): 트리에서 같은 깊이에 있는 노드들의 집합을 나타냅니다. 예를 들어, 루트 노드는 보통 레벨 1(또는 레벨 0)에 있고, 그 자식 노드들은 레벨 2에 있습니다.
- 서브트리(Subtree): 특정 노드와 그 노드의 모든 자손 노드로 구성된 트리입니다. → 재귀적 구조
특정 노드에 대한 정보
- 깊이(Depth): 특정 노드에서 루트 노드까지 도달하기 위한 엣지(간선)의 수입니다.
- 높이(Height): 특정 노드에서 가장 멀리 떨어진 리프 노드까지의 “최장 경로”의 길이를 의미합니다. 다르게 말하면, 주어진 노드로부터 가장 먼 리프 노드까지 도달하기 위해 거쳐야 하는 엣지(간선)의 수입니다.
계층적 구조 에 대한 용어
- 서브트리(Subtree): 특정 노드와 그 노드의 모든 자손 노드로 구성된 트리입니다.
- 부모(Parent) / 자식(Child) / 형제(Sibling)
- 부모 노드는 자식이 없을 수도 있고 많을 수도 있습니다. 루트 노드를 제외한 노드는 반드시 1명의 부모를 갖습니다.
- 자식은 부모 노드에 연결된 하위 노드를 말합니다.
- 형제는 같은 부모를 가지는 노드들입니다.
중요한 Tree 종류
이진 트리 (Binary Tree)
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 트리에는 여러 하위 유형이 있습니다.
- 완전 이진 트리 (Full Binary Tree): 모든 레벨이 완전히 채워져 있습니다.
- 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드들은 왼쪽부터 채워져 있습니다.
- 균형 이진 트리 (Balanced Binary Tree): 모든 리프 노드까지의 거리가 거의 동일합니다.
이진 검색 트리 (Binary Search Tree, BST)
이진 검색 트리는 이진 트리의 한 유형으로, 왼쪽 하위 트리의 모든 노드가 부모 노드보다 작고, 오른쪽 하위 트리의 모든 노드가 부모 노드보다 큽니다.
- Balanced BST
- AVL Tree (Balanced BST): 이진 검색 트리를 기반으로 하며, 균형이 유지되도록 설계되어 있습니다.
- Red-Black Tree (Balanced BST): 이진 검색 트리를 기반으로 하며, 노드에 색상을 부여해 균형을 유지합니다.
이진 검색 트리 구현
# 트리 노드 클래스 정의
class TreeNode:
def __init__(self, data):
self.data = data # 현재 노드의 데이터
self.children = [] # 자식 노드들을 저장하기 위한 리스트
def add_child(self, child_node):
self.children.append(child_node)
# 이진 트리 노드 클래스 정의
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.left = None # 왼쪽 자식 노드
self.right = None # 오른쪽 자식 노드
# 이진 검색 트리 클래스 정의
class BinarySearchTree:
def __init__(self):
self.root = None # 루트 노드
# 이진 검색 트리에 데이터 삽입
def insert(self, data):
new_node = BinaryTreeNode(data)
if self.root is None:
self.root = new_node
else:
self._insert_recursive(self.root, new_node)
# 재귀적으로 데이터 삽입 수행
def _insert_recursive(self, current_node, new_node):
if new_node.data < current_node.data:
if current_node.left is None:
current_node.left = new_node
else:
self._insert_recursive(current_node.left, new_node)
else:
if current_node.right is None:
current_node.right = new_node
else:
self._insert_recursive(current_node.right, new_node)
# 이진 검색 트리에서 데이터 검색
def search(self, data):
return self._search_recursive(self.root, data)
# 재귀적으로 데이터 검색 수행
def _search_recursive(self, current_node, data):
if current_node is None:
return False
if data == current_node.data:
return True
elif data < current_node.data:
return self._search_recursive(current_node.left, data)
else:
return self._search_recursive(current_node.right, data)
# 이진 검색 트리 생성과 사용 예제
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)
print(bst.search(10)) # True
print(bst.search(8)) # False다진 검색 트리
B-Tree와 B+ Tree는 데이터베이스와 파일 시스템에서 주로 사용됩니다. 노드가 여러 개의 자식을 가질 수 있어 디스크 접근을 최소화하는 데 유용합니다.
Tree 사용 사례
- 트리는 조부모 > 부모 > 자식 관계와 같이 계층적 구조를 갖는 자료구조입니다. 이 말은 실생활에서 계층적 데이터를 표현해야되는 경우에 Tree 자료구조를 활용할 수 있다는 의미입니다.
- 계층 구조가 필요한 상황
- HTML, XML 등 문서 개체 모델 (DOM)
- 추상 구문 트리(Abstract Syntax Tree, AST) - 프로그래밍 언어 컴파일러 및 파서
- 데이터베이스 인덱스
- 조직도와 조직의 계층 구조
- 파일 시스템
- 게임 개발에서의 스테이지 및 레벨 관리
- 검색 및 삽입, 삭제 작업이 빈번한 경우에는 효율적인 탐색 및 관리를 위해 이진 검색 트리(BST)를 사용할 수 있습니다.
Tree 순회
트리 순회(Tree Traversal)는 트리의 모든 노드를 방문하는 방법을 말합니다. 주요한 트리 순회 방법은 다음과 같습니다.
전위 순회 (Preorder Traversal)
현재 노드를 먼저 방문한 후, 왼쪽 서브트리를 전위 순회하고, 오른쪽 서브트리를 전위 순회합니다.
중위 순회 (Inorder Traversal)
왼쪽 서브트리를 중위 순회한 후, 현재 노드를 방문하고, 오른쪽 서브트리를 중위 순회합니다. 이 때, 이진 검색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있습니다.
후위 순회 (Postorder Traversal)
왼쪽 서브트리를 후위 순회한 후, 오른쪽 서브트리를 후위 순회하고, 마지막으로 현재 노드를 방문합니다.
Balanced BST - BST 문제점 보완
이진 검색 트리(Binary Search Tree, BST)
자료의 검색, 삽입, 삭제와 같은 기본적인 연산을 효율적으로 수행하는 데 있어 중요한 자료구조입니다.
특히 평균적으로 이러한 연산의 시간 복잡도가 으로 매우 빠르다는 것이 큰 장점입니다. 그러나 이는 "평균적으로"라는 단어에 주목해야 합니다.
이진 검색 트리가 항상 이러한 효율성을 보장하는 것은 아닙니다. 트리의 형태가 불균형하게 될 경우, 이는 사실상 링크드 리스트와 다름없이 연산의 시간 복잡도가 에 이를 수 있습니다.
이러한 문제점은 특별한 경우에 발생할 수 있으나, 발생한다면 그 비효율성은 무시할 수 없습니다.
균형 이진 검색 트리(Balanced Binary Search Tree)
이러한 문제를 해결하기 위해 고안된 것이 바로 "균형 이진 검색 트리(Balanced Binary Search Tree)"입니다. 이는 여러 알고리즘과 메커니즘을 활용하여 트리의 균형을 자동으로 조정합니다.
AVL 트리, 레드-블랙 트리 등이 이에 속합니다. 이러한 균형 이진 검색 트리는 연산의 시간 복잡도를 최악의 경우에도 으로 유지하는 것을 보장합니다.
데이터의 양이 증가하면 증가할수록, 불균형이 발생할 확률도 늘어납니다. 이를 예방하고 안정적인 성능을 유지하기 위해 균형 이진 검색 트리는 필수적입니다. 데이터베이스에서 사용하는 B-tree도 균형 트리의 일종입니다.
AVL 트리, 레드-블랙 트리에서 어떻게 균형을 유지하는지 알고 있으면 도움이 많이 됩니다.
AVL Tree
- AVL 트리는 이진 검색 트리(Binary Search Tree, BST)를 개선한 균형 이진 검색 트리입니다.
- 이 구조는 1962년에 Adelson-Velsky와 Landis에 의해 처음 발표되었으며, AVL 트리의 이름도 이들의 이니셜에서 유래했습니다.
- AVL 트리는 이러한 문제를 해결하기 위해 “균형 조건”을 도입한 이진 검색 트리(BST)입니다. 균형 조건을 만족하기 위해 트리가 변경될 때마다 회전 연산을 수행합니다.
- 여기서 균형 조건은 “AVL 트리에서는 모든 노드에 대해 그 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 최대 1이 되도록 유지” 하는 것을 의미합니다.
AVL 트리 균형 유지
AVL 트리는 삽입이나 삭제 연산이 이루어진 직후에 트리의 균형을 유지하기 위한 특별한 “회전 연산”을 수행합니다. 이를 통해 모든 노드에 대해 왼쪽과 오른쪽 하위 트리의 높이 차이가 최대 1이 되도록 합니다.
AVL 트리인 상태에서 삽입이나 삭제 직후에 균형이 깨질 때 전혀 관계없는 두 곳 이상에서 균형이 깨지는 경우는 없습니다. 어떤 서브 트리에서 균형이 깨졌다면, 그 서브 트리를 포함하는 위쪽 서브 트리도 균형이 깨질 수 있습니다.
여러 서브 트리에서 균형이 깨진 경우, 균형이 깨진 서브 트리 중 가장 낮은 곳에 있는 트리부터 균형을 잡아주는 작업을 하면서 올라갑니다.
-
삽입 후 균형 맞추기
- 새 노드를 삽입합니다.
- 삽입한 노드로부터 루트 노드까지 역방향으로 경로를 따라가며 각 노드의 균형 팩터를 확인합니다.
- 균형 팩터가 2 또는 -2인 노드를 발견하면 해당 노드를 기준으로 회전 연산을 수행하여 균형을 맞춥니다. 그 후에는 다시 위로 올라가며 균형 팩터를 확인하며 루트 노드까지 올라갑니다. 이 과정을 반복하면서 모든 노드의 균형을 맞춥니다.
-
삭제 후 균형 맞추기
- 삭제된 노드로부터 루트 노드까지 역방향으로 경로를 따라가며 각 노드의 균형 팩터를 확인합니다.
- 균형 팩터가 2 또는 -2인 노드를 발견하면 해당 노드를 기준으로 회전 연산을 수행하여 균형을 맞춥니다. 그 후에는 다시 위로 올라가며 균형 팩터를 확인하며 루트 노드까지 올라갑니다. 이 과정을 반복하면서 모든 노드의 균형을 맞춥니다.
- 만약 균형 팩터가 2 또는 -2인 노드가 여러 개인 경우, 가장 낮은 노드부터 회전 연산을 수행합니다.
AVL 트리에서의 삽입과 삭제 연산은 기본적으로 시간에 수행됩니다. 이는 높이 균형을 유지하기 위해 회전 연산을 수행하는 데에 드는 시간이 이기 때문입니다. 따라서 AVL 트리는 최악의 경우에도 삽입, 삭제, 검색 연산이 모두 에 수행될 수 있는 자료구조입니다.
구현 코드
class Node:
def __init__(self, key):
self.key = key
self.height = 1
self.left = None
self.right = None
def getHeight(node):
if not node:
return 0
return node.height
def updateHeight(node):
if node:
node.height = 1 + max(getHeight(node.left), getHeight(node.right))
def getBalance(node):
if not node:
return 0
return getHeight(node.left) - getHeight(node.right)
# 단일 오른쪽 회전
def rotateRight(y):
x = y.left
T = x.right
x.right = y
y.left = T
updateHeight(y)
updateHeight(x)
return x
# 단일 왼쪽 회전
def rotateLeft(x):
y = x.right
T = y.left
y.left = x
x.right = T
updateHeight(x)
updateHeight(y)
return y
# 노드를 삽입하고 균형을 맞춘다
def insert(root, key):
if not root:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
else:
return root # 중복 노드는 허용하지 않는다
updateHeight(root)
balance = getBalance(root)
# 균형이 깨진 경우 회전을 수행
# Left Heavy
if balance > 1:
if key < root.left.key:
return rotateRight(root) # 단일 오른쪽 회전
else:
root.left = rotateLeft(root.left) # 왼쪽 하위 트리를 왼쪽으로 회전
return rotateRight(root) # 단일 오른쪽 회전
# Right Heavy
if balance < -1:
if key > root.right.key:
return rotateLeft(root) # 단일 왼쪽 회전
else:
root.right = rotateRight(root.right) # 오른쪽 하위 트리를 오른쪽으로 회전
return rotateLeft(root) # 단일 왼쪽 회전
return root
# 트리를 순회하며 출력한다 (In-order Traversal)
def inOrder(root):
if not root:
return
inOrder(root.left)
print(root.key, end=' ')
inOrder(root.right)
def printTree(root, level=0, indent="----"):
if root is not None:
printTree(root.right, level + 1, " ")
print(indent * level + "-> " + str(root.key))
printTree(root.left, level + 1, " ")
# 예제 사용
root = None
keys = [30, 40, 50, 10, 20, 22, 24, 26, 14, 16, 18]
# 출력을 통해 균형이 잘 유지되고 있는지 확인한다
for key in keys:
root = insert(root, key)
print("After inserting {}: ".format(key))
printTree(root)
print("\n---")
출력 결과
After inserting 30:
-> 30
---
After inserting 40:
-> 40
-> 30
---
After inserting 50:
-> 50
-> 40
-> 30
---
After inserting 10:
-> 50
-> 40
-> 30
-> 10
---
After inserting 20:
-> 50
-> 40
-> 30
-> 20
-> 10
---
After inserting 22:
-> 50
-> 40
-> 30
-> 22
-> 20
-> 10
---
After inserting 24:
-> 50
-> 40
-> 30
-> 24
-> 22
-> 20
-> 10
---
After inserting 26:
-> 50
-> 40
-> 30
-> 26
-> 24
-> 22
-> 20
-> 10
---
After inserting 14:
-> 50
-> 40
-> 30
-> 26
-> 24
-> 22
-> 20
-> 14
-> 10
---
After inserting 16:
-> 50
-> 40
-> 30
-> 26
-> 24
-> 22
-> 20
-> 16
-> 14
-> 10
---
After inserting 18:
-> 50
-> 40
-> 30
-> 26
-> 24
-> 22
-> 20
-> 18
-> 16
-> 14
-> 10
---AVL 트리의 한계
AVL 트리는 높이 균형을 유지하기 위해 회전 연산을 수행하므로 삽입과 삭제 연산의 시간 복잡도는 입니다. 하지만 이러한 높이 균형을 유지하기 위한 추가적인 연산은 상대적으로 느립니다. 따라서 AVL 트리는 삽입과 삭제 연산이 빈번하게 일어나는 상황에서는 성능이 떨어질 수 있습니다.
또한, AVL 트리의 균형을 맞추기 위한 회전 연산은 비교적 복잡한 연산이므로 상수 시간 내에 수행하기 어렵습니다. 따라서 AVL 트리의 상수항이 더 크기 때문에 실제로는 효율적인 자료구조로 사용되기 어려울 수 있습니다.
또한 AVL 트리의 높이는 데이터의 삽입 순서에 따라 달라질 수 있습니다. 특정한 데이터를 삽입하는 순서에 따라 트리의 높이가 증가하면 검색 연산의 성능이 떨어질 수 있습니다. 이러한 경우를 방지하려면 데이터를 삽입하는 순서를 무작위화하거나, 다른 균형 이진 검색 트리 구조를 사용하는 것이 고려될 수 있습니다.
AVL 트리의 사용 예
AVL 트리는 높이 균형을 유지하는 데에 강점을 가지고 있으므로 검색 연산의 수행 시간이 중요한 상황에서 사용됩니다. 주로 데이터베이스 시스템이나 파일 시스템 등에서 활용됩니다.
데이터베이스 시스템에서는 데이터의 빠른 검색과 삽입, 삭제 연산이 중요하므로 AVL 트리와 같은 균형 이진 검색 트리가 사용됩니다. 또한, 파일 시스템에서는 파일의 이름을 효율적으로 검색하기 위해 AVL 트리를 활용할 수 있습니다.
이 외에도 AVL 트리는 데이터베이스 인덱스 구조, 자동 완성 기능을 제공하는 검색 엔진, 심볼 테이블 등 다양한 분야에서 사용될 수 있습니다.
레드-블랙 트리
- 레드-블랙 트리(Red-Black Tree)는 균형 이진 검색 트리의 일종으로, AVL 트리와 마찬가지로 트리의 균형을 유지하기 위한 자료구조입니다.
- 레드-블랙 트리는 삽입, 삭제 연산 시 AVL 트리보다 상대적으로 회전 연산이 적게 필요하므로 실제로는 삽입과 삭제 연산이 더 빠르게 수행될 수 있습니다.
- 이러한 특성으로 인해 레드-블랙 트리는 실용적인 균형 이진 검색 트리로 널리 사용되고 있습니다.
- 레드-블랙 트리는 이름에서 알 수 있듯이 각 노드에 레드(RED) 또는 블랙(BLACK) 색상을 부여하며, 특정한 규칙을 따라 색상을 조절하여 균형을 유지합니다.
6-2. 레드-블랙 트리의 특성
레드-블랙 트리는 다음과 같은 특성을 가집니다:
- 각 노드는 레드 또는 블랙 색상 중 하나를 가집니다.
- 루트 노드는 블랙이어야 합니다.
- 모든 리프 노드(즉, NIL 노드 또는 외부 노드)는 블랙이어야 합니다.
- 연속된 레드 노드가 나타나서는 안 됩니다. (레드-레드 연결 금지)
- 어떤 노드로부터 리프 노드까지의 모든 경로에는 블랙 노드의 개수가 동일해야 합니다. (블랙 높이 균형)
레드-블랙 트리는 이러한 특성을 유지하면서 삽입, 삭제 연산을 수행하며 균형을 유지합니다. 각각의 연산에서 레드-블랙 트리의 특성을 위반하지 않도록 색상을 조절하고, 회전 연산을 통해 균형을 맞춥니다. 이로써 모든 연산의 시간 복잡도는 이 보장됩니다.
6-3. AVL 트리 vs. 레드-블랙 트리
AVL 트리와 레드-블랙 트리는 모두 균형 이진 검색 트리의 일종이지만, 다음과 같은 차이점이 있습니다:
- 회전 연산의 빈도: AVL 트리는 높이 균형을 더 엄격하게 유지하기 위해 회전 연산을 더 자주 수행합니다. 반면 레드-블랙 트리는 균형을 덜 엄격하게 유지하므로 회전 연산의 빈도가 적습니다.
- 삽입 및 삭제 연산의 성능: 레드-블랙 트리는 회전 연산이 덜 필요하므로 삽입 및 삭제 연산이 더 빠를 수 있습니다. AVL 트리의 삽입 및 삭제 연산은 더 복잡할 수 있습니다.
- 트리의 높이: AVL 트리는 높이를 더 엄격하게 제한하기 때문에 트리의 높이가 더 낮을 수 있습니다. 레드-블랙 트리는 높이 균형을 덜 엄격하게 유지하기 때문에 높이가 더 높을 수 있습니다.
따라서 데이터의 삽입 및 삭제 연산이 빈번하게 일어나는 상황에서는 레드-블랙 트리가 AVL 트리보다 성능이 우수하다고 볼 수 있습니다. 그러나 검색 연산의 경우 두 트리의 성능은 비슷합니다.
6-4. 레드-블랙 트리의 사용 예
레드-블랙 트리는 데이터베이스, 파일 시스템, 네트워크 라우팅 등 다양한 분야에서 사용됩니다. 몇 가지 예시로는:
- 데이터베이스 인덱스 구조: 데이터베이스 시스템에서 데이터를 검색하는 데 사용됩니다.
- C++ STL의
std::map및std::set: C++ 표준 라이브러리에서 레드-블랙 트리가 기반으로 사용됩니다. - 리눅스 커널에서의 프로세스 스케줄링: 리눅스 커널은 레드-블랙 트리를 사용하여 프로세스 관리를 수행합니다.
레드-블랙 트리의 균형을 유지하는 능력과 삽입, 삭제 연산의 효율성으로 인해 다양한 응용 분야에서 사용되며, 효율적인 데이터 구조로 폭넓게 활용됩니다.
구현 코드
class Node:
# Node 생성자
def __init__(self, data, color, parent=None):
self.data = data # 노드의 값
self.color = color # 노드의 색상 (RED 또는 BLACK)
self.parent = parent # 부모 노드
self.left = None # 왼쪽 자식
self.right = None # 오른쪽 자식
class RedBlackTree:
# RedBlackTree 생성자
def __init__(self):
self.TNULL = Node(0, "BLACK") # NULL을 대체하는 블랙 노드
self.root = self.TNULL # 루트 초기화
# 전위 순회 함수
def pre_order_helper(self, node):
if node != self.TNULL:
print(node.data, end=" ")
self.pre_order_helper(node.left)
self.pre_order_helper(node.right)
# 노드 삽입 후 균형을 유지하는 함수
def balance_insert(self, k):
# 부모가 RED이면 균형을 맞춤
while k.parent.color == "RED":
# 부모가 할아버지의 오른쪽 자식일 때
if k.parent == k.parent.parent.right:
u = k.parent.parent.left # Uncle 노드
# Case 1: Uncle이 RED
if u.color == "RED":
u.color = "BLACK"
k.parent.color = "BLACK"
k.parent.parent.color = "RED"
k = k.parent.parent
else: # Case 2 or Case 3
# Case 2: 현재 노드가 왼쪽 자식일 때
if k == k.parent.left:
k = k.parent
self.rotate_right(k)
# Case 3
k.parent.color = "BLACK"
k.parent.parent.color = "RED"
self.rotate_left(k.parent.parent)
else: # 부모가 할아버지의 왼쪽 자식일 때
u = k.parent.parent.right # Uncle 노드
# Case 1: Uncle이 RED
if u.color == "RED":
u.color = "BLACK"
k.parent.color = "BLACK"
k.parent.parent.color = "RED"
k = k.parent.parent
else: # Case 2 or Case 3
# Case 2: 현재 노드가 오른쪽 자식일 때
if k == k.parent.right:
k = k.parent
self.rotate_left(k)
# Case 3
k.parent.color = "BLACK"
k.parent.parent.color = "RED"
self.rotate_right(k.parent.parent)
# 루트 노드까지 올라갔으면 종료
if k == self.root:
break
# 루트는 항상 BLACK
self.root.color = "BLACK"
# 삽입 함수
def insert(self, key):
# 새로운 노드 초기화
node = Node(key, "RED")
node.parent = None
node.data = key
node.left = self.TNULL
node.right = self.TNULL
node.color = "RED"
y = None
x = self.root
# 삽입 위치를 찾음
while x != self.TNULL:
y = x
if node.data < x.data:
x = x.left
else:
x = x.right
# 부모 노드 설정
node.parent = y
if y == None:
self.root = node
elif node.data < y.data:
y.left = node
else:
y.right = node
# 루트 노드면 BLACK으로 설정
if node.parent == None:
node.color = "BLACK"
return
# 할아버지 노드가 없으면 종료
if node.parent.parent == None:
return
# 균형을 맞춤
self.balance_insert(node)
# 왼쪽 회전 함수
def rotate_left(self, x):
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
# 오른쪽 회전 함수
def rotate_right(self, x):
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
# 트리 출력 함수
def print_tree(self, node, level=0, indent="----"):
if node != self.TNULL:
self.print_tree(node.right, level + 1, " ")
print(indent * level + "-> " + str(node.data) + "(" + node.color + ")")
self.print_tree(node.left, level + 1, " ")
# 테스트 코드
tree = RedBlackTree()
numbers = [30, 40, 50, 10, 20, 22, 24, 26, 14, 16, 18]
for num in numbers:
tree.insert(num)
print(f"After inserting {num}: ")
tree.print_tree(tree.root)
print("---")테스트 결과
After inserting 30:
-> 30(BLACK)
---
After inserting 40:
-> 40(RED)
-> 30(BLACK)
---
After inserting 50:
-> 50(RED)
-> 40(BLACK)
-> 30(RED)
---
After inserting 10:
-> 50(BLACK)
-> 40(BLACK)
-> 30(BLACK)
-> 10(RED)
---
After inserting 20:
-> 50(BLACK)
-> 40(BLACK)
-> 30(RED)
-> 20(BLACK)
-> 10(RED)
---
After inserting 22:
-> 50(BLACK)
-> 40(BLACK)
-> 30(BLACK)
-> 22(RED)
-> 20(RED)
-> 10(BLACK)
---
After inserting 24:
-> 50(BLACK)
-> 40(BLACK)
-> 30(RED)
-> 24(BLACK)
-> 22(RED)
-> 20(RED)
-> 10(BLACK)
---
After inserting 26:
-> 50(BLACK)
-> 40(RED)
-> 30(BLACK)
-> 26(RED)
-> 24(BLACK)
-> 22(BLACK)
-> 20(RED)
-> 10(BLACK)
---
After inserting 14:
-> 50(BLACK)
-> 40(RED)
-> 30(BLACK)
-> 26(RED)
-> 24(BLACK)
-> 22(BLACK)
-> 20(RED)
-> 14(RED)
-> 10(BLACK)
---
After inserting 16:
-> 50(BLACK)
-> 40(RED)
-> 30(BLACK)
-> 26(RED)
-> 24(BLACK)
-> 22(BLACK)
-> 20(RED)
-> 16(RED)
-> 14(BLACK)
-> 10(RED)
---
After inserting 18:
-> 50(BLACK)
-> 40(BLACK)
-> 30(BLACK)
-> 26(RED)
-> 24(BLACK)
-> 22(BLACK)
-> 20(BLACK)
-> 18(RED)
-> 16(BLACK)
-> 14(RED)
-> 10(BLACK)
---