[파이썬 자료구조] 이진 탐색 트리 (코드 구현 - 찾기, 순회, 삽입, 제거)

우선 이진 탐색 트리란,

모든 노드에 대해서,

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

(단, 중복되는 데이터 원소는 없는 것으로 가정)

 

 

1. 정렬된 배열을 이용한 이진 탐색과 이진 탐색 트리의 비교

이진 탐색 트리의 장점

• 데이터 원소의 추가, 삭제가 용이

이진 탐색 트리의 단점

• 공간 소요가 크다
• 항상 O(logn)의 탐색 복잡도를 가지는 것이 아니다.

 

 

 

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

• 데이터 표현 - 각 노드는 (key, value) 의 쌍으로
  • 키를 이용해서 검색 가능
  • 보다 복잡한 데이터 레코드로 확장 가능
• 연산의 정의
  • insert (key, data) - 트리에 주어진 데이터 원소를 추가
  • remove (key) - 특정 원소를 트리로부터 삭제
  • lookup(key) - 특정 원소를 검색
  • inorder() - 키의 순서대로 데이터 원소를 나열
  • min(), max() - 최소 키, 최대 키를 가지는 원소를 각각 탐색

 

다른 연산들은 크게 복잡하지 않은데 remove 연산의 경우 경우에 따라 나눠주어야 하기 때문에 꽤 복잡해진다.

 

remove() 코드 설계

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

인터페이스의 설계

입력: 키(key)

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

이진 탐색 트리 구조의 유지

삭제되는 노드가

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

 

그렇다면 이제 구현한 코드를 봐보자

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,r):
        self.root = r


    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:
                if parent:
                    if parent.left==node:
                        parent.left=None
                    elif parent.right==node:
                        parent.right=None
                else:
                    self.root=None
            # When the node has only one child
            elif nChildren == 1:
                if node.left:
                    var=node.left
                else:
                    var=node.right
                if parent:
                    if parent.left==node:
                        parent.left=var
                    elif parent.right==node:
                        parent.right=var
                else:
                    self.root=var
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                while successor.left:
                    parent=successor
                    successor=successor.left
                node.key = successor.key
                node.data = successor.data
                if parent.left==successor:
                    parent.left=successor.right
                elif parent.right==successor:
                    parent.right=successor.right
                

            return True

        else:
            return False


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

 

 

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

 

left와 right 양쪽의 균형이 잘 잡혀있지 않으면 선형 탐색에 가까워지기 때문에 효율이 떨어진다.

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

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

삽입, 삭제 연산이 보다 복잡

아래 트리들을 참고 할 것.

AVL trees
Red-black trees