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

Complexity

  • 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

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html https://www.cs.usfca.edu/~galles/visualization/BTree.html https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html