Trees

Binary Search Tree

• binary tree로 구성된 data structure
• binary-search-tree property를 만족
  • node $x$에 대해 $y$가 left subtree의 node이면 $y.key \le x.key$이다. 만약 $y$가 right subtree의 node이면 $y.key \ge x.key$이다.
• sorted order print는 inorder tree walk로 $Θ(n)$에 수행할 수 있다.

Query

• query는 $O(h)$에 수행된다.

search(x, k):
    if x == null or k == x.key:
        return x
    if k < x.key:
        return search(x.left, k)
    else:
        return search(x.right, k)

Insertion

• $O(h)$에 수행된다.

insert(T, z):
    y = null
    x = T.root
    while x != null:
        y = x
        if z.key < x.key
            x = x.left
        else x = x.right
    z.p = y
    if y == null
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

Deletion

• child가 있는 경우와 없는 경우로 나뉘는데, 있으면 문제가 tricky하다.
• child가 없으면 그냥 제거하면 된다.
• child가 하나면 z의 위치에 z의 child를 놓으면 된다.
• child가 둘인 경우
  • z의 successor y를 z 자리에 놓는다.
    • successor는 right subtree의 node 중 left subtree가 없는 것이다.
  • y가 z의 child일 경우 y를 z 자리에 놓으면 된다.
  • y가 z의 child가 아닐 경우
    • y를 y의 child 위치에 놓고 y를 옮긴다.

transplant(T, u, v):
    if u.p == null:
        T.root = v
    elif u == u.p.left:
        u.p.left = v
    else:
        u.p.right = v
    if v != null:
        v.p = u.p

• transplant는 한 subtree를

Python Code

boj 1539

• 1539는 bst같이 생겼지만 bst가 아니다.
  • bst의 새로 추가되는 node는 정렬한 후 양 옆 숫자를 확인했을 때 더 depth가 낮은 node의 child로 들어간다는 성질을 이용