[자료구조] Binary Search Tree(BST, 이진탐색트리) 정의와 python 구현

[자료구조] Binary Search Tree(BST, 이진 탐색 트리) 정의와 python 구현

 

 

살펴볼 주요 개념:

- Binary Search Tree의 정의

- Binary Search Tree 구현 방법

 

1. Binary Search Tree의 정의

이진탐색 트리는 탐색에 효율적인 트리이다.

이진트리의 규칙은 다음과 같다.

 

---

각 노드의 왼쪽 subtree의 값은 노드의 key값 보다 작거나 같아야 하고,

오른쪽 subtree의 값은 노드의 key값 보다 커야 한다.

 

 

12의 자리에 1이 올 수는 없다.

왜냐하면, 1이 부모 노드인 13보다 작은 수 이더라도, 10의 오른쪽 subtree이기 때문에 10보다 큰 수가 와야 하기 때문이다.

즉, 12 노드 자리에는 10~13까지만 key값으로 사용할 수 있는 것이다.

다른 노드들도 마찬가지이다.

 

2. Binary Search Tree 구현 방법

 

노드 클래스와 BST 클래스로 나누었다.

노드 클래스는 일반 이진 트리의 노드를 재활용한다.

 

BST 클래스에서 볼 것은 탐색, 삽입, 삭제이다.

탐색은 일반적인 구현과 다르게 find_location이라는 메소드를 통해 search를 구현하였다.

class Node:
  def __init__(self, key):
    self.key = key
    self.parent = self.left = self.right = None
  def __str__(self):
    return str(self.key)
    
class BST:
    def __init__(self):
        self.root = None
        self.size = 0
    
    def __len__(self):
        return self.size
    
    def __iter__(self):
        return self.root.__iter__()

    def find_location(self, key):
    # key값을 가지고 있는 노드가 있으면 해당 노드를 리턴한다.
    # 없으면 들어갈 수 있는 적절한 위치의 부모노드를 리턴한다.
        if self.size == 0:
            return None
        parent = None
        v = self.root
        while v != None:
            if v.key == key:
                return v
            elif v.key < key:
                parent = v
                v = v.right
            else:
                parent = v
                v = v.left
        return parent

    def search(self, key):
        v = self.find_location(key)
        if v == None:
            return None
        else:
            return v

    def insert(self, key):
        parent = self.find_location(key)
        if parent == None or parent.key != key:
            v = Node(key)
            if parent == None:
                self.root = v
            else:
                v.parent = parent
                if parent.key >= key:
                    parent.left = v
                else:
                    parent.right = v
            self.size += 1
            return v
        else:
            print("key가 이미 트리안에 있습니다.")
            return parent # 중복 키를 허용하지 않으면 None 리턴
            
     def deleteByMerging(self, x): # 노드 x 를 삭제
        a = x.left, b = x.right
        pt = x.parent
        # c == x를 대체할 노드
        # m == L에서 가장 큰 노드
        if a != None:
            c = a
            m = a
            while m.right:
                m = m.right
            if b != None:
                b.parent = m
                m.right = b
        else: # a == None
            c = b
        if pt != None:
            if c: 
                c.parent = pt
            if pt.key < c.key:
                pt.right = c
            else:
                pt.left = c
        else:  # pt == None (root == x)
            self.root = c
            if c: 
                c.parent = None
        self.size -= 1
        return