Binary Search Tree

Trees are like graphs but cant point back at themselves

nodes on the left are smaller, nodes on the right are larger

used in b-trees which are used in databases

no random access


  • Array
    • Search
      • Worst: O(log n)
    • Insert: O(n)
    • Delete: O(n)
  • Binary Search Tree
    • Search
      • Average: O(log n), in a balanced tree
      • Worst: O(n), in a very unbalanced tree
    • Insert: O(log n)
    • Delete: O(log n)

add/remove from tree is log(k). k = size of heap/tree