트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
용어 :
- Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
- Root Node : 트리 맨 위에 있는 노드
- Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
- Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
- Child Node : 어떤 노드의 상위 레벨에 연결된 노드
- Leaf Node : Child Node가 하나도 없는 노드
- Sibling : 동일한 Parent Node를 가진 노드
- Depth : 트리에서 Node가 가질 수 있는 최대 Level
이진 트리와 이진 탐색 트리
- 이진 트리 : 노드의 최대 Branch가 2인 트리
- 이진 탐색 트리 : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
- 왼쪽 노드는 해당 노드보다 작은값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음.
이진 탐색 트리 삭제
- 매우 복잡하다. 경우를 나누어서 이해하는 것이 좋다.
- Leaf Node 삭제
- Leaf Node : Child Node가 없는 Node
- 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.
- Child Node가 하나인 Node 삭제
- 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.
- 삭제할 Node의 자식이 2개인 경우 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다 (아래 방법중 하나를 선택해서 적용한다.)
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 삭제할 Node의 Parent Node가 가리키도록 한다.
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
Ex)
- 삭제할 Node의 오른쪽 자식 선택
- 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
- 해당 Node를 삭제할 Node의 Parent Node의 완쪽 Branch가 가리키게 한다.
- 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 한다.
- 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 한다.
- 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 한다.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeManagement:
def __init__(self, root):
self.root = root
def get_value(self):
return self.root.value
def insert(self, value):
self.current_node = self.root
while True:
if value < self.current_node.value:
if self.current_node.left is not None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right is not None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
def search(self, value):
self.current_node = self.root
while self.current_node:
if self.current_node.value == value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
def delete(self, value):
# 삭제할 노드 탐색
searched = False
self.current_node = self.root
self.parent = self.root
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value:
self.parent = self.current_node
self.current_node = self.current_node.left
else:
self.parent = self.current_node
self.current_node = self.current_node.right
# 삭제할 노드가 없음
if searched is False:
return False
# 삭제할 노드를 찾음
# 1. 삭제할 노드가 리프노드 경우
if self.current_node.left is None and self.current_node.right is None:
if value < self.parent.value:
self.parent.left = None
else:
self.parent.right = None
# 2. 삭제할 노드가 Child Node를 가지고 있을 경우
# 2-1 Child Node가 삭제할 노드의 왼쪽에 있을 경우
elif self.current_node.left is not None and self.current_node.right is None:
if value < self.parent.value:
self.parent.left = self.current_node.left
else:
self.parent.right = self.current_node.left
# 2-2 Child Node가 삭제할 노드의 오른쪽에 있을 경우
elif self.current_node.left is None and self.current_node.right is not None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
# 3. 삭제할 노드가 Child Node를 양쪽 모두 가지고 있을 경우
elif self.current_node.left is not None and self.current_node.right is not None:
# 3-1 삭제할 Node가 Parent Node 왼쪽에 있는 경우
if value < self.parent.value:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
self.change_node_parent.left = None
if self.change_node.right:
self.change_node_parent.right = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.left = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.left
# 3-2 삭제할 Node가 Parent Node 오른쪽에 있는 경우
else:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.current_node.left
return True
if __name__ == "__main__":
bst_nums = set()
while len(bst_nums) != 100:
bst_nums.add(random.randint(0, 999))
print(bst_nums)
head = node_management.Node(500)
binary_tree = node_management.NodeManagement(head)
for number in bst_nums:
binary_tree.insert(number)
# 검색 기능 확인
for number in bst_nums:
if binary_tree.search(number) is False:
print("search failed : ", number)
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
delete_nums.add(bst_nums[random.randint(0, 99)])
# 삭제 기능 확인
for del_num in delete_nums:
if binary_tree.delete(del_num) is False:
print('delete failed', del_num)
이진 탐색 트리의 시간 복잡도와 단점
시간 복잡도 (탐색)
- depth ( 트리의 높이) 를 h라고 표기한다면 O(h)
- 검색을 하기위해 비교 할때마다 절반씩 사라지므로 O(log n)으로 표시할 수 있다.
단점
- 균형이 잡혀이는 트리의 경우 평균 시간 복잡도는 O(log n)이지만 트리가 한쪽으로 편향되어 있으면 O(n)으로 나빠질 수 있다.