[자료구조] 탐색 트리

1. 이진 탐색 트리

(1) 정의

- 탐색 트리 : 탐색을 위한 트리 기반의 자료 구조

- 이진 탐색 트리 : 효율적인 탐색을 위한 이진 트리 기반의 자료 구조, 삽입/삭제/탐색의 시간복잡도는 O(log(2)n)이다.

- 이진 탐색 트리의 특징 : 

  모든 노드는 유일한 키를 가짐, 왼쪽 서브트리의 키 < 루트의 키 < 오른쪽 서브트리의 키, 왼쪽과 오른쪽 서브트리도 이진탐색트리

(2) 노드 구조

class BSTNode :     def __init__(self, key, value) :         self.key = key         self.value = value         self.left = None         self.right = None

(3) 탐색

- 순환 구조 혹은 반복 구조로 구현

# 순환 구조 def search_bst(n, key) :     if n == None :         return None     elif key == n.key :         return n     elif key < n.key :         return search_bst(n.left, key)     else :         return search_bst(n.right, key) # 탐색(반복) 구조 def search_bst_iter(n, key) :     while n != None :         if key == n.key :             return n         elif key < n.key :             n = n.left         else :             n = n.right     return None

- '키'가 아닌 '값'을 이용한 탐색 시 모든 노드의 검사 필요

- 최대와 최소 노드 탐색

def search_max(n) :     while n!= None and n.right != None :         n = n.right     return n def search_min(n) :     while n!= None and n.left != None :         n = n.left     return n

(4)  삽입 연산

- 탐색이 실패한 위치에 노드 삽입

# 순환 구조 이용 def insert_bst(r, n) :     if n.key < r.key :         if r.left is None :             r.left = n             return True         else :             return insert_bst(r.left, n)     elif n.key > r.key :         if r.right is None :             r.right = n             return True         else :             return insert_bst(r.right, n)     else :         False

(5) 삭제 연산

- 삭제하려는 노드는 3가지 경우로 나누어짐

- 단말 노드일 경우, 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우

- 두 개의 서브트리를 모두 가지고 있는 경우

# 단말 노드인 경우 def delete_bst_case1(parent, node, root) :     if parent is None :         root = None     else :         if parent.left == node :             parent.left = None         else :             parent.right = None     return root # 한쪽만 가진 경우 def delete_bst_case2(parent, node, root) :     if node.left is not None :         child = node.left     else :         child = node.right     if node == root :         root = child     else :         if node is parent.left :             parent.left = child         else :             parent.right = child     return root # 양쪽 다 가진 경우 def delete_bst_case3(parent, node, root) :     succp = node     succ = node.right     while (succ.left != None) :         succp = succ         succ = succ.left     if (succp.left == succ) :         succp.left = succ.right     else :         succp.right = succ.right     node.key = succ.key     node.value = succ.value     node = succ     return root # 통합 def delete_bst(root, node) :     if root = None : return None     parent = None     node = root     while node != None and node.key != key :         parent = node         if key < node.key : node = node.left         else : node = node.right     if node == None : return None     if node.left == None and node.right == None :         root = delete_bst_case1(parent, node, root)     elif node.left == None or node.right == None :         root = delete_bst_case2(parent, node, root)     else :         root = delete_bst_case3(parent, node, root)     return root

(6) 이진 탐색 트리의 성능

 - 탐색, 삽십, 삭제 연산의 시간 트리의 높이에 비례함

 - 키를 이용한 탐색, 값을 이용한 탐색, 최대/최소 노드 탐색, 삽입, 삭제 모두 O(n)  

(7) 이진 탐색 트리 맵 클래스

class BSTMap() :     def __init__(self) :         self.root = None     def isEmpty(self) : return self.root == None     def clear(self) : self.root = None     def size(self) : return count_node(self.root)     def search(self, key) : return search_bst(self.root, key)     def searchValue(self, key) : return search_value_bst(self.root, key)     def findMax(self) : return search_max_bst(self.root)     def findMin(self) : return search_min_bst(self.root)     def insert(self, key, value=None) :         n = BSTNode(key, value)         if self.isEmpty() :             self.root = n         else :             insert_bst(self.root, n)     def delete(self, key) :         delete_bst(self.root, key)     def display(self, msg = 'BSTMap : ') :         print(msg, end =' ')         inorder(self.root)         print()

(8) Test Code

map = BTSMap() data = [35,18,7,26,12,3,68,22,30,99] print("삽입 연산 : ", data) for key in data :     map.insert(key) map.display("중위 순회 : ") if map.search(26) != None : print("탐색 26 : 성공") else : print("탐색 26 : 실패") if map.search(25) != None : print("탐색 25 : 성공") else : print("탐색 25 : 실패") map.delete(3) map.display("[3 삭제] : ") map.delete(68) map.display("[68 삭제] : ") map.delete(18) map.display("[18 삭제] : ")

삽입 연산 :  [35, 18, 7, 26, 12, 3, 68, 22, 30, 99] 중위 순회 :  3 7 12 18 22 26 30 35 68 99  탐색 26 : 성공 탐색 25 : 실패 [3 삭제] :  3 7 12 18 22 26 30 35 68  [68 삭제] :  3 7 12 18 22 26 30 35 68  [18 삭제] :  3 7 12 18 22 26 30 35 68

2. AVL 트리

(1) 정의

- Adelson Velskii Landis

- 균형인수 = 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이 (AVL은 0, +1, -1 중에 하나인 트리)

- 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리

- 평균, 최악, 최선의 시간 복잡도는 O(log(2)n)을 보장함

- 삽입과 삭제 시 균형 상태가 깨질 수 있음

(1) AVL 트리의 탐색 연산 = 이진 탐색 트리와 동일

(2) AVL 트리의 삽입 연산

- 삽입 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 미침

- 삽입 후에 불균형 상태로(균형 인수가 ±2) 변한 가장 가까운 조상 노드의 서브 트리들에 대하여 재균형

- 삽입 노드부터 균형인수가 ±2가 된 가장 가까운 조상 노드까지 회전

def rotateLL(A) :     B= A.left     A.left = B.right     B.right = A     return B def rotateRR(A) :     B = A.right     A.right =  B.left     B.left = A     return B def rotateRL(A) :     B = A.left     A.left =  B.left     B.left = A     return B def rotateLR(A) :     B = A.right     A.right =  B.right     B.right = A     return B def reBalance(parent) :     hDiff = cal_height_diff(parent)     if hDiff > 1 :         if cal_height_diff(parent.left) > 0 :             parent = rotateLL(parent)         else :             parent = rotateLR(parent)     elif hDiff < -1 :         if cal_height_diff(parent.right) > 0 :             parent = rotateRR(parent)         else :             parent = rotateRL(parent)     return parent def insert_avl(parent) :     if node.key < parent.key :         if parent.left != None :             parent.left = insert_avl(parent.left.node)         else :             parent.left = node         return reBalance(parent)     elif node.key > parent.key :         if parent.right != None :             parent.right = insert_avl(parent.right, node)         else :             parent.right = node         return reBalance(parent)     else :         print("중복된 키 에러")

(3) 트리 맵

node = [7,8,9,2,1,5,3,6,4] map = AVLMap() for i in node :     map.insert(i)     map.display("AVL(%d) : "%i)