[Programmers] 14. 기본 자료구조: 트리 (Tree) (3): 이진 트리의 응용 (1): 이진 탐색 트리

illstandtall·2021년 4월 29일

programmers python 이진 탐색 트리 이진 트리 자료구조 트리

Programmers dev course

목록 보기

15/34

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

이진 트리의 응용 1

이진 탐색 트리 (Binary Search Tree)

모든 노드에 대해서 아래의 성질을 만족합니다.
왼쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 작고,
오른쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 큽니다.
중복 데이터는 없는 것으로 가정합니다. (구현하기 나름)
트리의 재귀적인 성질을 이용하여 연산을 수행합니다.

배열을 이용한 이진 탐색과 이진 탐색 트리 비교

	배열의 이진 탐색	이진 탐색 트리
장점	공간의 소요가 적다.	데이터 원소의 추가/삭제가 용이하다.
단점	데이터 원소의 추가/삭제 시 배열을 밀어야 한다.	공간 소요가 크다.
평균 시간복잡도	$O(logn)$	$O(logn)$

이진 탐색 트리의 연산

insert(key, data): 주어진 data 원소를 key값을 이용해 적당한 위치에 추가합니다.
remove(key): 특정 key값을 가지는 원소를 트리에서 삭제합니다.
- key를 이용해 노드를 찾습니다.
  - key를 가진 노드가 없을 때
    - 삭제할 것도 없습니다.
  - key를 가진 노드가 있을 때
    - 노드를 삭제하고 이진탐색 트리의 성질을 만족하도록 트리의 구조를 조정합니다.
    - 말단 노드인 경우:
      - 단순히 노드를 삭제하고, 부모 노드의 링크만 조정합니다.
    - 자식 노드를 하나 가지고 있는 경우
      - 노드를 삭제하고 그 자리에 자식 노드를 배치합니다. 그리고 부모 노드의 링크 조정
    - 자식 노드를 둘 가지고 있는 경우
      - 삭제되는 노드보다 바로 다음 큰 키를 가진 노드를 찾아 그 자리에 배치합니다.
lookup(key): key값을 가진 원소를 검색합니다.
inorder(): key의 순서대로 데이터 원소를 나열합니다.
min(): 최소 key값을 가진 노드를 반환합니다.
max(): 최소 key값을 가진 노드를 반환합니다.

이진 탐색 트리의 연산 구현 1. insert()

# Node.insert():
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)


# BinSearchTree.insert():
def insert(self, key, data):
    if self.root:
        self.root.insert(key, data)
    else:
        self.root = Node(key, data)
#

이진 탐색 트리의 연산 구현 2. remove()

# BinSearchTree.remove

def remove(self, key):
    node, parent = self.lookup(key)
    if node:
        nChildren = node.countChildren()
        if nChildren == 0:
            if parent:
                if node == parent.left:
                    parent.left = None
                else:
                    parent.right = None
            else:
                self.root = None
        elif nChildren == 1:
            if node.left:
                tmp = node.left
            else:
                tmp = node.right
            if parent:
                if node == parent.left:
                    parent.left = tmp
                else:
                    parent.right = tmp
            else:
                self.root = tmp
        else:
            parent = node
            successor = node.right
            while successor.left:
                parent = successor
                successor = successor.left
            node.key = successor.key
            node.data = successor.data
            if successor == parent.left:
                parent.left = successor.right
            else:
                parent.right = successor.right
        return True

    else:
        return False

이진 탐색 트리의 연산 구현 3. lookup()

# Node.lookup()
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


# BinSearchTree.lookup()
def lookup(self, key):
    if self.root:
        return self.root.lookup(key)
    else:
        return None, None

이진 탐색 트리의 연산 구현 4. inorder()

# Node.inorder()
def inorder(self):
    traversal = []
    if self.left:
        traversal += self.left.inorder()
    traversal.append(self)
    if self.right:
        traversal += self.right.inorder()
    return traversal


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

이진 탐색 트리의 연산 구현 5. min()

# Node.min()
def min(self):
    if self.left:
        return self.self.min()
    else:
        return self
        

# BinSearchTree.min()
def min(self):
    if self.root:
        return self.root.min()
    else:
        return None

이진 탐색 트리의 연산 구현 6. max()

# Node.max()
def max(self):
    if self.right:
        return self.self.max()
    else:
        return self
        
        
# BinSearchTree.max()
def max(self):
    if self.root:
        return self.root.max()
    else:
        return None