Developer_Neo
[자료구조] 트리 (Tree) 구조 -Data Structure with 파이썬 본문
트리 (Tree) 구조
Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
즉 노드로 이루어진 자료 구조이다.
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
- 노드(node)들과 노드들을 연결하는 간선(edge, Branch)들로 구성되어 있다.
- 트리에는 사이클(cycle)이 존재할 수 없다.
- 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
- 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
- 각 노드는 어떤 자료형으로도 표현 가능함
어디에 많이 사용되나?
트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용
용어
- Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
- Root Node: 트리 맨 위에 있는 노드
- Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
- Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
- Child Node: 어떤 노드의 상위 레벨에 연결된 노드
- Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
- Sibling (Brother Node): 동일한 Parent Node를 가진 노드
- Depth: 트리에서 Node가 가질 수 있는 최대 Level
레벨에 있어서 루트노드를 레벨 1로 두는게 보통이다 그래서 깊이와는 1차이가 나게 된다.
예를 들어 깊이가 2이라면 레벨은 3까지라는 것이다.
레벨(level) : 루트 노드들로부터 깊이(루트 노드의 레벨 = 1)
트리의 깊이(depth of tree) : 트리에 속한 노드의 최대 레벨
이진 트리와 이진 탐색 트리 (Binary Search Tree)
- 이진 트리
- 노드의 최대 Branch가 2(자식노드가 최대 2개)인 트리
- 이진 탐색 트리 (Binary Search Tree, BST)
- 이진 트리에 다음과 같은 추가적인 조건이 있는 트리 (자식노드가 최대 2개 + 추가적인 조건)
- 왼쪽 노드는 루트 노드보다 작은 값, 오른쪽 노드는 루트 노드보다 큰 값을 가지고 있음
- 이진 트리에 다음과 같은 추가적인 조건이 있는 트리 (자식노드가 최대 2개 + 추가적인 조건)
이진 탐색 트리의 장점과 주요 용도
- 주요 용도: 데이터 검색(탐색)
- 장점: 탐색 속도를 개선할 수 있음
이진 탐색 트리 구현 코드 (파이썬)
class Node:
def __init__(self,value):
self.left=None
self.value=value
self.right=None
class HeadNode:
def __init__(self,data):
self.head=Node(data)
def add(self,value):
node = self.head
new_node = Node(value)
while True:
if node.value < value:
if node.right==None:
node.right=new_node
break
else:
node=node.right
else:
if node.left == None:
node.left = new_node
break
else:
node = node.left
def search(self,value):
node=self.head
while True:
if node.value==value:
return True
elif node.value<value:
node=node.right
else:
node=node.left
return False
def delete(self,value):
#삭제할 노드 탐색
searched=False
self.current_node=self.head
self.parent_node=self.head
while self.current_node:
if self.current_node.value==value:
searched=True
break
elif self.current_node.value>value:
self.parent_node=self.current_node
self.current_node=self.current_node.left
else:
self.parent_node = self.current_node
self.current_node = self.current_node.right
if searched==False:
return False
#Case1: 삭제할 Node가 Leaf Node인 경우
if self.current_node.left==None and self.current_node.left==None:
if value<self.parent_node.value:
self.parent_node.left=None
else:
self.parent_node.right = None
del self.current_node
#Case2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
if self.current_node.left==None and self.current_node.right!=None:
if value<self.parent_node.value:
self.parent_node.left=self.current_node.right
else:
self.parent_node.right=self.current_node.right
elif self.current_node.left!=None and self.current_node.right==None:
if value<self.parent_node.value:
self.parent_node.left=self.current_node.left
else:
self.parent_node.right=self.current_node.left
# Case3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)
if self.current_node.left != None and self.current_node.right != None:
if value<self.parent_node.value:
self.change_node=self.current_node.right
self.change_node_parent=self.current_node.right
while self.change_node.left!=None:
self.change_node_parent=self.change_node
self.change_node=self.change_node.left
if self.change_node.right!=None:
self.change_node_parent.left=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.current_node.left
else: #Case3-2: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
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.left = self.current_node.left
self.change_node.right = self.current_node.right루트누드의 오른쪽은 루트누드의 데이터값보다 크고 루트누드의 왼쪽은 루트누드의 데이터값보다 작다는 것이 재귀적으로 자식노드에게 적용되니 이 특성(이진트리의 조건)을 고려해서 삭제를 할때에 구현해야한다.
delete함수구현
1. 삭제할 노드를 탐색
- 없는 경우 False를 반환하면서 종료
- 부모노드에 해당하는 것을 가지고 있어야한다.(부모노드를 찾아놓은 노드 전 것으로 설정해둔다.)
2. 3개의 경우로 나뉘어진다.
위에서 이미 삭제할 노드는 찾아놓은 것이다.
- 삭제할 노드가 Leaf Node인경우
- 삭제할 노드의 Child Node가 하나인 경우
- 삭제할 노드의 Child Node가 2개인 경우
삭제할 노드가 Leaf Node(마지막 노드)인경우
1. child node에 해당하는 것이 없으니 부모노드의 오른쪽, 왼쪽 둘 중 하나가 child node일텐데 이때 그 child node가 속한 곳에 None을 넣어주면 된다.
삭제할 노드의 Child Node가 하나인 경우
1. child node가 왼쪽 오른쪽 가지고 있는 2가지 경우가 있다. 그래서 2가지경우로 나누어서 해야한다.
왜냐하면 child node를 2개 다 가지고 있는 경우와 구별해야하기 때문이다.
2. child node가 왼쪽, 오른쪽인 경우
2-1. 삭제할 노드가 부모노드의 왼쪽인지 오른쪽인지 판단
2-2. 판단 후에 그쪽에 child node를 할당해준다.
삭제할 노드의 Child Node가 2개인 경우
1. 삭제할 노드와 부모 노드를 다른 변수인 change_node와 change_node_parent 노드에 할당해둔다.
2. 삭제할 노드가 부모노드의 오른쪽인 경우
2-1. 삭제할 노드를 대체할 노드를 찾아야한다.
2-1-1. 찾는 노드는 삭제할 노드의 자식노드들을 거친 가장 왼쪽노드이다.
why? 이진트리는 루트노드의 값과 비교하여 자식노드가 할당된다.
이때 삭제할 노드의 right로써 거친 가장 오른쪽 노드가 대체할 노드라면 이진트리의 조건이 맞지 않게 된다.
또, 삭제할 노드의 left로 가고 그다음 right로 갈 경우 이것은 가능하다 하지만 삭제할 노드와 가 장 비슷한 값을 찾아서 올리는것이 나중에 탐색을 진행할때에 이득이 있기 때문에 이것으로 하지 않는다. (이때 또 left가 아닌 right로 가도 가까운 것이 있을 수 있는데 여러가지 중 채택한 한 방 법이라고 생각하면 될 것같다)
3. 삭제할 노드가 부모노드의 왼쪽인 경우
2-1. 삭제할 노드를 대체할 노드를 찾아야한다.
2-1-1. 찾는 노드는 삭제할 노드의 left 자식노드.right거친 가장 오른쪽노드이다.
+extra
시간 복잡도 (탐색시)
- depth (트리의 높이) 를 h라고 표기한다면, O(h)
- n개의 노드를 가진다면, h=log2n 에 가까우므로, 시간 복잡도는 O(logn)
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미
(빅오 표기법에서 logn 에서의 log의 밑은 2입니다)
이진 탐색 트리 단점
- 평균 시간 복잡도는 O(logn)(->이는 트리가 균형잡혀 있을 때의 평균 시간복잡도) 이지만
- 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 ( O(n) )
이진 탐색 트리의 단점의 예
'자료구조' 카테고리의 다른 글
| [자료구조] 그래프 (Graph) 구조 -Data Structure with 파이썬 (0) | 2022.02.16 |
|---|---|
| [자료구조] 힙 (Heap) 구조 -Data Structure with 파이썬 (0) | 2022.01.28 |
| [자료구조] 해쉬 테이블(Hash Table) -Data Structure with 파이썬 (0) | 2022.01.25 |
| [자료구조] 링크드(연결) 리스트(Linked List) -Data Structure with 파이썬 (0) | 2022.01.21 |
| [자료구조] 스택(Stack) -Data Structure with 파이썬 (0) | 2022.01.21 |
