[prev] [index] [next]

Tree Review

Binary search trees ...
  • data structures designed for O(logN) search
  • consist of nodes containing item (incl. key) and two links
  • can be viewed as recursive data structure (subtrees)
  • have overall ordering (values(L) < root < values(R))
  • insert new nodes as leaves, delete from anywhere
  • have structure determined by insertion order (worst: O(N))
  • operations: insert, delete, search, rotate, rebalance, ...