이진 탐색 트리 (Binary Search Trees)

- 왼쪽 서브트리의 모든 값 < 본인 < 오른쪽 서브트리의 모든 값 

- 중복된 원소는 없다.

- 데이터 검색에 이용

- 정렬된 배열에서의 이진탐색과 유사하나, 배열에 비해 데이터 원소의 추가 및 삭제가 용이하다.

- BUT 배열에 비해 공간복잡도가 크고, 시간 복잡도는 클 수도 있다. (이진 탐색 트리가 항상 logn인 것은 아님)

 

 

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

- 데이터가 (key, value) 쌍으로 표현됨

 

 

[연산의 종류]

1. insert(key, data) - 주어진 원소 추가

2. remove(key) - 특정 key 값 가진 원소 트리에서 삭제

3. lookup(key) - 특정 key 값 가진 원소 검색 -> bfs/dfs로 탐색, 찾은 노드+부모노드 함께 반환 -> 다른 함수에서 쓰기 위해

4. inorder() - 키의 순서대로 데이터 원소를 나열

5. min(), max() - 정렬된 그래프이므로, 최대 최소 키를 갖는 원소 탐색 가능

 

 

[자료 구조 구현]

 

1. 노드

 

class Node:
    def __init__(self,key,data): #key, data 쌍을 가진 원소
        self.key = key
        self.data = data
        self.left = None
        self.right = None
        
    def inorder(self):
        traversal = []
        
        if self.left:
            traversal+=self.left.inorder()
        traversal.append(self) ##이전과 다른 점 - key, data 쌍이므로 노드 자체를 append
        if self.right:
            traversal _- self.right.inorder()
        return traversal
        
    def min(self): #최솟값을 찾아 왼 쪽으로 이동, max는 오른 쪽으로 이동
        if self.left:
            return self.left.min()
        else:
            return self
            
    def lookup(self,key,parent = None): #parent 인자 안 주면 None으로 처리
        if self.key==key:
            return self, parent #root가 아니라면 항상 None이 아님
        elif self.key>key:
            if self.left:
                self.left.lookup(key,self) #자식에게 본인을 인자로 줌             
            else:
                return None, None
        elif self.key<key:
            if self.right:
                self.right.lookup(key,self)
            else:
                return None,None
                
    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else: #왼쪽 노드가 없으므로 이 자리에 들어감
                self.left = Node(key,data)
        elif key>self.key:
            if self.right:
                self.right.insert(key,data)
            else: #오른쪽 노드가 없으므로 여기 들어감
                self.right = Node(key,data)
        else: #중복된 키는 없다.
            raise KeyError
            
    def countChildren(self): #자식의 개수에 따라 삭제 방법이 다르므로 알아야 함
        count = 0
        if self.left:
            count+=1
        if self.right:
            count+=1
        return count

 

 

 

2. 이진 트리

 

class BinSearchTree:
    def __init__(self):
        self.root = None
    
    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []
            
    def min(self): #max도 같음
        if self.root:
            return self.root.min()
        else:
            return None
    
    def lookup(self,key):
        if self.root:
            self.root.lookup(key)
        else:
            return None, None #자식과 부모 둘다 리턴해야 하므로
            
    def insert(self, key, data):
        if self.root:
            self.root.insert(key,data)
        else:
            self.root = Node(key,data)
            
    def remove(self,key): #key를 가진 노드, 부모 리턴
        #좀 이ㄸㅏ 등장

 

 

[이진 탐색 트리의 원소 삭제 알고리즘]

1. 키(key)를 이용해서 노드를 찾는다. (lookup)
    -> 만약 노드가 없다면, 삭제할 것도 없음 (False 반환)
    -> 만약 노드가 있다면, 해당 노드와 노드의 부모노드를 반환받는다.(lookup함수의 특징, root 제외)
2. 부모 노드를 이용해 이진 탐색 트리 구조를 다시 정리한다. (이후 True 반환)

 

[삭제 후 이진 탐색 트리 재정비]

-> 삭제되는 노드의 자식 개수(0,1,2)에 따라 다름

- 삭제 이후 모든 트리는 그 성질을 유지한다(왼쪽 서브트리 <노드 <오른쪽 서브트리)

- 삭제되는 노드가 속한 서브트리 이외의 트리의 다른 부분은 삭제 후에도 변함없이 규칙을 유지중이다.

 

1. 리프 노드의 경우

  1) 자식이 없으므로 해당 노드를 삭제하고

  2) 그것과 이어졌던 부모의 링크를 None으로 조정 (왼쪽, 오른쪽 중 삭제된 노드가 소속된 링크)

  **만약 삭제되는 노드가 root노드인 경우, 트리 자체가 없어진다.

 

2. 자식이 하나 있는 경우

  1) 삭제되는 노드의 자리에, 그 자식(왼쪽 또는 오른쪽)을 배치한다.

  2) 삭제되는 노드의 부모의 링크(삭제되는 노드가 있던 링크)도 그 노드를 가리키도록 None으로 조정한다.

**삭제되는 노드가 root인 경우, 대신 들어오는 자식이 root가 된다.

 

3. 자식이 둘 있는 경우

 1) 삭제되는 노드 바로 다음 키(전체 트리에서 삭제노드 바로 다음으로 큰/작은 키)를 찾아서, 대신 그 자리에 배치한다.

  ->즉, 삭제되는 노드의 오른쪽 서브트리에 있는 키(모두 삭제노드의 키보다 큼)중 가장 작은 노드를 찾으면 된다.(왼쪽 자식을 찾아서 감)

 - 찾은 노드를 삭제된 노드의 자리에 배치한다.

 

 2) 찾은 노드의 부모 노드 링크를 조정한다.

 - '찾은 노드의 부모노드'는 삭제된 노드일 수도 있고, 그 노드의 오른쪽 서브트리에 소속된 노드일 수도 있다.

 - 전자의 경우 '찾은 노드의 부모노드'의 오른쪽 링크를, 후자의 경우 왼쪽 링크를 수정한다.

 - 찾은 노드는 오른쪽 서브트리에서 가장 작은 자식이므로, 더 이상 왼쪽 자식이 없을 것이고, 오른쪽 자식은 있을 수도, 없을 수도 있다.

 - 만약 찾은 노드가 오른쪽 자식이 있다면, 찾은 노드의 부모노드의 링크를 그 오른쪽 자식에 연결한다. 

 - 만약 찾은 노드가 자식이 없다면, 찾은 노드의 부모노드가 더이상 찾은 노드가 아닌 None을 가리키게 된다.

 

class BinaryTree:
##다른 메소드 ###
    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent가 있으면 그냥 None으로 연결 끊어내고 끝
                if parent:
                    if parent.left ==node:
                        parent.left = None
                    elif parent.right == node:
                        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:
                    child = node.left
                elif node.right:
                    child = node.right
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent의 링크가 그걸 가리키도록 함
                if parent:
                    if parent.left == node:
                        parent.left = child
                    elif parent.right == node:
                        parent.right = child
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣음
                else:
                    self.root = child
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
				#node의 오른쪽 서브 트리에서 가장 작은 노드를 찾기 위한 과정
                #node의 오른쪽 자식이 왼쪽 자식이없다면 넘어가고, 있다면 그중 제일 왼쪽 것을 찾는다.
                while successor.left:
                    parent = successor
                    successor = successor.left
                    
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입
                # 삭제될 노드 대신 대입
                node.key = successor.key
                node.data = successor.data
                
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                if parent.left == successor:
                #node의 오른쪽 자식이 아니라, 그것의 제일 왼쪽 자식
                    parent.left = successor.right
                elif parent.right == successor:
                #node의 오른쪽 자식의 제일 왼쪽 자식
                    parent.right = successor.right
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 함
                # successor 가 오른쪽 자식이 None이든 무언가 있든 상관 X
            return True

        else:
            return False

 

 

 

 

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

 

- 연속해서 계속 작아지거나, 계속 커지는 순으로 자료가 입력될 때, 선 형태의 트리가 만들어지므로 선형 탐색과 같은 복잡도를 가지게 된다. (이때 시간 복잡도는 O(logN)이 아니라 O(N)에 가까워질 것이다.)

-> 트리의 균형을 유지해 O(logN)의 탐색도를 보이는 이진 탐색 트리로 AVL tree, Red-black tree가 있다