BST 기초개념 및 구현실습

2019-04-19

그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork

Binary Search Tree(이진탐색트리) 개요

[탐색]

1) 선형탐색 : O(N)

2) 이진탐색 : O(log(n)) -> 엄청 빠르다

[BST의 응용]

BST는 딕셔너리를 구현하는데 많이 쓴다.

ex) 파이썬의 딕셔너리가 정확히 BST이다.

[딕셔너리의 구현]

1) BST 이용해서 구현

2) hasing (hash table) 이용해서 구현

[BST의 특징]

1) 모든 원소는 서로다른 ‘키’를 갖는다.

(키는 반드시 유니크해야하지만 아이템은 중복되도 무방)

2) 왼쪽 서브트리에 있는 모든키들은 루트의 키보다 작다.

3) 오른쪽 서브트리에 있는 모든키들은 루트의 키보다 크다.

(아래 그림참고)

4) 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색 트리이다.

[delete와 remove의 미묘한 차이점]

delete : 리스트가 있다고 하면, 특정 데이터를 뽑아서 아예 없애는것(사용자에게 반환x)
remove : 리스트가 있다고하면, 특정 데이터를 뽑아서 사용자에게 삭제를 할지 안할지 넘기는 것.(사용자에게 return해줌)

사용자에게 반환하냐 안하냐

따라서 엄밀히따지면 둘이 약간 다르다.

BST insert, search, remove 알고리즘

구현 시 고민해야할 사항

insert나 remove 오퍼레이션 후에도 이 트리가 여전히 BST인가?’
예를 들어서 내가 5을 집어 넣으려고 하면 어떤 알고리즘에 의해 넣어야 하는가

insert

BST가 유지될 수 있는 여건의 공노드에 삽입해준다.

search

remove

노드를 지울때는 3가지 상황 중에 하나이다.

1) 삭제할 노드가 리프노드일때

2) 자식노드가 하나일때

삭제가 되었을때 삭제된 놈의 자식노드를 삭제된 놈 부모노드와 이어줘야 한다.

3) 자식노드가 두개일때

지우는 놈 값을 대체해서 지운다.

좌측 자식노드들 중에 가장 큰 수 일경우

(cur를 좌측으로 한번 내려오고 우측으로 가장 쭉 내려보내면 된다)

우측 자식노드들 중에 가장 작은 수 일경우

(cur를 우측으로 한번 내려보내고 좌측으로 가장 쭉 내려보내면 된다)

삭제할 노드가 리프노드일때

자식노드가 하나일때

자식노드가 두개일때

1) 대체노드를 찾는다.

삭제하는 노드를 삭제해도 BST의 특성을 유지시켜야 하기 때문에

2) 대체노드와 위치교환

3) 대체노드를 지운다. 대체노드는 반드시 리프이거나 자식이 하나여야 한다.

6에서 3으로 내려와서 계속 오른족으로 쭉 내려가면 된다. 대체노드를 찾을때

remove()함수에서 루트 노드를 업데이트하는 이유는 결국에는 BST의 특성을 유지하기 위함이다.

위의 내용 파이썬 코드 구현

from binary_tree import TreeNode 
## 구현 시 바이너리 트리구조가 필요함. 
## 'Binary tree 기초개념 및 구현실습' 노트 참고!

class BST:
    def __init__(self):
        self.root=None

    def get_root(self):
        return self.root

    def preorder_traverse(self, cur, func, *args, **kwargs):
        if not cur:
            return

        func(cur, *args, **kwargs)
        self.preorder_traverse(cur.left, func, *args, **kwargs)
        self.preorder_traverse(cur.right, func, *args, **kwargs)

    ## 키값이 같을때는 배제하고 작성한 insert 함수임
    ## 원래는 키값 중복시 에러를 일으키거나 예외처리를 해줘야한다.
    def insert(self, data):
        new_node=TreeNode()
        new_node.data=data
        cur=self.root
        
        if not cur:
            self.root=new_node
            return
        
        ## 아직 데이터가 하나도 없으면
        ## 새로운 노드를 루트로 만든다
        while True:
            
            parent = cur
            
            if data < cur.data:
                
                cur = cur.left
                
                if not cur:
                    parent.left=new_node
                    return
            else:
                
                cur = cur.right
                
                if not cur:
                    parent.right=new_node
                    return 

    def search(self, target):
        cur=self.root
        while cur:
            if cur.data==target:
                return cur
            elif cur.data > target:
                cur=cur.left
            elif cur.data < target:
                cur=cur.right
        return cur

    def __remove_recursion(self, cur, target):
        ## recursion은 기저조건이 필요한데 
        ## if not cur가 기저조건이다.
        if not cur: 
            return None, None
        
        ## 타겟이 현재 커렌트의 데이터보다 크냐
        elif target < cur.data:
            cur.left, rem_node = self.__remove_recursion(cur.left, target)
            
        elif target > cur.data:
            cur.right, rem_node = self.__remove_recursion(cur.right, target)
            ## 인자로 커런트의 오른쪽이 들어간다. 타겟은 9로 들어간다.
        
        ## 타겟과 현재위치가 같을때도 기저조건이라고 할 수 있다.
        else:
            if not cur.left and not cur.right:
                rem_node=cur
                cur=None
                
            elif not cur.right:
                rem_node=cur
                cur=cur.left
                
            elif not cur.left:
                rem_node=cur
                cur=cur.right
            
            ## 자식노드가 두개일때
            else:
                replace=cur.left
                
                while replace.right:
                    replace = replace.right
                    
                cur.data, replace.data = replace.data, cur.data
                cur.left, rem_node = self.__remove_recursion(cur.left, replace.data)
                
        return cur, rem_node

    def remove(self, target):
        self.root, removed_node=self.__remove_recursion(self.root, target)
        if removed_node:
            removed_node.left=removed_node.right=None
        return removed_node
    
bst=BST()

insert

bst.insert(6)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(5)
bst.insert(8)
bst.insert(10)
bst.insert(9)
bst.insert(11)

f=lambda x: print(x.data, end='  ')

bst.preorder_traverse(bst.get_root(), f)

6  3  2  4  5  8  10  9  11

res=bst.search(8)
if res:
    print('searched data : {}'.format(res.data))
else:
    print('search failed')

searched data : 8

delete

#지울 노드가 리프 노드일 때
#bst.remove(9)
#자식 노드가 하나일 때
#bst.remove(8)
#자식 노드가 둘일 때
bst.remove(6)
bst.preorder_traverse(bst.get_root(), f)

data 6 is deleted
5  3  2  4  8  10  9  11  

 Binary tree 기초개념 및 구현실습 B-tree 기초개념 