Binary Search Tree (notes)

 Binary Search:

Worst-case: O(h). h = height of the tree; Best-case: O(1)

AVL Tree: (height balanced property)

Height- Balanced Property: For every internal node v of T, the heights of the children of  v differ at most 1.

Proposition: The height of an AVL tree sorting n entries is O(logn)



a way to achieve logarithmic time for the fundamental dictionary operations.

Slay Tree