Binary Search Trees

shin·2022년 7월 7일

Python DataStructure & Algorithm

목록 보기

6/16

1. Binary Search Trees

1) 이진 탐색 트리 특징

모든 노드에 대해서,
left subtree에 있는 데이터는 모두 현재 node의 값보다 작고
right subtree에 있는 데이터는 모두 현재 node의 값보다 큼
이때, 중복되는 데이터 원소는 없는 것으로 가정

2) 이진 탐색 트리의 추상적 자료구조

데이터 표현 : 각 노드는 (key, value)의 쌍으로 표현
키를 이용해서 검색이 가능하고, 보다 복잡한 data record로 확장 가능

2. inorder, min, max 연산

inorder() : 키 순서대로 데이터 원소를 나열
min(), max() : 최소 키, 최대 키를 가지는 원소 탐색

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) # node들의 리스트를 생성
        if self.right:
            traversal += self.right.inorder()
        return traversal
        
    # left에 가장 작은 값이 있기 때문에 왼쪽으로만 내려가면 최소 값을 찾을 수 있음
    def min(self):
        if self.left: 
            return self.left.min()
        else:
            return self
           
    # right에 가장 큰 값이 있기 때문에 오른쪽으로 내려감
    def max(self):
        if self.right: 
            return self.right.max()
        else:
            return self
            

class BinSearchTree:

    def __init__(self): 
        self.root = None # 빈 트리로 초기화
        
    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []
            
    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

3. lookup 연산

lookup(key) : 특정 원소 검색
찾은 노드와 찾은 노드의 부모 노드 리턴

class Node:
	... 생략 ...
    def lookup(self, key, parent = None): # parent node는 없으면 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
                
class BinSearchTree:
    ... 생략 ...
    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None

4. insert 연산

insert(key, data) : 트리에 주어진 데이터 원소 추가

class Node:
	... 생략 ...
    def insert(self, key, data):
        if key < self.key: # 삽입하려는 키 값이 더 작다면 왼쪽 서브트리 확인
            if self.left:
                return self.left.insert(key, data)
            else: # 왼쪽에 노드가 없다면 그 자리에 바로 삽입
                self.left = Node(key, data)
        elif key > self.key: # 삽입하려는 키 값이 더 크다면 오른쪽 서브트리 확인
            if self.right:
                return self.right.insert(key, data)
            else: # 오른쪽에 노드가 없다면 그 자리에 바로 삽입
                self.right = Node(key, data)
        else:
            raise KeyError('Key %s already exists.' % key) # 중복된 값은 삽입할 수 없음 - 예외 발생
            
class BinSearchTree:
    ... 생략 ...
    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)

5. remove 연산

remove(key) : 특정 원소를 트리로부터 삭제
- 키를 이용해서 노드를 찾음
- 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리해야 하기 때문에, 찾은 노드의 부모 노드도 알고 있어야 함
삭제되는 노드가 left node인 경우
: 그 노드를 없애고 부모 노드의 링크를 조정
child를 하나만 가지고 있는 경우
: 삭제되는 노드 자리에 그 자식 노드를 대시 배치하고 부모 노드의 링크를 조정
left와 right child를 모두 갖고 있는 경우
: 삭제되는 노드보다 바로 다음으로 큰 키를 갖는 노드를 찾아서 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제함
삭제되는 노드가 root node인 경우 :
- 대신 들어오는 자식이 이진 트리의 새로운 root가 됨
- 삭제되는 노드 오른쪽 자식의 왼쪽 서브 트리에서 가장 작은 값을 갖는 노드를 찾으면, 삭제되는 노드 바로 다음으로 큰 키를 갖는 Successor 노드를 찾을 수 있음
- Successor를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제하고, 부모 노드의 왼쪽 링크를 조정
- 삭제되는 노드 오른쪽 자식의 왼쪽 서브 트리가 없는 경우
- Successor의 parent는 삭제되는 노드와 같은 노드이기 때문에, Successor를 대신 배치하고 부모 노드의 오른쪽 링크를 조정

class Node:
	... 생략 ...
    def countChildren(self): # child node 개수 카운트
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count
            
            
    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 is parent.left:
                        parent.left = None
                    else:
                        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 != None:
                    child = node.left
                else:
                    child = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if node == parent.left:
                        parent.left = child
                    else:
                        parent.right = child
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = child
            # 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 == parent.left:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
            return True
        else:
            return False
    
class BinSearchTree:
    ... 생략 ...
    def remove(self, key): # key를 입력으로 받음
        node, parent = self.lookup(key)
        if node:
            return True # 삭제한 경우
        else:
            return False # 해당 키의 노드가 없는 경우