이진탐색트리 (Binary Search Tree)에 대해 – python

Binary Search Tree

이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.

이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.

탐색 트리의 옵션

이진 탐색 트리 구조는 다음과 같은 기능을 제공한다.

  • 새로운 맵 생성
  • 키-값 쌍 저장 : put(key, val)과 같은 형식으로 키 값 쌍을 저장한다.
  • 키를 사용하여 값 얻기: get(key는 키에 대한 값을 리턴한다.
  • del 명령으로 특정 키-값 제거. __delete__를 구현한다.
  • len 명령으로 노드의 수 구하기. __len__을 구현한다.
  • in 명령으로 키가 있는지 검사. __contains__ 프로토콜을 구현한다.

이진 탐색 트리는 이진 탐색 알고리듬의 규칙을 활용한다.

  • 트리에는 루트 노드가 존재한다. 이는 최초로 추가되는 키/값 쌍을 담는다.
  • 신규 키가 추가되면, 루트로부터 각 노드의 키와 신규 키를 비교한다.
    • 신규 키가 현재 노드의 키보다 작으면 왼쪽 자식 노드에 추가된다.
    • 신규 키가 현재 노드의 키보다 크면 오른쪽 자식 노드에 추가된다.
    • 이미 해당 노드의 자식 노드가 있다면 다시 자식 노드의 키와 비교한다.
  • 값을 찾는 경우에도 루트 노드로부터 키의 대소를 비교하여 내려가면 원하는 키를 찾을 수 있다.

노드 클래스

따라서 각 노드 객체는 다음과 같은 기능을 기본적으로 가져야 한다.

  • 키와 값 속성
  • 부모노드와 좌/우 자식 노드
  • 잎 노드인지 확인
  • 왼쪽 자식을 갖고 있는지 확인
  • 오른쪽 자식을 갖고 있는지 확인
  • 부모 노드에 대해 왼쪽 노드인지 확인
  • 부모 노드에 대해 오른쪽 노드인지 확인

그외에 노노드 삭제와 관련하여 다음의 기능을 가지고 있어야 한다.

  • 자신의 상속자(Successor)를 찾음. 상속자는 하위 노드 계통 중에서 자신보다 바로 다음번으로 키가 큰 노드이다.
  • 최소값찾기 : 자신의 자식 중에서 최소의 키를 가진 노드를 찾는다. 이는 상속자를 찾는 과정에 필요하다.
  • 노드 잘라내기. 노드 잘라내기는 상속자노드가 되는 노드를 트리구조에서 잘라내는 것을 말한다. 이 기능은 결국 자신의 오른쪽 노드값을 자신의 위치로 옮기는 일이다.

노드 클래스 구현

아래와 같이 기본적인 속성들을 구현해준다. 간단한 내용들이다. 별도로 양쪽 자식 노드가 다 존재하는지 여부를 알 수 있는 메소드를 추가했는데, 이는 트리 클래스에서 노드를 삭제할 때, 왼쪽 자식만 있을 때, 오른쪽 자식만 있을 때, 양쪽 모두에 자식이 있을 때 처리해야 하는 방식이 다르기 때문이다.

class TreeNode:
    def __init__(self, key, val, left=None, right=None, parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild is not None

    def hasRightChild(self):
        return self.rightChild is not None

    def isLeftChild(self):
        return self.parent and self.parent.leftChild is self

    def isRightChild(self):
        return self.parent and self.parent.rightChild is self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return not self.isLeaf()

    def hasBothChildren(self):
        return self.hasLeftChild() and self.hasRightChild()

트리 클래스 기초 구현

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

이제 키/값 쌍을 추가하는 로직을 구현해보자. 루트 노드가 없는 경우에는 바로 루트 노드가 추가되고, 그렇지 않은 경우에는 루트노드로 부터 키를 비교하여 자식을 추가하는 로직을 태운다.

def put(self, key, val):
    """ put method of BinarySearchTree class"""
    if self.root:
        self._put(key, val, self.root)
    else:
        self.root = TreeNode(key, val)

키를 비교하며 자식 노드로 추가되는 과정은 일종의 재귀 로직이기 때문이 별도의 함수로 분리한다.

def _put(self, key, val, currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
            self._put(key, val, currentNode.leftChild)
        else:
            currentNode.leftChild = TreeNode(key, value, parent=currentNode)
    else:
        if currentNode.hasRightChild():
            self._put(key, val, currentNode.rightChild)
        else:
            currentNode.rightChild = TreeNode(key, value, parent=currentNode)

그리고 dictionary와 같은 subscription 문법을 지원하기 위해서 __setitem__ 메소드를 구현한다.

def __setitem__(self, k, v):
    self.put(k, v)

이제 키를 통해 값을 받아오는 get 메소드를 구현해본다. 이진 탐색 트리의 알고리듬을 그대로 따르면 된다.

def get(self, key):
    if self.root is None:
        return None
    res = self._get(key, self.root)
    if res:
        return res.payload
    return None

def _get(self, key, currentNode):
    if key == currentNode.key:
        return currentNode
    elif key < currentNode.key:
        if currentNode.hasLeftChild():
            return self._get(key, currentNode.leftChild)
        else:
            return None
    else:
        if currentNode.hasRightChild():
            return self._get(key, currentNode.rightChild)
        else:
            return None

키 삭제

특정 키를 삭제하는 것은 조금 어려운데, 트리 구조를 유지해주기가 만만치 않기 때문이다. 키를 제거하는 과정은 1) 지울 키에 대한 노드를 찾고 2) 해당 노드를 제거한다. 이 때 이 노드의 자식 노드가 어떻게 달려있느냐에 따라 처리가 달라진다.

먼저 다음과 같이 키를 찾고, 지울 노드를 찾아보자.

def delete(self, key):
    if self.size > 1:
        nodeToRemove = self._get(key, self.root)
        if nodeToRemove:
            self.remove(nodeToRemove)
            self.size -= 1
        else:
            Raise KeyError('Error, key is not in tree.')
    elif self.size == 1 and self.root.key == key:
        self.root = None
        self.size = 0
    else:
        raise KeyError('Error, key is not in tree.')

실제 삭제될 노드가 루트가 아니면 내부 메소드인 _delete를 통해서 노드가 삭제된다.

잎 노드 삭제

노드를 삭제하는 것은 부모노드의 자신의 위치를 지우거나, 자신의 자식을 끼워넣으면 된다.

def remove(self, currentNode):
    if currentNode.isLeaf():
        if currentNode.isLeftChild():
            currentNode.parent.leftChild = None
        else:
            currentNode.parent.rightChild = None

삭제할 노드의 자식이 2개인 경우에는 처리가 복잡하므로 뒤로 미루겠다.

    elif currentNode.hasBothChildren():
        pass

1개 노드만 있는 경우를 먼저 처리한다.

    else:
        if currentNode.hasLeftChild():
            if currentNode.isLeftChild():
                currentNode.parent.leftChild = currentNode.leftChild
            else:
                currentNode.parent.rightChild = currentNode.leftChild
        else:
            if currentNode.isLeftChild():
                currentNode.parent.leftChild = currentNode.rightChild
            else:
                currentNode.parent.rightChild = currentNode.rightChild

제거할 노드가 어느쪽이든 한 개 자식만 있는 경우에는, 그 자식 노드가 제거할 노드가 부모노드에 대해 차지한 위치로 이동하면 된다. (실제 객체 자체를 릴리즈하는 것은 파이썬이 알아서한다. C라면 해제하는 작업을 별도로 거쳐야 한다.)

이제 아까 패스해버린 케이스를 살펴보자.

             19
          /     \
        13        28  
       /  \      /  \
     12    18   21   29
          /
         17
        /
       16
      /
    14
      \
       15

이 중에서 13을 제거한다고 가정하자. 13이 제거되면 2개의 자식 노드가 남게된다. 이 자리에는 다른 노드를 바꿔넣어서 트리 구조를 유지할 수 있도록 해야 한다. 따라서 해당 자리를 상속받을 노드를 찾아야 한다. 이 노드에 가장 어울리는 노드는 원래 노드보다는 크고 가장 작은 노드를 찾는 것이다. 이 노드가 어디있는지는 모르지만 아마 다음의 조건을 충족할 것이다.
* 제거할 노드의 부모의 우측 노드보다는, 제거할 노드 자신의 우측 가지에 존재할 것이다.
* 우측 가지에 접어든 이후에서는 각 레벨의 노드의 왼쪽을 따라 찾는다.
* 더 이상 왼쪽가지가 없는 위치가 상속노드가 된다.

상속자 노드의 정의에 따르면 자신의 키 값보다 바로 다음으로 큰 키 값이므로 만약 현재 노드의 우측 자식 노드가 없다면 그 부모가 상속자 노드가 된다. 하지만, 현재 노드의 우측 자식이 없는 경우는 위에서 별도로 처리하고 있으므로 생각하지 않아도 된다.

이렇게 찾은 상속자 노드에 만약 자식 노드가 있다면? 다행히 상속자 노드를 찾는 알고리듬에 따르면 상속자 노드는 오른쪽 자식 노드만 있어야 한다. 상속자 노드를 떼어내는 작업은 상속자 노드의 우측 노드를 상속자 노드의 부모노드에 붙여주는 작업을 한다.

이 기능은 TreeNode 클래스에 추가하도록 한다.

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        succ = self.rightChild.findMix()
    return succ

def findMin(self):
    if self.hasLeftChild():
        return self.leftChild.findMix()
    return self

그리고 상속자 노드를 떼어내기 위한 메소드도 정의하자.

def sliceOut(self):
    if self.hasRightChild():
        if self.isLeftChild():
            self.parent.leftChild = self.rightChild
        else:
            self.parent.rightChild = self.rightChild

자식 노드가 없는 경우는 None이 할당되어 있을 것이므로 따로 생각하지 않아도 된다. 이제 양쪽 자식 노드가 다 존재하는 노드를 트리에서 제거하는 코드는 다음과 같이 된다.

    elif currentNode.hasBothChildren():
        succ = self.findSuccessor()
        succ.sliceOut()
        self.key = succ.key
        self.payload = succ.payload

간단해졌다. 키와 값만 변경하면 트리 구조를 다시 손댈 필요가 없다.

아래는 전체 코드이다.

  • SoonHyung Jung

    sliceOut 맞나요?findMin했을때 우측 자식이 없으면 오류가 뜨는데..

    • 작은 값은 왼쪽으로 가기 때문에, findMin은 우측 자식을 보지 않습니다. sliceOut에서도 마찬가지로 우측 노드의 attribute를 참조하는 일은 없기 때문에 오류가 안날 것 같은데요…