My Profile Photo

DongChanS's blog

수학과 학생의 개발일지

• on data structure, algorithm, tree, recursive

파이썬 자료구조 (4) Binary Search Tree

아래 포스트는 Data Structure and Algorithmic Thinking with Python을 참고하여 작성되었습니다.

1) Binary Search Tree (BST)

이전 포스트(3편)에서 만든 이진트리는 사실 별 기능이 없습니다.

그냥 원소들을 여러 방법으로 순회하는 기능만 담고 있을 뿐이죠.

하지만 이번에 소개할 이 Binary Search Tree(이하 BST)는

이전에 소개했던 Binary Tree의 재귀적인 특성(left subtree와 right subtree도 Binary Tree)을 이용해서 매우 효율적으로 삽입, 검색, 제거 연산을 구현하였습니다.

1-1. Binary Search Tree란?

BST와 Binary Tree가 다른 점은 단 하나입니다.

바로 원소들의 순서가 정해져 있다는 것입니다.

1

left subtree에는 root노드보다 작은 값들이 저장되어있고,

right subtree에는 root노드보다 큰 값들이 저장되어있습니다.

물론, root 노드에만 국한된 규칙이 아니고 Binary Tree의 임의의 subtree에 대해서도 이러한 규칙이 성립해야합니다.

그렇기 때문에 아무렇게나 노드를 집어넣으면 이러한 규칙이 만족되기가 어렵죠. 그래서 따로 삽입 로직을 작성해줘야 합니다.

…

아! 그러면 root노드와 같은 값이 등장하면 어떻게 하냐구요?

안타깝게도 BST에서는 같은 값이 중복되는 것을 허용하지 않습니다.


1-2 Important Notes on Binary Search Trees

다음은 BST를 이해하는 데 있어 매우 중요한 특성들입니다.

  1. BST의 Left subtree, Right subtree 또한 BST이다.

    => 가장 중요한 특성입니다. 이 때문에 LEVEL에 대한 재귀함수를 구성할 수 있습니다.

  2. BST에서 데이터를 순서대로 가져오기 위해서는 중위순회(inorder traversal)가 필요하다.

    => 왜냐하면 중위순회는 left subtree -> root node -> right subtree 순서대로 순회하는데, BST의 원소 배열도 left subtree < root node < right subtree 형식으로 이루어져 있기 때문입니다.

    그 말인 즉슨, 중위순회를 통해서 자동으로 Sorted된 데이터를 가지고 올 수 있다는 말입니다.

  3. BST의 각 연산(삽입/삭제/검색)의 시간복잡도는 Tree의 높이(Level)에 영향을 받습니다.

    => 왜냐하면 우리가 만들 재귀함수는 left subtree와 right subtree 둘 중에 하나를 선택해서 level을 낮춰서 다시 재귀함수를 call할 것이기 때문입니다.

  4. 그렇기 때문에 BST는 Fully binary tree(균형 트리)일 때 가장 효율적이고, 트리가 한 쪽으로만 뻗어나갈 때 비효율적인 구조입니다.


2) Implementation

이전 포스트에 비해서 구현 부분이 상당히 많은 비중을 차지합니다.

(BST를 제가 직접 구현했기 때문에 책이랑은 많이 다릅니다.)

2-0. Node, BinSrcTree

from Tree import Node

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

이전 포스트에서 작성했던 노드와 완벽히 동일한 클래스입니다.

BST의 생성자도 그냥 root를 명시해주는 것 말고는 없습니다. 시작은 항상 루트니까요.

2-1. Operations

  • Inserting an element

  • Find an element / Find maximum / Find minimum
  • Deleting an element

기능이 그렇게 다양하지는 않습니다. 사실 Data Structure로써 삽입/저장/삭제만 잘 되면 장땡 아닙니까?

  • Sorting the elements of binary search tree

1-3절에서 언급한 대로, 데이터를 정렬하는 것은 중위순회와 동일합니다. (따라서 시간복잡도가 O(n)이 될 것이라는 것을 짐작할 수 있습니다.)


2-2. Inserting an Element

데이터 삽입은 다음과 같은 로직으로 이루어집니다.

  1. BST를 만족하면서 데이터를 삽입할 수 있는 빈 자리를 찾는다.
  2. 데이터를 삽입한다.

사실 데이터를 삽입하려면 검색을 먼저 해야하지 않나? 하고 생각하실 수 있는데,

BST에서 데이터 삽입은 무조건 빈 자리에서만 이루어지기 때문에, 이미 갖고 있는 원소를 검색하는 검색로직과 우리의 1번 로직은 매우 다르다고 할 수 있습니다.


# 노드에 데이터를 넣는 과정이 중복되서 따로 staticmethod를 만들어놨습니다.
@staticmethod
def valued_Node(data):
    a = Node()
    a.setData(data)
    return a

def insert(self,data):
# 1. 루트가 비었다 : 그 자리에 넣음
# 2. 루트가 안 비었다 : tree를 계속 타고 내려가면서 넣을 자리를 찾는다.
    if self.root == None:
        self.root = BinSrcTree.valued_Node(data)
    else:
        BinSrcTree.insert_wt_base(data,self.root)
        
@staticmethod
def insert_wt_base(data,base):
# data가 base보다 크다면 right subtree만 고려
    if data > base.getData():
        if base.getRight():
            # 바로 오른쪽에 뭔가가 있으니 바로 들어가지는 못하겠구나..
            BinSrcTree.insert_wt_base(data,base.getRight())
        else:
            # 오른쪽에 없으면 그냥 그자리에 들어가면되겠군!
            base.setRight(BinSrcTree.valued_Node(data))
# data가 base보다 작다면 left subtree만 고려
    elif data < base.getData():
        if base.getLeft():
            BinSrcTree.insert_wt_base(data,base.getLeft())
        else:
            base.setLeft(BinSrcTree.valued_Node(data))

data = base.getData()의 상황을 무시하기 위해서 의도적으로 else문을 넣지 않았습니다.

(같은 데이터가 이미 있다면 넣을 필요가 없으니까요)


2-3. Searching an Element

데이터 검색의 로직은 다음과 같습니다.

다만 이전과는 달리 트리에 데이터가 없는 상황도 고려를 해야합니다.

  1. 검색할 값(data)이 root노드의 값과 같다면 -> 데이터 반환
  2. data가 root의 값보다 작다면 -> left subtree로 진입
  3. data가 root의 값보다 크다면 -> right subtree로 진입

저는 compare함수를 통해서 data와 루트노드를 지속적으로 비교하는 작업을 수행하였습니다.

def find(self,data):
    return self.compare(self.root,data)

@staticmethod
def compare(base,data):
    if data == base.getData():
        return base
    elif base.getLeft() and data < base.getData():
        # 일단 Left가 있는지 확인해야 왼쪽 서브트리를 탈 수 있습니다!
        return BinSrcTree.compare(base.getLeft(),data)
    elif base.getRight() and data > base.getData():
        return BinSrcTree.compare(base.getRight(),data)

아까부터 계속 instance method로 직접 구현하지 않고 staticmethod를 통해서 재귀함수를 구현하는 이유는

굳이 재귀함수에 멤버변수(내지는 클래스변수 포함)들을 쓸 필요가 없어서 그렇습니다. (물론 멤버변수라고는 루트하나밖에 없지만요..)


그리고 최대 최소원소를 찾는 로직은 간단합니다.

왜나하면 BST의 특성상 최대값은 항상 맨 오른쪽에 있으며, 최소값은 항상 맨 왼쪽에 있기 때문입니다.

def findmax(self):
    curr = self.root
    while(curr.getRight()):
        curr = curr.getRight()
    return curr.getData()
def findmin(self):
    curr = self.root
    while(curr.getLeft()):
        curr = curr.getLeft()
    return curr.getData()


2-4. Deleting an Element

원소를 삭제하는 로직은 이전보다는 까다롭습니다.

삽입 연산의 경우는 빈 자리에서만 수행하기 때문에 BST의 조건을 위해서 고려해야할 것이 부모노드밖에 없었는데,

삭제 연산의 경우 Leaf가 아닌 노드에서 삭제를 한다면 끊긴 포인터를 다시 복구하는 작업도 필요하고, 그렇게 복구하면서 엉망진창이 된 트리가 BST의 조건을 만족하는지도 확인해야 하기 때문입니다.


결론적으로 원소 삭제의 유형은 3가지입니다.

  1. Leaf node를 삭제할 때
  2. 한쪽 자식만 있는 노드를 삭제할 때
  3. 양쪽 자식이 있는 노드를 삭제할 때

1번 유형은 간단합니다.

2

아무런 걱정 없이 제거하시면 됩니다.


다음은 2번 유형입니다. 다음과 같은 상황에서 4번 노드를 삭제하고 싶다면,

3

4번노드의 자식이 하나밖에 없기 때문에 4번 노드의 자식을 2번노드로 연결시킨다면

2번 입장에서는 4번노드 대신에 3번노드가 자식이 되기 때문에 여전히 Binary Tree의 조건을 만족하며, Right subtree는 어자피 2번노드보다 큰 값들만 모여있기 때문에 크기조건도 문제가 되지 않습니다.


3번 유형은 조금 복잡합니다.

다음과 같은 예시에서 8번 노드를 삭제하려고 한다면,

4

  1. 7번 노드의 값과 8번 노드의 값을 바꿔치기한다.
  2. 기존의 7번 노드를 삭제한다.

굉장히 영리한 방법입니다. 노드의 연결관계를 복잡하게 하는게 아니라 값만 바꿔치기하는 것으로 대체하였습니다.

그런데 무슨 기준으로 바꿔치기할 노드를 선정했을까요?

바로, 8번 노드의 Left subtree 중에서 가장 큰 값을 찾은 것입니다.

왜냐하면,

  • BTS의 특성에 의해서 findmax 함수는 매우 간단하다.

  • 그렇게 찾은 maximum값은 기껏해야 left child밖에 없다. -> 1번, 2번유형 재활용 가능

    (right child가 존재한다면 maximum이라는 가정에 모순이 됩니다.)

같은 논리로 Right subtree 중에서 가장 작은 값을 찾는 방법도 적용할 수 있습니다.


그런데 이상한 점이 있습니다.

어찌됬건 삭제할 노드를 찾기 위해서 위에서 구현한 Search method를 활용하고 싶은데,

아까 구현한 Search method는 주어진 노드만 반환할 뿐이지 부모노드의 정보를 반환하지는 않습니다.

그렇게 되면 2번 유형에서 4번 노드의 위치를 찾아도 부모노드인 2번노드에 대한 정보가 없기 때문에 연결시켜줄 수가 없습니다.

그래서 Find method를 다시 구현해야합니다 ㅠㅠ

아까랑 다른 점이 있다면, 검색할 data와 root의 데이터를 비교하는게 아니라 왼쪽자식, 오른쪽자식의 데이터를 각각 비교한다는 점입니다.

연산량은 조금 더 추가되겠지만 부모노드의 정보를 같이 들고올 수 있습니다.

#################### Overwrite ##############
def find(self,data):
    if data == self.root.getData():
        return self.root
    return BinSrcTree.compare(self.root,data)
    # self.compare의 결과값은 None이거나, [부모노드, 방향]이 됨.
@staticmethod
def compare(base,data):
    if base.getLeft() and data <= base.getData():
        if data == base.getLeft().getData():
            return [base,"left"]
        return BinSrcTree.compare(base.getLeft(),data)
    elif base.getRight() and data >= base.getData():
        if data ==  base.getRight().getData():
            return [base,"right"]
        return BinSrcTree.compare(base.getRight(),data)

Delete 메소드 전체는 이렇습니다.

def delete(self,data):
    res = self.find(data)
    if res:
        if type(res) == Node:
            """루트노드는 어떻게합니까? : 그건 잠시 후에.."""
        else:
            [parent,direction] = res
            base = BinSrcTree.get_wt_direction(*res)
            # direction이 문자열이기 때문에 자식노드(검색된 노드)를 찾기 위해서 메소드를 따로 구성하였습니다.
            BinSrcTree.delete_wt_node(parent,base,direction)
            
@staticmethod
def delete_wt_node(parent,base,direction):
    if base.getLeft() == None and base.getRight() == None: # 유형1
        base = None
    elif base.getRight() == None: # 유형2 (1)
        BinSrcTree.set_wt_direction(parent,direction,base.getLeft())
        # 이 경우에는 garbage collection에 따라 base는 자동으로 사라집니다.
    elif base.getLeft() == None: # 유형2 (1)
        BinSrcTree.set_wt_direction(parent,direction,base.getRight())
    else: # 유형3
        # 삭제로직을 한 번 더 써야하므로 curr의 부모노드가 필요합니다.
        parent, curr = base, base.getRight()
        while(curr.getLeft()):
            parent, curr = curr, curr.getLeft()
            # 만약,
            # parent = curr
            # curr = curr.getLeft()라고 하면 parent와 curr이 같아져버림!
        base.setData(curr.getData()) # 바꿔치기
        BinSrcTree.delete_wt_node(parent,curr,"right") # curr 삭제

@staticmethod
def get_wt_direction(parent,direction):
    if direction == "left":
        return parent.getLeft()
    elif direction == "right":
        return parent.getRight()
@staticmethod    
def set_wt_direction(parent,direction,node):
    if direction == "left":
        parent.setLeft(node)
    elif direction == "right":
        parent.setRight(node)

만약 루트노드의 값을 삭제해야한다면??

이 경우도 3번 유형의 아이디어를 이용해서 간단하게 해결할 수 있습니다.

바로, root노드와 Right subtree의 가장 작은 값을 바꿔치기해서 제거하면 됩니다.

그런데 주의할 점은 Right subtree가 없을 때 바로 root를 제거해버리면 garbage collected에 의해서 트리 전체가 없어집니다. 꼭 root를 Left노드로 지정해주어야합니다.

if type(res) == Node:
    if self.root.getRight():            
        parent, curr = base, base.getRight()
        while(curr.getLeft()):
            parent, curr = curr, curr.getLeft()
            base.setData(curr.getData())
            BinSrcTree.delete_wt_node(parent,curr,"right")
    else:
        self.root = self.root.getLeft()


3) Disadvantage of BST

사실 BST의 삽입/삭제/검색 연산의 시간복잡도는 전부 O(h)입니다.

(h : 트리의 높이)

그런데, 같은 데이터여도 삽입 순서에 따라서 높이차이가 심하게 나게 됩니다

bt = BinSrcTree() # skewed, 높이 6
bt.insert(1)
bt.insert(3)
bt.insert(5)
bt.insert(7)
bt.insert(8)
bt.insert(10)

bt = BinSrcTree() # 괜춘함, 높이 3
bt.insert(5)
bt.insert(3)
bt.insert(1)
bt.insert(7)
bt.insert(8)
bt.insert(10)

이런 문제 때문에 최악의 시간복잡도는 O(n)이며, skewed tree일때는 단연 최악의 자료구조가 됩니다.

이것을 해결하기 위해서 AVL트리가 필요하다고 합니다.

comments powered by Disqus