콘텐츠로 건너뛰기
Home » 이진탐색트리 (Binary Search Tree) 구현하기 – python

이진탐색트리 (Binary Search Tree) 구현하기 – python

Binary Search Tree

이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.
이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.

이진 탐색트리는 이진트리와 같이 부모와 두 개의 자식으로 연결되며, 키와 값을 갖는 노드의 연결로 구성된다. 이러한 구조는 다음과 같은 특징을 갖는다.

  • 각 노드는 키와 값을 가지며, 노드의 키는 고유해야 한다.
  • 노드의 왼쪽 서브트리는 그 노드의 키보다 작은 키를 가진다.
  • 노드의 오른쪽 서브트리는 그 노드의 키보다 큰 키를 가진다.

경우에 따라서는 키와 값이 일치한다고 가정하는 구현도 있을 수 있다.
 

트리 맵 클래스 디자인

이진 탐색 트리는 다음과 같은 기능들을 제공해야 할 것이다. 이 글에서는 이러한 기능을 어떻게 구현할 것인지 알아보고 실제로 구현까지 해 볼 것이다. 트리는 실질적으로 노드들의 연결로 구성되는 자료 구조이나, 이를 둘러싼 클래스를 만들고, 해당 클래스에서 값의 입/출력을 수행하는 인터페이스를 제공하는 것으로 한다. 따라서 우리의 트리 클래스는 다음과 같은 기능을 제공해야 한다.

  1. 새로운, 비어있는 이진 트리 맵을 생성한다. 이는 클래스의 인스턴스를 생성하는 것이다.
  2. 키, 값 쌍의 데이터를 받아서 트리에 추가한다. put(key, value)의 형태로 메소드를 만들 것이다.
  3. 키를 이용해서 해당 키에 연결된 값을 얻을 수 있다. get(key)를 구현할 것이다.
  4. 특정 키를 주고, 해당 키를 트리 내에서 탐색한다. contains(key)의 메소드를 구현한다.
  5. 특정 키를 주고, 해당 키를 트리 내에서 제거한다. delete(key) 의 메소드를 구현한다.

파이썬의 여러 문법에서 사전과 같이 map[key] 를 이용해서 키-값 쌍을 액세스하거나, len() 함수를 이용해서 길이를 구하고, in 연산자를 이용해서 특정 키가 있는지를 조사할 수 있게 만든다면 보다 실용적인 자료 구조를 만들 수 있을 것이다. 이러한 문법으로 액세스할 수 있도록 하는 방법에 대해서도 끝부분에서 좀 더 살펴볼 예정이다.

트리 노드 클래스 디자인

트리는 실제로 각 노드들의 연결로 구성된다. 노드는 맵과는 별개의 클래스로 만들 것이며, 다음의 특징을 가질 것이다.

  1. 키와 값 속성을 갖는다.
  2. 자신의 부모 노드에 대한 참조를 갖는다.
  3. 두 개의 자식 노드에 대한 참조를 갖는다. 왼쪽은 자신의 키보다 작은 키를 갖는 노드들이, 오른쪽에는 자신의 키보다 큰 키값을 갖는 노드들이 연결되어 서브 트리를 구성한다.

상호 참조

두 개의 노드가 부모-자식의 관계를 맺는 경우에 다음의 내용을 주의해야 한다. 부모노드는 자식노드에 대해서 왼쪽 혹은 오른쪽 자식이라는 속성으로 참조하게 된다. 그리고 그 반대방향에서 자식노드는 부모노드를 부모라는 속성으로 참조한다. 이 때 두 개의 객체 인스턴스가 서로를 참조한다. 이 경우에 참조 순환이 발생하며, 메모리 누수가 발생하기 쉽다. 이를 해결하기 위해서는 다음과 같은 전략을 취할 수 있다.

  1. 부모-자식 관계가 끊어지거나 변경되어야 하는 경우에, 해당 작업이 수행되는 시점에서 부모 노드와 자식 노드에 대한 참조를 모두 가지고 있어야 한다. 그리하여 자식노드의 부모를 None 으로 변경하고, 부모노드의 자식을 None으로 변경하여 상호간의 참조를 양방향 모두에서 제거해야 한다. 단순히 parentNode.leftChild = newNode 이라고 하는 경우, 끊어져 나간 이전 자식 노드는 계속해서 부모 노드에 대한 참조를 유지하고, 이는 메모리 누수로 이어진다.
  2. 혹은 부모 속성에 대해서는 약한 참조를 이용하는 방법이 있다. 약한 참조는 객체를 참조는 하되, 메모리에 유지시키는 역할을 하지 않는다. 이 경우에는 자식 노드를 쉽게 버릴 수 있으며, 자식은 부모에 대해서 직접적으로 참조하지 않으므로 이전에 자식이었던 노드 객체에 의해서 메모리 누수가 발생하는 것을 막을 수 있다.

어느쪽이든 간에 좀 성가시기는 한데, 이 글에서는 부모 자식 관계를 맺는 것을 메소드 내부에서만 제어한다고 가정하고 주의깊게 상호간의 참조를 관리하는 방식을 따르도록 하겠다.
 

노드의 추가 동작

트리 내부에서 특정 노드를 제거하려 할 때,  제거되는 노드가 트리 중간에 있고, 양쪽 자식을 모두 가지고 있는 경우 처리가 좀 복잡하다. 이 부분에 대한 자세한 설명은 뒤에서 할 것인데 이를 위해서 몇 가지 추가 메소드를 구현해줄 필요가 있다.

  • 자신이 부모 노드의 왼쪽 자식인지, 오른쪽 자식인지를 알아낼 방법이 있어야 한다. 자신을 제거하는 경우, 부모와 자신의 연결을 부모와 None 혹은 자신의 자식 노드와의 연결로 교체할 필요가 있기 때문이다.
  • 노드를 제거하려는 경우의 처리가 자신이 루트인지, 종단노드(Leaf)인지, 자식을 하나만 가지는지, 두 개 자식 노드가 모두 있는지 등에 따라 처리 방식이 다르므로 이러한 정보를 확인해야 한다.
  • 노드 삭제와 관련하여 몇 가지 특별한 메소드들이 필요하다.
    • 자신의 자식 노드 중에서 최소 노드를 찾는 작업
    • 자신을 제거할 때, 자신의 자리를 대체할 자식 노드를 찾는 작업
    • 자신이 속한 트리 구조 내에서 자기를 떼네는 작업 (여기에는 몇 가지 제약을 걸어서 구현을 쉽게 만들 것이다.)

기본적인 노드 클래스 구현

아래와 같이 기본적인 속성들을 구현해준다. 간단한 내용들이다.

class TreeNode:
  def __init__(self, key, val):
    self.key = key
    self.value = val
    self._leftChild = None
    self._rightChild = None
    self.parent = None

자식노드의 액세스 방식을 프로퍼티를 사용하기

양쪽 자식 노드 이름에 _를 붙인 것은 이를 별도의 프로퍼티로 설정하기 위해서이다. 프로퍼티를 이용하면 속성의 접근과 업데이트를 메소드를 getter, setter 메소드를 통해서 간접적으로 처리하게 되는데, 이 때 자식 노드와 자신의 부모/자식 관계를 쉽게 정리할 수 있다.

class TreeNode:
  ...
  @property
  def leftChild(self):
    return self._leftChild
  @leftChild.setter
  def leftChild(self, value):
    # 현재 왼쪽 자식 노드가 있다면, 그 부모 속성을 제거한다.
    if self._leftChild:
      self._leftChild.parent = None
    # 새 노드가 None이 아니라면 새 노드의 부모를 자신으로 설정해준다.
    if value:
      value.parent = self
    self._leftChild = value

실제로 다음과 같이 테스트 해 볼 수 있다.

> p = TreeNode(4, 4)
> l = TreeNode(2, 2)
> p.leftChild = l
> l.parent.value
4
> l2 = TreeNode(1, 1)
> p.leftChild = l2
> l.parent
# None
> l2.parent.value
4

동일한 방식으로 오른쪽 노드에 대한 처리도 해주도록 하자. 그리고 다음은 그외 몇 가지 노드의 속성을 확인하는 처리이다.

노드의 속성 확인용 메소드 구현

노드의 속성을 확인한다는 것은 앞에서 언급한, 자신이 루트인지, 종단노드인지, 자식을 가지고 있는지 등을 확인하는 것이다.

class TreeNode:
  ...
  def isRoot(self):
    '''자신이 루트인지 판단. 부모가 없으면 루트이다.'''
    return parent is None
  def isLeaf(self):
    '''자신이 종단노드인지 확인'''
    return self._leftChild is None and self._rightChild is 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 hasLeftChild(self):
    return self._leftChild is not None
  def hasRightChild(self):
    return self._rightChild is not None
  def hasBothChildren(self):
    return self._rightChild is not None and self._leftChild is not None
  def hasAnyChild(self):
    return not self.isLeaf()

트리 클래스 기초 구현

트리 클래스는 트리를 시작하는 루트 노드와 트리의 크기를 담고 있는 속성값 하나를 기본적으로 정의해준다. 따라서 빈 트리를 생성할 수 있다.

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

노드 추가

이제 키와 값을 받아서 새로운 노드를 추가하는 로직을 구현해보자. 먼저 트리에 루트 노드가 없다면, 넘겨진 값을 이용해서 노드를 만들고 이를 루트 노드로 삼는다. 만약 루트 노드가 만들어져 있다면 키를 비교하여 신규 노드를 집어넣을 곳을 찾아야 할 것이다.

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)

루트가 이미 존재하는 경우에는 특정한 노드의 하위로 신규 노드를 추가해야 한다. 이 부분을 좀 깔끔하게 만들려고 별도의 메소드로 분리했다. 해당 메소드인 __put()put()내에서만 호출될 것이기 때문에 언더스코어를 두 개 붙여서 이름 지었다. 이 메소드는 이전에 재귀 방식으로 돌아가도록 작성하였으나, 루프를 도는 방식으로 변경했다. 이 메소드에서는 타깃이 되는 노드의 키와 새로 주어진 키를 비교한다. 이진 탐색과 같은 방식으로 새로운 키가 작으면 타깃노드의 왼쪽으로, 크면 오른쪽으로 달려야 하는데, 타깃 노드가 해당 방향의 자식 노드를 이미 가지고 있다면, 해당 자식 노드를 타깃으로 변경해서 같은 검사를 반복 수행한다.
또한 정확한 트리의 크기는 노드를 추가/제거하는 시점마다 업데이트하여 관리해야 한다.

def __put(self, key, val, currentNode):
  targetNode = currentNode
  while True:
    if key < targetNode.key:
      if not targetNode.hasLeftChild():
        targetNode.leftChild = TreeNode(key, value)
        break
      else:
        targetNode = targetNode.leftChild
    else:
      if not targetNode.hasRightChild():
        targetNode.rightChild = TreeNode(key, value)
        break
      else:
        targetNode = targetNode.rightChild
  self.length += 1

이제 키를 통해 값을 받아오는 get 메소드를 구현해본다. 이진 탐색 트리의 알고리듬을 그대로 따르면 된다. 역시 이진 탐색의 알고리듬을 그대로 사용하므로 실질적으로 put 메소드와 동일하다.  역시 구성 자체를 동일하게 맞추었다. 참고로 이전 버전에서는 __get() 메소드 역시 재귀적으로 작성하였으나 루프를 도는 방식으로 변경하였다.

def get(self, key):
  if self.root is None:
    return None
  res = self.__get(key, self.root)
  if res:
    return res.value
  return None
def __get(self, key, currentNode):
  targetNode = currentNode
  while True:
    if key == targetNode.key:
      return targetNode
    elif key < targetNode.key:
      if targetNode.hasLeftChild():
        targetNode = targetNode.leftChild
      else:
        return None
    else:
      if targetNode.hasRightChild():
        targetNode = targetNode.rightChild
      else:
        return None

여기까지 기본적인 키, 값을 트리맵에 삽입하고, 키를 통해서 값을 액세스하는 방법까지 살펴보았다.  특정한 키를 주고, 해당 키가 트리 내에 포함되어 있나하는 여부 역시 get() 메소드를 이용해서 해당 키에 대응하는 노드를 찾고, 노드가 있으면 True를, 그렇지 않으면 False를 리턴하도록 하면 된다.  이번에는 트리 내에서 키를 삭제하는 방법에 대해서 살펴보도록 하자.

키를 삭제하기

트리 내에서 키를 삭제하는 절차는 다음과 같다.

  1. 먼저 삭제하고자 하는 노드의 키를 전달한다.
  2. 주어진 키에 해당하는 노드를 찾는다. 만약 찾지 못했다면, 존재하지 않는 키를 삭제하려는 시도이다. 예외를 던지거나 그냥 리턴할 수 있는데, 어떻게 처리할지는 구현자의 선택이다. (여기서는 예외를 던지도록 한다.)
  3. 찾은 노드를 제거한다.

이렇게 하면 간단해보이지만, 사실 노드를 삭제하는 것은 삭제될 노드의 위치나 상황에 따라서 달라진다. 예를 들어 종단 노드(Leaf)의 경우라면 해당 노드를 제거하더라도, 자식 노드가 없기 때문에 제법 간단히 제거될 수 있다. 그런데 자식 노드가 있다면, 즉 트리 그래프의 중간 지점에 있는 노드를 제거하는 것은 간단한 일이 아니다. 왜냐하면 해당 노드를 기점으로 부모 노드와 그 자식 노드(들)이 연결된 상태로 유지되어야 하며, 그 모양 자체가 이진 탐색 트리의 규칙을 지켜야 하기 때문이다.
따라서 케이스는 다음과 같이 달라질 수 있다.

  1. 길이가 1인 트리 내에서 루트 노드를 제거하는 경우
  2. 종단 노드를 제거하는 경우
  3. 좌/우 중 한쪽에만 자식 노드를 달고 있는 노드를 제거하는 경우
  4. 양쪽에 자식 노드를 달고 있는 노드를 제거해야 하는 경우

루트 노드 제거

가장 처리하기 쉬운 케이스는 길이가 1인 트리(즉, 루트 노드 하나만 붙어 있는 상태)에서 루트 노드를 제거하는 경우이다. 이 때의 루트 노드는 자식노드나 부모노드가 없는 특별한 케이스이기 때문에 이 경우를 따로 분리하여 처리하는 것이 수월하다. 왜냐하면 이를 따로 처리하면 다른 케이스들에서는 항상 부모노드가 있다는 가정을 할 수 있기 때문이다.
 
키를 주고 노드를 제거하는 메소드를 delete() 라 할 때, 루트 노드를 제거하는 케이스는 다음과 같이 정의할 수 있다.

def delete(self, key):
  if self.length == 1 and self.root.key == key:
    self.root = None
    self.length = 0
  node_to_delete = self.get(key)
  if not node_to_delete:
    raise KeyError("There is no node in the tree.")
  ...

본 케이스의 경우에는 루트 노드를 None  으로 대체하고 크기를 0으로 리셋하는 것으로 처리가 가능하다. 만약 이 케이스가 아니라면 제거해야할 노드를 트리 내에서 찾아야 할 것이다. (이는 get() 을 사용한다고 했다.) 그리고 찾고자 하는 키의 노드가 없다면 예외를 일으킨다.
이제 다음 케이스들에 대해서 생각해보자.

종단 노드를 제거하는 경우

종단노드를 제거하는 경우는 그 다음으로 간단하다.  시각화해보자면 다음과 같은 경우가 있을 것이다.  사실 이진 트리는 “다음 노드”가 두 개인 이중 연결리스트와 비슷하기 때문에, 자신의 “앞노드”즉 자신의 부모노드로부터 자기로 이어지는 연결을 끊어주면 된다.

           ...                   ...
           24                     24
         /   \                   /  \
제거 >>> 20    28                20   28 <<< 제거

위와 같은 두 경우가 있다. 20을 제거하는 경우는 24의 leftChild 속성을, 28을 제거하는 경우에는 24의 rightChild 속성을 None 으로 대체하면 된다. 물론 이 때 제거되는 노드들의 parent 속성들도 함께 제거해야 순환참조에 의한 고리가 끊어지게 되는데, 이 처리는 자식 노드에 대한 접근을 프로퍼티를 통해서 수행하면서 처리되도록 해두었으므로 여기서는 노드를 None으로 교체하는 것에 집중하면 된다.
아, 그리고 루트노드가 자식이 없는 경우는 이미 앞에서 처리했으므로, 이 케이스에서 제거될 노드(node_to_delete)는 무조건 부모노드가 존재한다고 볼 수 있다.

def delete(self, key):
  ...
  if node_to_delete.isLeaf():
    ## 왼쪽 자식이었으면 부모의 왼쪽 자식 노드를 제거
    if node_to_delete.isLeftChild():
      node_to_delete.parent.leftChild = None
    ## 그 반대
    else:
      node_to_delete.parent.rightChild = None

자식을 1개만 가지는 노드를 제거하는 경우

자식을 왼쪽 혹은 오른쪽 1개만 가지는 노드를 제거하는 경우는 종단 노드의 경우와 비슷하다. 다만 해당 노드가 가지고 있는 자식이 트리에서 끊어져 나가는 불상사를 막기 위해서 해당 자식 노드를 다시 자신의 부모 노드에 이어 붙이는 작업을 추가로 수행해야 한다.
참고로 코드 상에서는 두 개의 자식 노드를 가지는 경우를 먼저 판별하는 것이 좋다. 그렇지 않다면 “왼쪽 자식 노드가 있고 오른쪽 자식 노드는 없는 경우”와 “오른쪽 자식은 있고 왼쪽은 없는 경우”를 각각 찾아야 하기 때문이다.
 

def delete(self, key)
  ...
  if node_to_delete.isLeaf():
    ## 종단노드처리
    ...
  elif node_to_delete.hasBothChildren():
    ## 두 자식 노드를 갖는 경우 처리
    pass
  elif node_to_delete.leftChild:
     ## 왼쪽 자식만 있는 경우
  else:
     ## 오른쪽 자식만 있는 경우

이 경우에 처리해야 하는 상황은 총 4가지가 된다고 생각할 수 있는데,

  • 자신은 부모의 왼쪽 노드이면서 왼쪽 자식을 갖는 경우
  • 자신은 부모의 왼쪽 노드이면서 오른쪽 자식을 갖는 경우
  • 자신의 부모의 오른쪽 노드이면서 왼쪽 자식을 갖는 경우
  • 자신은 부모의 오른쪽 노드이면서 왼쪽 자식을 갖는 경우

사실은 다음의 세 가지로 봐야 한다.  위의 케이스에서는 삭제될 노드가 부모노드가 없는 경우를 고려하지 않았다.

  • 루트노드이면서 한쪽 자식만 갖는 경우
  • 부모노드의 왼쪽 자식이면서 한쪽 자식만 갖는 경우
  • 부모노드의 오른쪽 자식이면서 한쪽 자식만 갖는 경우

그런데 어떻게 케이스를 줄였을까? 그것은 왼쪽 혹은 오른쪽 한쪽만 있는 자식 노드를 따로 참조할 수 있도록 이름을 붙여주면 되기 때문이다. 그런 다음 현재 노드와 자식 노드의 연결을 끊는다. 부모노드에 자식 노드를 연결할 때에는 자식노드의 방향은 고려할 필요가 없고, 오로지 삭제 대상 노드 자신이 부모의 어느쪽에 붙어있느냐만 중요하기 때문이다.
따라서 코드는 아래와 같이 정리된다.

  ...
  else:
    ## 한쪽 자식만 있는 경우이다.
    ## 자식과 제거될 노드의 연결을 끊는다.
    ## 그전에 자식 노드에 대한 참조를 별도로 유지한다.
    child = node_to_delete.leftChild \
            if node_to_delete.leftChild is not None else \
            node_to_delete.rightChild
    node_to_delete.leftChild = None
    node_to_delete.rightChild = None
    if node_to_delete.isRoot(): ## 만약 자기가 루트이면
      self.root = child
    elif node_to_delete.isLeftChild(): ## 이 이후부터는 부모가 존재하는 것이 보장된다.
      node_to_delete.parent.leftChild = child
    else:
      node_to_delete.parent.rightChild = child

다음으로 가장 복잡하다던 양쪽 자식을 모두 갖는 경우를 생각해보자.  아래 예시에서 노드 13을 제거한다고 생각해보자. 노드 13은 두 개의 자식을 모두 가지고 있다. 그렇다면 이 때 12와 18중 어느 자식이 13을 대체해야 할까? 그림상으로는 12가 맞는 것 같다. 왜냐하면 12는 자식이 없기 때문에 위로 올라와서 12의 오른쪽 자식으로 18이 붙으면 될 것 같기 때문이다. 하지만 12에 오른쪽 자식이 달려있다면 그때는?
 

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

해당 자리를 상속받을 노드를 찾아야 한다. 이는 13의 자식 노드가 아니라, 이 노드에 가장 어울리는 노드 여야 할 것이다. 이는 원래 노드보다는 크고 가장 작은 노드를 찾는 것이다. (반대로 원래 노드보다 작은 것 중에 가장 큰 노드 일 수도 있다.) 왜 그래야 할까? 원래의 노드보다 큰 것 중에서 가장 작은 노드라는 것은 결국 해당 노드는 자기보다 작은 서브 노드를 가지고 있지 않다는 의미이고, 최소한 이는 왼쪽 자식은 가지고 있지 않은 노드라는 뜻이기 때문에 처리하기가 조금 수월하기 때문이다.
따라서 제거될 노드의 위치를 상속받는 노드는 다음의 알고리듬으로 찾아야 한다.

  • 제거할 노드의 부모의 우측 노드보다는, 제거할 노드 자신의 우측 가지에 존재할 것이다.
  • 우측 가지에 접어든 이후에서는 각 레벨의 노드의 왼쪽을 따라 찾는다.
  • 더 이상 왼쪽가지가 없는 위치가 상속노드가 된다.

따라서 위 그림에서 13을 제거하는 경우, 그 위치를 이어 받을 노드는 14이다. 그리고 14가 13의 위치에 오더라도 이진 탐색 트리의 규칙을 여전이 잘 준수하게 된다.
상속자 노드의 정의에 따르면 자신의 키 값보다 바로 다음으로 큰 키 값이므로 만약 현재 노드의 우측 자식 노드가 없다면 그 부모가 상속자 노드가 된다. 하지만, 지금 상황에서는 현재 노드가 양쪽의 자식 노드를 모두 가지고 있는 상황까지 좁혀졌으므로 이는 생각하지 않아도 된다.
이렇게 찾은 상속자 노드는 종단 노드이거나 오른쪽 자식 노드만 있어야 한다. 상속자 노드를 떼어내는 작업은 상속자 노드의 우측 노드를 상속자 노드의 부모노드에 붙여주는 작업으로 대신할 수 있다. 이 기능은 TreeNode 클래스에 sliceOut() 메소드를 추가하여 구현한다. 그전에 먼저 상속자 노드를 찾는 메소드를 먼저 작성해보자.

def findSuccessor(self):
  succ = None
  if self.hasRightChild():
    succ = self.rightChild
    while succ.hasLeftChild():
      succ = succ.leftChild
  return succ

그리고 상속자노드에 대해 호출하여 이를 떼어낼 sliceOut이다.

def sliceOut(self):
  ## 현재 노드는 상속자이므로, 부모가 반드시 존재하고 왼쪽 자식은 없다.
  child = self.rightChild if self.hasRightChild() else None
  self.rightChild = None
  if self.isLeftChild():
    self.parent.leftChild = child
  else:
    self.parent.rightChild = child

이제 다시 트리의 delete로 돌아와서, 양쪽 노드를 모두 가질 때 어떻게 제거해야하는지를 구현해보자. 로직은 이렇다.

  1. 상속자 노드를 찾고
  2. 상속자 노드를 떼어낸 다음
  3. 제거해야 할 노드의 키와 값을 상속자 노드의 그것으로 변경해버린다.

떼어낼 노드를 떼어내고 그 자리에 상속자 노드를 다시 붙이는 것보다 이게 더 깔끔하다는 것이다. 코드 역시 깔끔하게 처리된다.

    elif node_to_delete.hasBothChildren():
        succ = self.findSuccessor()
        succ.sliceOut()
        self.key, self.value = succ.key, succ.value

그리고 노드를 떼어내는 작업을 완료했으면 length 값을 1만큼 감소시켜주는 것으로 마무리할 수 있다. 이제 delete() 메소드를 정리하면 다음과 같다.

def delete(self, key):
  if self.length == 1 and self.root.key == key:
    self.root = None
    self.length = 0
    return
  node_to_delete = self.get(key)
  if not node_to_delete:
    raise KeyError("There is no node in the tree.")
  if node_to_delete.isLeaf():
    ## 루트가 아닌 종단 노드의 경우
    if node_to_delete.isLeftChild():
      node_to_delete.parent.leftChild = None
    else:
      node_to_delete.parent.rightChild = None
  elif node_to_delete.hasBothChildren():
    ## 양쪽 자식을 모두 가지는 경우
    succ = self.findSuccessor()
    succ.sliceOut()
    self.key, self.value = succ.key, succ.value
  else:
    ## 한쪽 자식만 있는 경우이다.
    ## 자식과 제거될 노드의 연결을 끊는다.
    ## 그전에 자식 노드에 대한 참조를 별도로 유지한다.
    child = node_to_delete.leftChild \
            if node_to_delete.leftChild is not None else \
            node_to_delete.rightChild
    node_to_delete.leftChild = None
    node_to_delete.rightChild = None
    if node_to_delete.isRoot(): ## 만약 자기가 루트이면
      self.root = child
    elif node_to_delete.isLeftChild(): ## 이 이후부터는 부모가 존재하는 것이 보장된다.
      node_to_delete.parent.leftChild = child
    else:
      node_to_delete.parent.rightChild = child
  self.length -= 1

아래는 전체 코드이다.
 


class TreeNode:
'''TreeNode in Binary Search Tree'''
def __init__(self, key, val):
self.key = key
self.value = val
self._leftChild = None
self._rightChild = None
self.parent = None
@property
def leftChild(self):
return self._leftChild
@leftChild.setter
def leftChild(self, node):
if self._leftChild:
self._leftChild.parent = None
if node:
node.parent = self
self._leftChild = node
@property
def rightChild(self):
return self._rightChild
@rightChild.setter
def rightChild(self, node):
if self._rightChild:
self._rightChild.parent = None
if node:
node.parent = self
self._rightChild = node
def isRoot(self):
return not self.parent
def isLeaf(self):
return not (self.rightChild or self.leftChild)
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 hasAnyChildren(self):
return not self.isLeaf()
def hasBothChildren(self):
return self.hasLeftChild() and self.hasRightChild()
def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild
while succ.hasLeftChild():
succ = succ.leftChild
return succ
def sliceOut(self):
'''트리 내에서 현재 노드를 잘라낸다.
단, 이 동작은 successor가 되는 노드에만
한정되는 것으로 간주한다.
따라서, 현재노드는 왼쪽 자식이 없어야 한다'''
child = self.rightChild if self.hasRightChild() else None
self.rightChild = None
if self.isLeftChild():
self.parent.leftChild = child
elif self.isRightChild():
self.parent.rightChild = child
# !!! the successor node never has a left child.
def traverse(self):
# ! in-order traverse prints out an sotred list.
if self.hasLeftChild():
self.leftChild.traverse()
print(self.value)
if self.hasRightChild():
self.rightChild.traverse()
class BinarySearchTree:
def __init__(self):
self.root = None
self.length = 0
def put(self, key, val):
if self.root is not None:
self.__put(key, val, self.root)
else:
self.root = TreeNode(key, val)
self.length += 1
def __put(self, key, val, currentNode):
targetNode = currentNode
while True:
if key < targetNode.key:
if not targetNode.hasLeftChild():
targetNode.leftChild = TreeNode(key, val)
break
else:
targetNode = targetNode.leftChild
else:
if not targetNode.hasRightChild():
targetNode.rightChild = TreeNode(key, val)
break
else:
targetNode = targetNode.rightChild
self.length += 1
def get(self, key):
if self.root:
res = self.__get(key, self.root)
if res:
return res.value
return None
def __get(self, key, currentNode):
targetNode = currentNode
while True:
if targetNode.key == key:
return targetNode
elif key < currentNode.key:
if targetNode.hasLeftChild():
targetNode = targetNode.leftChild
else:
return None
else:
if targetNode.hasRightChild():
targetNode = targetNode.rightChild
else:
return None
def delete(self, key):
if self.length == 1 and self.root.key == key:
self.root = None
self.length = 0
return
node_to_delete = self.__get(key, self.root)
if not node_to_delete:
raise KeyError('There is no key in the tree.')
if node_to_delete.isLeaf():
if node_to_delete.isLeftChild():
node_to_delete.parent.leftChild = None
else:
node_to_delete.parent.rightChild = None
elif node_to_delete.hasBothChildren():
succ = node_to_delete.findSuccessor()
succ.sliceOut()
node_to_delete.key, node_to_delete.value = succ.key, succ.value
else:
child = node_to_delete.leftChild \
if node_to_delete.hasLeftChild() else\
node_to_delete.rightChild
node_to_delete.leftChild = None
node_to_delete.rightChild = None
if node_to_delete.isRoot():
self.root = child
elif node_to_delete.isLeftChild():
node_to_delete.parent.leftChild = child
else:
node_to_delete.parent.rightChild = child
self.length -= 1
def main():
b = BinarySearchTree()
ad = (17, 5, 25, 2, 11, 29, 38, 9, 16, 7, 8)
for i in ad:
b.put(i, i)
b.root.traverse()
print('remove 5')
b.delete(5)
b.root.traverse()
if __name__ == '__main__':
main()