• Binary tree

  • binary tree 안의 각각의 노드는 최대 2개의 child node를 가짐

• Max nodes

  • $2^0+2^1+...+2^{h-1} = 2^h-1$
  • h : height

• Max and Min heights of N Nodes

  • Max Height : N
  • Min Height : log(N+1)
    • $N_{max} = 2^h-1$

• findItem() in a tree

  • root부터 child node까지 다 찾아봄
  • O(N)

Binary Search Tree

• BST

  1. 각각의 노드가 distinct value를 가지고 있음
  2. tree 안의 key value들은 greater than, less than으로 비교됨
  3. 왼쪽 < key value of each node < 오른쪽

  → node를 넣는 순서에 따라 모양이 달라짐

• findItem in a BST

  • Time Complexity : O(logN) ~ O(N) 사이

• deleteItem in a BST

  • 두 children이 있는 노드를 삭제할 때
    • 왼쪽 subtree에서 가장 오른쪽 노드로 교체하거나 → predecessor
    • 오른쪽 subtree에서 가장 왼쪽 노드로 교체 → successor

Tree Traversal

BST 가정

• Inorder Traversal

  • tree를 ascending order로 print
  • 왼 → 가 → 오

• Preorder Traversal

  • copy the tree
  • Depth first search (DFS)