Tree Review
Binary search trees …
- data structures designed for O(log n) search
- consist of nodes containing item (incl. key) and two links
- can be viewed as recursive data structure (subtrees)
- have overall ordering (data(Left) < root < data(Right))
- insert new nodes as leaves (or as root), delete from anywhere
- have structure determined by insertion order (worst: O(n))
- operations: insert, delete, search, …
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}