이진 탐색 트리(Binary Search Trees)

정의

모든 노드에 대해서,

• 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
• 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰

성질을 만족하는 이진 트리를 말한다.

---

• 이진 탐색과 매우 연관이 깊은 자료구조 -> 탐색에 특화된 자료구조
• (장점) 데이터의 원소의 추가, 삭제가 용이하다.
• (단점) 공간 소요가 큼

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

• 데이터 표현 - 각 노드는(key, value) 의 쌍으로 관리. 키를 노드의 번호로 하고 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

 

inorder, min, max 까지의 구현

class Node:
    def __init__(self, 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)
        if self.right:
            traversal += self.right.inorder()
    
    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 __init__(self):
        self.root = None

    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []
        
    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:
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None
    
    def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self) # self = parent node
            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 __init__(self):
        self.root = None
    
    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:
            pass
        elif key > self.key:
            pass
        else:
            raise KeyError('...')

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

위 Node의 insert 메서드 조건문 안에 내용 채우는 것은 과제!

 

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = 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 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 __init__(self):
        self.root = None


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


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


def solution(x):
    return 0

---

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

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

인터페이스 설계

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

이진 탐색 트리 구조의 유지

삭제 되는 노드가

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

말단 노드의 삭제

📌 만약 삭제되는 노드 x 가 root node인 경우라면?

트리 자체가 삭제되도록 구현하면 된다. ex) self.root = None

자식이 하나인 노드의 삭제

삭제할 노드: X, 부모 노드: P

만약 X의 왼쪽이 아닌 오른쪽에만 자식 노드가 있었어도 마찬가지다.

📌 중요한 키포인트는 삭제한 이후에도 이진 탐색 트리의 구조가 맞는지 검정하는 과정이 꼭 필요하단 것. 부모의 링크 포인트에 유의하며 구현해보기

📌 삭제되는 노드(X)가 root node인 경우에는 하나 있는 자식노드가 root node가 된다.

 

자식이 둘인 노드의 삭제

삭제 구현 - 과제

 

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = 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('Key %s already exists.' % key)


    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


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


    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

    def __init__(self):
        self.root = None


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


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


    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 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


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


def solution(x):
    return 0

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

 

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

만약 한쪽으로 치우쳐져 있고 균형이 잡혀있지 않은 트리일 경우에는 선형탐색과 동등해 지므로 효율적이지 못하다.

 

보다 나은 성능을 보이는 이진 탐색 트리들

높이의 균형을 유지함으로써 O(logN)의 탐색 복잡도 보장

삽입, 삭제 연산이 복잡함

📌 AVL 트리

📌 레드-블랙 트리