개념

이진 탐색 트리 - 위키백과, 우리 모두의 백과사전

삽입과 탐색 과정은 비교적 간단하지만 삭제과정은 삭제한 노드를 다른 노드로 대체해야하기 때문에 복잡하다. 삭제과정만 정리한다.

삭제과정

삭제할 노드를 발견했다면 그 노드의 child노드를 확인한다. 자세한 코드는 아래의 delete 함수를 보자.

• Left, Right 둘다 존재할 경우 (가장 복잡함) : Right노드의 child노드들중에서 가장 왼쪽에 있는 child노드를 삭제노드로 대체시킨다. 삭제할 노드를 node, right노드의 가장 왼쪽 노드를 child, 그 child노드의 부모노드를 parent노드라고 하자.
  1. child의 left를 node의 left로 지정한다. node의 자리를 child로 대체하기 때문에 그 left노드들을 child의 left에 연결해주어야 한다.
  2. parnet가 node가 아니라면 (right의 left가 하나도 존재하지 않다면) 여기서 삭제과정이 끝난다. parent가 node가 아니라면 child의 right노드들을 parent의 left로 올려주어야 한다. child노드 하나만 때서 node쪽으로 올려야 하기 때문에 child에 붙어 있던 right를 parent의 left로 붙여주는 것이다.
• Left또는 Right노드 하나만 있는 경우 : 노드를 삭제하고 Left or Right노드를 삭제 노드로 대체하면 된다.
• 둘 다 없는 경우 : 그냥 삭제만 한다.

Python

• insert(data)
• find(data)
• delete(key)

class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

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

    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None

    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data <= node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node

    def find(self, key):
        return self._find_value(self.root, key)

    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)

    def delete(self, key):
        self.root, deleted = self._delete_value(self.root, key)
        return deleted

    def _delete_value(self, node, key):
        if node is None:
            return node, False

        deleted = False
        if key == node.data:
            deleted = True
            if node.left and node.right:
                """
                왼쪽, 오른쪽 둘다 있는 경우 : 

                오른쪽 노드의 가장 왼쪽에 있는 노드로 대체시킨다.
                """
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            elif node.left or node.right:
                node = node.left or node.right
            else:
                node = None
        elif key < node.data:
            node.left, deleted = self._delete_value(node.left, key)
        else:
            node.right, deleted = self._delete_value(node.right, key)
        return node, deleted

bst = BinarySearchTree()

print(bst.insert(1))
print(bst.insert(2))
print(bst.insert(3))
print(bst.insert(4))
print()
print(bst.find(0))
print(bst.find(2))
print(bst.find(4))
print(bst.find(6))
print()
print(bst.delete(0))
print(bst.delete(2))
print(bst.delete(4))
print(bst.delete(6))

C

Binary Search Tree의 Data Type을 일반화했다.

doxygen형식으로 주석을 상세하게 작성하였다.

• insert
• search