[algorithm] binary search tree

• binary search tree

• definition

  • root node의 left child는 root보다 작다
  • root node의 right child는 root보다 크다
  • node는 중복없이 uniq해야한다.
  • left, right child 역시 binary search tree(recursive definition)

• property

  • 오름차순으로 정렬되어 있음(in-order traversal)
  • root의 left most child는 최소값
  • root의 right most child는 최대값

• traversal

  • in-order
    • bst에 저장된 키값을 오름차순으로 순회
  • pre-order
    • bst를 serialize할 때 사용
  • post-order

• find key

  • recursive 혹은 while loop로 구현 가능

• insert key

  • root = insert(root, key)
  • if(!node) return make_node(key)
  • 작으면, node->left = insert(node->left, key)
  • 크면, node->right = insert(node->right, key)
  • 같으면, return node

• delete key

  • insert와 비슷한 방식으로 구현
  • delete(root, key) recursively
  • 일단 해당 key를 찾아야한다.
  • 해당 key node가 leaf 혹은 null
    • if(node) free(node)
    • return null
  • 해당 key node가 left child만 있음
    • free(node)
    • return node->right
  • 해당 key node가 right child만 있음
    • free(node)
    • return node->left
  • 해당 key node가 left,right child 모두 있음
    • right successor, rkey를 찾는다
    • node->right = delete(node->right, rkey)

• serialize and deserialize

  • serialze(pre-order traversal)
    • ex) 10 5 1 7 12
  • deserialize
    • transition-based dependency parsing과 약간 다르지만 비슷
    • stack을 사용
    • push(list[0])
    • list[1:n]까지 iterate
      • stack top과 list[i] 비교
      • list[i]가 작으면
        • top->left = insert(top, list[i])
        • push(list[i])
      • list[i]가 크면
        • pop untill top < list[i]
        • last->right = insert(last, list[i])

• catalan number

  • n개의 숫자로 구성 가능한 bst의 개수는 catalan number
    • C(0) : 1
    • C(1) : 1
    • C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... C(n-1)*C(0)