이진 탐색 트리(Binary Search Trees)

1 이진 탐색 트리(Binary Search Trees) 란?

• 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리
  • 중복되는 원소는 없다고 가정
• 배열을 이용한 이진 탐색 알고리즘과 유사하다

• 장점: 데이터 원소의 추가, 삭제가 용이
• 단점: 공간 소요가 크다
  • 트리는 왼쪽, 오른쪽 자식도 기록해 두어야 한다

• 항상 O(logn)의 탐색 복잡도를 갖는다

2 이진 탐색 트리의 추상적 자료구조

2.1 데이터 표현

• 각 노드는 (key, value) 의 쌍으로
  • key를 이용해 검색 가능
  • 보다 복잡한 데이터 레코드로 확장 가능

class Node:
		def __init__(self, key, data):
				self.key = key
				self.data = data
				self.left = None
				self.right = None
		
class BinSearchTree:
		def __init__(self):
				self.root = None

2.2 연산의 정의

• insert(key, data): 트리에 주어진 데이터 원소를 추가

class Node:
		def insert(self, key, data):
        if key < self.key:
            if self.left:
                return self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif key > self.key:
            if self.right:
                return self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
            raise KeyError

class BinSearchTree:
		def insert(self, key, data):
				if self.root:
						self.root.insert(key, data)
				else:
						self.root = Node(key, data)

• remove(key): 특정 원소를 트리로부터 삭제

1. 키를 이용해서 노드를 찾는다

   • 해당 키의 노드가 없으면 삭제할 것도 도 없다

2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정의한다

   → 이를 위해 찾은 노드의 부모 노드도 알고 있어야 한다

• 입력: 키(eky)
• 출력: 삭제한 경우 True, 해당 노드가 없는 경우 False

노드를 삭제할 때는 다음과 같이 세 가지 경우를 고려해야 한다

1. 말단 (leaf) 노드를 삭제하는 경우

   → 그 노드를 없애고 부모 노드의 링크를 조정한다

   

   삭제하는 노드가 root 노드라면?

   → 대신 자리로 들어오는 노드가 root 노드가 된다

2. 자식을 하나 가지고 있는 노드를 삭제하는 경우

   → 삭제되는 노드 자리에 그 자식을 대신 배치

   

3. 자식을 둘 가지고 있는 노드를 삭제하는 경우

   → 삭제되는 노드보다 바로 다음 (큰) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제

   

class Node:
		# 자식의 개수를 세는 함수
		def countChildren(self):
				count = 0
				if self.left:
						count += 1
				if self.right:
						count += 1
				return count				

class BinSearchTree:
		def remove(self, key):
        node, parent = self.lookup(key)
        
        if node:
            nChildren = node.countChildren()
            
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                if parent:
                    if key < parent.key: # 왼쪽 자식
                        parent.left = None
                    else:       # 오른쪽 자식
                        parent.right = None
                
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None
                    
            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:   # 왼쪽 자식
                    children = node.left
                else:   # 오른쪽 자식
                    children = node.right
                    
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if key < parent.key:   # 왼쪽 자식
                        parent.left = children
                    else:       # 오른쪽 자식
                        parent.right = children
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = children
                    
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                # parent 는 node 를 가리키고 있고,
                # successor 는 node 의 오른쪽 자식을 가리키고 있으므로
                # successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
                # 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
                # 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
                while successor.left:
                    successor = successor.left
            
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                self.remove(successor.key)
                
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data

            return True

        else:
            return False

• lookup(key): 특정 원소를 검색
  • 입력: 찾으려는 대상 키
  • 리턴: 찾은 노드와 그것의 부모 노드
    • 각각, 없으면 None

class Node:
		def lookup(self, key, parent=None):
				if key < self.key:
						if self.left:
								return self.left.lookup(key, self)
						else: # 못찾은 경우
								return None, None
				elif key > self.key:
						if self.right:
								return self.right.lookup(key, self)
						else: # 못찾은 경우
								return None, None
				else: # 일치한다
						return self, parent

class BinSearchTree:
		def lookup(self, key):
				if self.root:
						return self.root.lookup(key)
				else:
						return None, None

• inorder(): 키의 순서대로 데이터 원소를 나열

class Node: 
		def inorder(self):
						traversal = []
						
						if self.left:
								traversal += self.left.inorder()	
						traversal.append(self)
						if self.right:
								traversal += self.right.inorder()
								
						return traversal

class BinSearchTree:
		def inorder(self):
				if self.root:
						return self.root.inorder()
				else:
						return []

• min(), max(): 최소 키, 최대 키를 가지는 원소 탐색

class Node: 
		def min(self):
				if self.left:
						return self.left.min()
				else:
						return self
		
		def max(self):
				if self.right:
						return self.right.max()
				else:
						return self

3 이진 탐색 트리가 별로 효율적이지 못한 경우

• 트리가 왼쪽, 혹은 오른쪽으로 치우친 경우 트리로써 가지는 효율성을 잃게 된다
• 이진 트리는 높이의 균형을 유지함으로써 O(logn)의 탐색 복잡도를 보장한다 → AVL tree, Red-black tree는 이진 탐색 트리에 규칙을 추가해 좋은 탐색 성능을 갖추기 위해 만들어진 자료구조