20강/21강: 이진 탐색 트리(Binary Search Trees) (1) / (2)

강의

"이진 탐색 트리"는 left subtree의 모든 값이 root node의 값보다 작고 right subtree의 모든 값이 root node의 값보다 큰 이진트리 입니다. 

이때, 중복되는 데이터는 없다고 가정합니다.

 

이진 탐색 트리는 데이터 검색에 이용할 수 있습니다.

배열을 이용한 이진 탐색과 다르게 원소의 추가와 삭제가 용이하지만 공간 소요가 크다는 단점도 있습니다.

 

노드를 (key, value) 쌍으로 표현합니다.

 

균형이 없는 이진 탐색 트리는 효율적이지 않기 때문에 이진 탐색을 사용하는 것이 낫습니다.

 

 

연산

• insert(key, data) : 원소 추가
• remove(key) : 원소 삭제
• lookup(key) : 원소 검색
• inorder() : key의 순서대로 원소 나열

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    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 inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

• min(), max() : 최소 key, 최대 key를 가지는 원소 탐색

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None
        
    
    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self
            
    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self
         
         
class BinSearchTree:

    def __init__(self):
        self.root = None
        
        
    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None
            
            
    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

 

 

20강 실습: 이진 탐색 트리의 원소 삽입 연산 구현

⭐ 알맞은 크기 비교와 마지막 노드가 없을 때까지 재귀로 구현하는 문제!

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 is key:     # 중복 제거
            raise KeyError
            
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        
        else:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)


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)

 

 

21강 실습: 이진 탐색 트리에서 노드의 삭제 연산 구현

⭐ child node의 수에 따라 경우를 나누어 구현하는 문제!

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    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


    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

    def __init__(self):
        self.root = None


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


    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:
                    direct = node.left
                else:
                    direct = node.right
                    
                if parent:
                    if node == parent.left:
                        parent.left = direct
                    else:
                        parent.right = direct
                else:
                    self.root = direct
            
            else:   # 자식을 모두 가지고 있는 경우
                parent = node
                successor = node.right
                
                while successor.left:
                    parent = successor
                    successor = successor.left
                
                node.key = successor.key
                node.data = successor.data
                
                if successor.key is parent.left.key:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                    
            return True

        else:
            return False