Tree Data Structures (cont)
Other special kinds of tree
- m-ary tree:
each internal node has exactly m children
- Ordered tree:
all left values < root, all right values > root
- Balanced tree:
has ≅minimal height for a given number of nodes
- Degenerate tree:
has ≅maximal height for a given number of nodes
![[Diagram:Pic/binary-search-trees.png]](Pic/binary-search-trees.png)
Perfectly balanced binary trees have the properties
- #nodes in left subtree = #nodes in right subtree
- this property applies over all nodes in the tree
Shape of tree is determined by order of insertion.
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}