[Algorithm] 이진 탐색 트리(BST)_TIL Day3-6

이진 탐색 트리

이진 탐색 트리란?

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

- 이진 탐색 알고리즘과 비슷함
(이진 탐색 알고리즘 : 이미 정렬된 선형 배열을 대상으로 절반씩 잘라가면서 찾고자 하는 원소를 탐색)

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

 

이진 탐색 트리 삽입 연산 구현해 보기

 - 연산의 정의

• insert(key, data) - 트리에 주어진 데이터 원소를 추가
• remove(key) - 특정 원소를 트리로부터 삭제
• lookup(key - 특정 원소를 검색 (Ologn)
• inorder() - 키의 순서대로 데이터 원소를 나열
• min(), max() - 최대, 최소 원소를 탐색 

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 self.key == key:
            raise KeyError
        
        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)


    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

---

이진 탐색 트리 삭제 연산 구현해 보기

 - 대략적인 순서

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

 - 이진 탐색 트리 구조의 유지를 위해

• 삭제되는 노드가 말단(Leaf) 노드
  해당 노드만 삭제하면 됨
  부모 노드가 가지고 있던 링크 정보(왼쪽or 오른쪽 자식의 정보) 수정
• 자식 하나를 가지고 있는 노드
  삭제되는 노드 자리에 그 자식을 대신 배치
  부모 노드가 가지고 있던 링크 정보 조정
• 자식을 둘 가지고 있는 노드
  삭제되는 노드보다 바로 다음(큰) 키를 가지는 노드를 찾아 그 노드 자리에 대신 배치하고 배치한 노드의 원래 노드를 삭제

- 자식 갯수마다 로직이 달라지므로 먼저 자식의 수를 구함

 

class BinSearchTree:

    def __init__(self):
        self.root = 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 node == parent.left:
                        parent.left = None
                    if node == parent.right:
                        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:
                    direct = node.left
                else:
                    direct = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if node == parent.left:
                        parent.left = direct
                    else:
                        parent.right = direct
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = direct
            # 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 successor.key is parent.left.key:
                    parent.left = successor.right
                else:
                    parent.right = successor.right

            return True

        else:
            return False