Binary Search Tree
By TBTB7
SW/Algorithm & Data Structure
2021. 6. 13. 17:19

Binary Search Tree

이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조입니다.

코드 전체를 보시려면 이곳 을 참고하세요.

  • 이진탐색의 장단점 : 탐색 시간복잡도는 𝑂(log𝑛)으로 빠르지만 자료 입력, 삭제가 불가능
  • 연결리스트의 장단점 : 자료 입력, 삭제 시간복잡도는 𝑂(1)로 효율적이지만 탐색은 𝑂(𝑛)의 시간복잡도가 소요되어 비효율적

이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게 만들어진 자료구조입니다.

특징

  • 중복된 값을 가진 노드는 없습니다.
  • 각 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값을 지닌 노드들로만 이루어집니다.
  • 각 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 지닌 노드들로만 이루어집니다.
  • 왼쪽 서브트리, 오른쪽 서브트리 또한 위의 조건을 만족합니다.

이진탐색트리를 중위순회(inorder) 방식(왼쪽 서브트리-노드-오른쪽 서브트리 순)으로 탐색하면 이진탐색트리 내의 모든 값들을 정렬된 순서대로 읽을 수 있습니다.

operations

이진탐색트리의 핵심 연산은 네가지입니다.

  • 순회(traversal)
  • 검색(retreive/find)
  • 삽입(insert)
  • 삭제(delete)

이밖에 이진탐색트리 생성(create), 이진탐색트리 삭제(destroy), 해당 이진탐색트리가 비어 있는지 확인(isEmpty), 트리순회(tree traverse) 등의 연산이 있습니다.

Tree 구현

class Node(object):
  def __init__(self, data):
    self.data = data
    self.left = self.right = None

class BinarySearchTree(object):
  def __init__(self):
    self.root = None

traversal

이진탐색트리를 순서대로 탐색하는 방법은 중위순회입니다.

  def traversal(self):
    return self.traversalNode(self.root)

  def traversalNode(self, node):
    ret = []
    if node.left:
      ret.extend(self.traversalNode(node.left))
    ret.extend([node.data])
    if node.right:
      ret.extend(self.traversalNode(node.right))
    return ret

retreive/find

이진탐색트리의 특징(부모노드가 왼쪽 자식노드보다 크고, 오른쪽 자식노드보다 작다)을 활용하여 효율적인 탐색이 가능합니다.

리프노드까지 탐색하였는데 해당 값이 없다면 값이 트리에 존재하지 않음을 의미합니다.

이진탐색트리 탐색의 시간복잡도는 트리의 높이(루트노드-잎새노드에 이르는 엣지 수의 최대값) ℎ에서 𝑂(ℎ)가 됩니다.

최악의 경우 잎새노드까지 탐색해야 하는데, 이 때 ℎ번 비교 연산을 수행합니다.

  def find(self, key):
    return self.findNode(self.root, key)

  def findNode(self, node, key):
    if node == None:
      print("Tree doesn't have this key")
      return False, None
    elif node.data == key:
      return True, node.data
    elif node.data > key:
      return self.findNode(node.left, key)
    else:
      return self.findNode(node.right, key)

insert

이번엔 삽입 연산은 새로운 데이터를 트리의 리프노드에 붙이는 연산입니다.

(트리의 중간에 새 데이터를 삽입하게 되면 서브트리의 속성이 깨질 수 있기 때문에 삽입 연산은 반드시 리프노드에서 이뤄집니다.)

이진탐색트리 삽입의 시간복잡도는 트리의 높이(루트노드-리프노드에 이르는 엣지 수의 최대값)가 ℎ일 때 𝑂(ℎ)가 됩니다.

삽입할 위치의 리프노드를 탐색하며 ℎ번 비교하는 데 걸리는 시간이고, 연결리스트 삽입에 𝑂(1)만큼 추가로 소요됩니다.

  def insert(self, data):
    if self.root:
      self.insertNode(self.root, data)
    else:
      self.root = Node(data)

  def insertNode(self, node, data):
    if node.data > data:
      if node.left:
        self.insertNode(node.left, data)
      else:
        node.left = Node(data)
    else:
      if node.right:
        self.insertNode(node.right, data)
      else:
        node.right = Node(data)

delete

삭제 결과로 자칫 이진탐색트리의 속성이 깨질 수 있기 때문에 다른 연산보다 복잡합니다.

삭제 연산은 세가지 경우로 나누어 처리해주어야 합니다.

  • Case1) 자식노드가 없는 경우 : 해당 노드를 삭제하면 됩니다. 아래 고려해야할 자식 노드가 없습니다.

  • Case2) 자식노드가 하나 있는 경우 : 해당 노드를 삭제하고, 해당 노드의 자식노드와 부모노드를 연결해주어야 합니다.따라서 자식노드를 부모노드와 연결시켜주면 이진탐색트리의 속성이 깨지지 않습니다.

  • ex. 위의 그림에서 50의 자식노드인 55를 삭제하는 자리로 옮기면 속성이 깨지지 않게됩니다.

  • 이 때, 서브트리가 부모노드의 왼쪽이라면 자식노드들은 부모노드보다 모두 작고, 부모노드의 오른쪽이라면 자식노드들은 부모노드보다 모두 큽니다. (이진탐색트리의 속성)

  • Case3) 자식노드가 두 개 있는 경우

    • 노드를 삭제하고 Case2 처럼 자식 노드 중 하나를 그 자리에 놓으려고 하면 두 가지 방법(왼쪽/오른쪽)이 있는데, 이 때 문제가 발생할 수 있습니다.
    • 왼쪽 노드를 놓는 경우, 자식 노드가 오른쪽에 존재한다면 겹치게 됩니다.
    • 오른쪽 노드를 놓는 경우, 자식 노드가 왼쪽에 존재한다면 겹치게 됩니다.

    ex. 위의 그림에서 17 노드를 삭제하는 경우입니다. 왼쪽 자식 노드로 대체하면 15 vs 40, 오른쪽 자식 노드로 대체하면 13 vs 30 인 상황입니다. 이 상황을 해결할 수 있는 방법이 필요합니다.2, 3, 4, 5, 7, 13, 15,

    17

    , 25, 30, 35, 40, 50, 52, 55여기서

    • 15를 predecessor(삭제 대상 노드 왼쪽 서브트리 중 최댓값)
    • 25를 successor(삭제 대상 노드 오른쪽 서브트리 중 최솟값)

    이라고 합니다.

    • 두 노드는 반드시 자식 노드를 하나 이하만 갖습니다.
    • 또 자식노드를 하나 가질 경우
      • predecessor 는 왼쪽
      • successor 는 오른쪽에 있습니다. 즉, predecessor or successor 를 삭제한 노드의 자리에 위치시키고 있던 자리를 case0/case1로 처리해주면 트리의 속성을 깨지 않고 노드를 삭제할 수 있습니다.

    삭제 방법은 successor를 기준으로 다음과 같습니다.

    1. 삭제 대상 노드의 오른쪽 서브트리에서 successor 노드를 찾는다.
    2. 1에서 찾은 successor 노드를 삭제한다(Case1 or Case2).
    3. successor 노드를 삭제 대상 노드로 옮긴다.

  • 결과와 트리를 보면 지우려는 노드의 왼쪽 서브트리는 모두 해당노드(17) 보다 작고 오른쪽 서브트리는 큽니다. 결과에서 지우려는 노드의 양 옆 값을 주목해보겠습니다.

  • 이진트리는 중위순회로 탐색을 했을 때, 정렬된 순으로 탐색하게 됩니다. 현재 삭제하고 싶은 곳을 확인해보면 아래와 같죠.

Delete 연산의 시간복잡도는 Big-O notation으로 최악의 케이스를 고려해야 하므로 가장 연산량이 많은 case 3(삭제 대상 노드의 자식노드가 두 개인 경우)이 기준이 됩니다.

트리의 높이가 ℎ이고 삭제대상 노드의 레벨이 𝑑일 때, 1번 과정에서는 𝑑번의 비교 연산이 필요하고, successor 노드를 찾기 위해서는 삭제 대상 노드의 서브트리 높이(ℎ−𝑑)에 해당하는 비교 연산을 수행해야 합니다. 2번 3번 과정은 복사하고 삭제하는 과정으로 상수시간으로 계산할 수 있습니다. 즉, 𝑂(𝑑+ℎ−𝑑) = 𝑂(ℎ)가 됩니다.

  def delete(self, key):
    parent, node = self.root, self.root
    while node is not None and node.data != key:
      parent = node
      if key < node.data:
        node = node.left
      # search right
      elif key > node.data:
        node = node.right

    if node is None:
      return False
    else:
      # case3. left child, right child exist
      if node.left and node.right:
        successor_parent, successor = node, node.right
        # 1. find successor node at right subtree
        while successor.left is not None:
          successor_parent, successor = successor, successor.left
        # 2. delete successor node
        if successor.right:       # case2.
          successor_parent.left = successor.right
        else:                     # case1.
          successor_parent.left = None
        # 3. move successor node to delete node
        if parent.right == node:
          parent.right = successor
        else:
          parent.left = successor
        successor.left, successor.right = node.left, node.right

      # case2. left or right only one child exist
      elif node.left or node.right:
        # connect parent - child
        if parent.right == node:
          parent.right = node.left or node.right
        else:
          parent.left = node.left or node.right
      # case1. child not exist
      else:
        if parent.right == node:
          parent.right = None
        else:
          parent.left = None
      return True

실행

array = [7, 4, 2, 3, 5, 17, 13, 15, 40, 30, 25, 27, 35, 50, 55, 52]
bst = BinarySearchTree()

for x in array:
  bst.insert(x)
print(bst.traversal())

# Find
print(bst.find(15)) # True
print(bst.find(17)) # True

# Delete
print(bst.delete(3)) # True
print(bst.delete(3)) # True
print(bst.traversal())

print(bst.delete(50)) # True
print(bst.traversal())

print(bst.delete(17)) # True
print(bst.traversal())
[2, 3, 4, 5, 7, 13, 15, 17, 25, 27, 30, 35, 40, 50, 52, 55]
(True, 15)
(True, 17)
True
False
[2, 4, 5, 7, 13, 15, 17, 25, 27, 30, 35, 40, 50, 52, 55]
True
[2, 4, 5, 7, 13, 15, 17, 25, 27, 30, 35, 40, 52, 55]
True
[2, 4, 5, 7, 13, 15, 25, 27, 30, 35, 40, 52, 55]

한계점

이진탐색트리 탐색, 삽입, 삭제의 시간복잡도는 모두 𝑂(ℎ)입니다.

트리의 높이에 의해 수행시간이 결정되는 구조입니다.

이로 인한 한계가 존재합니다.

균형이 맞지 않게 연산이 이루어지게 될 경우, 아래의 그림처럼 극단적으로는 𝑛개의 노드가 크기 순으로 일렬로 늘어뜨려져 높이 또한 𝑛이 되는 이진트리탐색이 될 수 있습니다.

이 경우, 결과적으로 이진탐색트리의 시간복잡도는 𝑂(𝑛)이 됩고, 탐색 속도가 𝑂(log𝑛)으로 빠른 이진탐색의 장점을 활용할 수 없게 됩니다.

이러한 한계를 극복하기 위해 트리의 입력, 삭제 단계에 트리 전체의 균형을 맞추는 이진탐색트리의 일종인 AVL Tree가 만들어지게 됩니다.

저작자표시

'SW > Algorithm & Data Structure' 카테고리의 다른 글

AVL Tree  (0) 2021.08.01
Sorting Algorithm  (0) 2021.05.29
Tree  (0) 2021.05.10

티스토리툴바