이진 탐색 트리 (Binary Search Trees)

이진 탐색 트리는 이진 트리의 일종으로 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리이다. 단 중복되는 데이터는 없는것으로 가정한다.

이진 탐색 트리는 데이터 검색을 하는데 유용하게 이용된다. 이러한 탐색법은 이진탐색과 비슷해보인다,

 

 

 

 

정렬된 배열을 이용한 이진 탐색과 비교

정렬된 배열을 이용한 이진 탐색

트리를 이용한 이진 탐색

이진 탐색 트리를 이용했을 때는 배열을 이용하는 것 보다 데이터의 추가, 삭제가 용이하다. 하지만 공간을 많이 차지한다는 단점이 있다. 또 항상 O(logN)의 복잡도를 갖고있진 않는다.

 

 

 

 

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

데이터 표현 - 각 노드는 (key, value)의 쌍으로 표현한다. 키를 이용해서 검색가능, 보다 복잡한 데이터 레코드로 확장 가능하다. 숫자가 key, 이름이 value

연산의 정의

• insert(key, data) - 트리에 주어진 데이터 원소를 추가
• remove(key) - 특정 원소를 트리로 부터 삭제
• lookup(key) - 특정 원소를 검색
• inorder() - 키의 순서대로 데이터 원소를 나열
• min(), max() - 최소 키, 최대 키를 가지는 원소를 각각 탐색

 

 

 

이진 탐색 트리에 원소 삽입

 

 

코드 구현 - 초기화

class Node:
    # 초기화
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None
        
class BinSearchTree:
    # 저번에는 인자를 주었는데 이번에는 none으로 초기화
    def __init__(self):
        self.root = None

 

 

 

코드 구현 - inorder traversal

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
            
            
            
# 이진 탐색 트리 클래스
class BinSearchTree:
    
    def min(self):
        # 루트 노드가 존재하면
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

 

 

 

코드 구현 - lookup()

• 입력인자 - 찾으려는 대상 키
• 리턴 - 찾은 노드와 그것의 부모 노드(삭제에 이용됨) 각각 없으면 None으로

# 노드 클래스
class Node:

    # parent 인자가 주어지지않으면 None으로 생각하라는 말
    def lookup(self, key, parent=None):
        # 지금 방문된 노드(self.key)보다 탐색하려는 키가 작으면 왼쪽으로 가야함
        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            

 

 

 

코드 구현 - insert()

• 입력 인자 - 키, 데이터 원소
• 리턴 - 없음

class Node:
    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:
            print("중복된 노드가 존재")

        return True
        
        
class BinSearchTree:
    # 노드 삽입
    def insert(self, key, data):
        # 존재하는 트리라면
        if self.root:
            self.root.insert(key,data)
        
        # 트리가 존재하지않다면 해당 노드를 루트에 넣는다.
        else:
            self.root = Node(key, data)
            
            

 

 

 

이진 탐색 트리에서 원소 삭제

• 키(key)를 이용해서 노드를 찾는다. 만약 해당 키의 노드가 없으면 삭제할 것이 없음, 노드가 있으면 찾은 노드의 부모 노드도 알고있어야한다.
• 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다 (부모노드를 알아야하는 이유)

 

원소 삭제의 인터페이스 설계

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

 

이진 탐색 트리 구조의 유지

삭제되는 노드가

1. 말단(leaf)노드인 경우 -> 그냥 그 노드를 없애면 됨 부모 노드의 링크 조정(좌? 우?)
2. 자식을 하나 가지고 있는 경우 -> 삭제되는 노드 자리에 그 자식을 대신 배치한다. 자식이 왼쪽인지 오른쪽인지, 부모 노드의 링크를 조정(좌? 우?)
3. 자식을 둘 가지고 있는 경우 -> 삭제되는 노드보다 바로 다음 (큰) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제한다.

 

 

원소 삭제의 경우 1 - 삭제하려는 노드가 말단(leaf)노드일 때

 

 

원소 삭제의 경우 2 - 자식이 하나인 노드의 삭제

 

원소 삭제의 경우3 - 자식이 둘인 노드의 삭제

생각을 많이 해봐야하는 경우다. 예제로 생각을 해보자.

노드 5를 삭제하는 경우

 

 

노드 8을 삭제하는 경우

 

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):
        # 삭제하려는 노드와 p를 검색
        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 parent.left == node:
                        parent.left = None
                    if 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:
                    temp = node.left
                else:
                    temp = node.right

                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if parent.left == node:
                        parent.left = temp
                    else:
                        parent.right = temp
                
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = temp
            
            # 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:
                    parent = successor
                    successor = successor.left
                
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data

                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                    

            return True

        else:
            return False

어떻게 풀긴했지만 너무 어렵네,, 마지막에 successor가 parent의 왼쪽 자식인지 오른쪽 자식인지 판단하는 부분이 잘 이해가 가지 않는다. 그림 그려서 돌아가는걸 확인해보니 해결됐다. 너무 복잡하고 헷갈리는구만

 

 

 

 

 

이진트리가 효율적이지 못한 경우

순서대로 삽입하는 경우에 효율적이지 못하다. -> 한쪽으로 치우친 모양

 

 

 

 

보다 나은 성능을 보이는 이진 탐색 트리들 (참고)

높이의 균형을 유지함으로써 O(logN)의 탐색 복잡도를 보장한다. 삽입, 삭제 연산이 보다 복잡함 

AVL tree - https://ko.wikipedia.org/wiki/AVL_트리 

AVL 트리 - 위키백과, 우리 모두의 백과사전

Red black tree - https://ko.wikipedia.org/wiki/레드-블랙_트리 

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전