이진탐색트리 - 각 노드 n의 키가 n의 왼쪽 서브트리에 있는 키들보다 크고, n의 오른쪽 서브트리에 있는 키들보다 작다.
꼭 자식이 2개여야지만 이진탐색 트리인 것은 아니다
노드를 생성할때는 키와 밸류만 가지고 lt와 rt는 none 상태로 초기화하고 삽입 연산을 통해서
이진탐색트리 탐색, 삽입, 삭제 연산
이진탐색트리 순회
전위순회 - 루트부터 방문해서 맨 처음 나오는게 루트
class Node:
def __init__(self, key, value, left = None, right = None):
self.key = key
self.value = value
self.left = left
self.right = right
class BST:
def __init__(self):
self.root = None
#탐색연산
def get(self, k):
return self.get_item(self.root, k)
def get_item(self, node, k):
if node == None: #탐색 실패
return None
if node.key > k:
return self.get_item(node.left, k)
elif node.key < k:
return self.get_item(node.right, k)
else:
return node.value
#삽입연산
def put(self, key, value):
self.root = self.put_item(self.root, key, value)
def put_item(self, node, key, value):
#n번째 노드가 없으면 생성
if node == None:
return Node(key,value)
# n번째 노드의 키값이
if node.key > key:
node.left = self.put_item(node.left, key, value)
elif node.key < key:
node.right = self.put_item(node.right, key, value)
#기존에 해당 키 값이 있으므로 값을 갱신
else:
node.value = value
return node
#최소값 찾기, delete 연산에서 사용됨
def min(self):
if self.root == None:
return None
return self.minimum(self.root)
def minimum(self, node):
if node.left == None:
return node
return self.minimum(node.left)
def delete_min(self):
if self.root == None:
print('트리가 비었음')
self.root = self.del_min(self.root)
#최소값 삭제 연산
def del_min(self, node):
if node.left == None:
return node.right
node.left = self.del_min(node.left)
return node
#삭제 연산
def del_node(self, node, k):
if node == None:
return None
if node.key > k :
node.left = self.del_node(node.left, k)
elif node.key < k:
node.right = self.del_node(node.right, k)
else:
if node.right == None:
return node.left
if node.left == None:
return node.right
target = node #삭제될 노드
node = self.minimum(target.right)
node.right = self.del_min(target.right)
node.left = target.left
return node
def preorder(self, node):
if node == None:
return
else:
print(node.key, end =' ')
self.preorder(node.left)
self.preorder(node.right)
def inorder(self, node):
if node == None:
return
else:
self.inorder(node.left)
print(node.key, end =' ')
self.inorder(node.right)
bst = BST()
bst.put(500,1)
bst.put(600, 1)
bst.put(200, 1)
bst.put(100, 1)
bst.put(400, 1)
bst.put(250, 1)
bst.put(150, 1)
bst.put(800, 1)
bst.put(700, 1)
bst.put(50, 1)
bst.put(350, 1)
bst.put(10, 1)
bst.preorder(bst.root)
print()
bst.inorder(bst.root)
print()
print(bst.get(10))
print(bst.min().key)
AVL 트리 - 임의의 노드에 대해서 왼쪽, 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진탐색트리
