트리 (tree)
정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조
비선형구조이며 트리의 목적은 주로 탐색이다.
트리에서는 사이클이 존재할수 없다.
트리의 노드 유형
- 루트 노드 (root node) : 제일 최고 부모 노드. 트리는 하나의 루트노드만을 가진다.
- 리프 노드,단말 노드(leaf node) : 자식이없는 노드입니다.
- 내부 노드(internal) : 단말 노드가 아닌 노드
트리를 표현하는 용어
- 노드의 크기 (size) : 자신을 포함한 모든 자손 노드의 개수
- 노드의 깊이 (depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야하는 간선의 수
- 노드의 레벨 (level) : 트리의 특정 깊이를 가지는 노드의 집합
- 노드의 차수 (degree) : 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
- 트리의 차수 (degree of tree) : 트리의 최대 차수
- 트리의 높이 (height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이
이진 트리(Binary Tree)
각 노드가 최대 두개의 자식을 가지는 트리
이진 트리 구현 (python)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __str__(self):
return str(self.data)
class Tree:
def __init__(self):
self.root = None이진트리 깊이와 노드 수를 구하는 코드 구현
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __str__(self):
return str(self.data)
def size(self):
l = self.left.size() if self.left else 0
r = self.right.size() if self.right else 0
return l + r + 1
def depth(self):
leftDepth = self.left.depth() if self.left else 0
rightDepth = self.right.depth() if self.right else 0
return leftDepth + 1 if leftDepth > rightDepth else rightDepth + 1
class Tree:
def __init__(self):
self.root = None
def size(self):
if self.root: return self.root.size()
else: return 0
def depth(self):
if self.root: return self.root.depth()
else: return 0
def makeRoot(self, node, left_node, right_node):
if self.root == None:
self.root = node
node.left = left_node
node.right = right_node
if __name__ == "__main__":
node = []
node.append(Node('-'))
node.append(Node('*'))
node.append(Node('/'))
node.append(Node('A'))
node.append(Node('B'))
node.append(Node('C'))
node.append(Node('D'))
m_tree = Tree()
for i in range(int(len(node)/2)):
m_tree.makeRoot(node[i],node[i*2+1],node[i*2+2])
print(m_tree.size())
print(m_tree.depth())이진트리 순회 구현 (python) >> 이건 완전 이진 트리이다..ㅠ 순회구현은 백준 알고리즘 문제 참고**
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __str__(self):
return str(self.data)
class Tree:
def __init__(self):
self.root = None
# 전위 순회 : DLR
def preorderTraversal(self, node):
print(node, end='')
if not node.left == None : self.preorderTraversal(node.left)
if not node.right == None : self.preorderTraversal(node.right)
# 중위 순회 : LDR
def inorderTraversal(self, node):
if not node.left == None : self.inorderTraversal(node.left)
print(node, end='')
if not node.right == None : self.inorderTraversal(node.right)
# 후위 순회 : LRD
def postorderTraversal(self, node):
if not node.left == None : self.postorderTraversal(node.left)
if not node.right == None : self.postorderTraversal(node.right)
print(node, end='')
def makeRoot(self, node, left_node, right_node):
if self.root == None:
self.root = node
node.left = left_node
node.right = right_node
if __name__ == "__main__":
node = []
node.append(Node('-'))
node.append(Node('*'))
node.append(Node('/'))
node.append(Node('A'))
node.append(Node('B'))
node.append(Node('C'))
node.append(Node('D'))
m_tree = Tree()
for i in range(int(len(node)/2)):
m_tree.makeRoot(node[i],node[i*2+1],node[i*2+2])
print( '전위 순회 : ', end='') ; m_tree.preorderTraversal(m_tree.root)
print('\n' + '중위 순회 : ', end='') ; m_tree.inorderTraversal(m_tree.root)
print('\n' + '후위 순회 : ', end='') ; m_tree.postorderTraversal(m_tree.root)이진 탐색 트리(binary search tree)
이진 탐색 트리는 기본적인 특징은 이진 트리와 같지만 하나 다른 점은 자기 왼쪽에는 자신보다 값이 작은 노드가, 오른쪽에는 자신보다 값이 큰 노드가 와야한다는 것이다.
이진 트리의 규칙
- 모든 원소는 서로 다른 키를 갖는다.
- 왼쪽 서브 트리에 있는 원소들은 루트의 키보다 작다.
- 오른쪽 서브 트리에 있는 원소들은 루트의 키보다 크다.
- 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.
이진 트리의 시간 복잡도
이진 탐색 트리의 평균 시간복잡도는 O(logN)이지만
최악의 경우 트리의 높이 h는 O(n)이다. >> 편향 트리일 경우
따라서 균형잡힌 트리 >> 레드-블랙 트리 등을 대안으로 사용한다.
원소 삽입 구현 (python)
def insertElement(self, data):
new_node = Node(data)
if self.root == None:
self.root = new_node
node = self.root
while True:
pre_node = node
# 새 노드의 데이터가 작으면
# 왼쪽으로 이동
if node.data > new_node.data:
node = node.left
# 이동한 노드가 빈 노드면 노드 추가
if node == None:
node = new_node
pre_node.left = node
# 새 노드의 데이터가 크면
# 오른쪽으로 이동
elif node.data < new_node.data:
node = node.right
if node == None:
node = new_node
pre_node.right = node
else: return # 똑같은 키가 있으면 취소원소 탐색 구현 (python)
같은 원소가 있는 경우 반환
def searchElement(self, data):
node = self.root
while True:
if node.data > data:
node = node.left
elif node.data < data:
node = node.right
elif node.data == data:
break
else:
return Node('탐색 결과 없음')
return node이진 탐색 트리 전체 코드 (python)
import random
class Node:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
def __str__(self):
return str(self.data)
class SearchTree:
def __init__(self):
self.root = None
def insertElement(self, data):
new_node = Node(data)
if self.root == None:
self.root = new_node
node = self.root
while True:
pre_node = node
if node.data > new_node.data:
node = node.left
if node == None:
node = new_node
pre_node.left = node
elif node.data < new_node.data:
node = node.right
if node == None:
node = new_node
pre_node.right = node
else: return
def searchElement(self, data):
node = self.root
while True:
if node.data > data:
node = node.left
elif node.data < data:
node = node.right
elif node.data == data:
break
else:
return Node('탐색 결과 없음')
return node
if __name__ == "__main__":
m_tree = SearchTree()
m_tree.insertElement(250)
for i in range(20):
m_tree.insertElement(random.randint(0,500))
node = m_tree.searchElement(250)
print('\n' + '탐색한 노드의 값 :', node)
print( '노드의 왼쪽 서브 트리 :', node.left)
print( '노드의 오른쪽 서브 트리 :', node.right)
node = m_tree.searchElement(node.left.data)
print('\n' + '탐색한 노드의 값 :', node)
print( '노드의 왼쪽 서브 트리 :', node.left)
print( '노드의 오른쪽 서브 트리 :', node.right)