It turns out that binary trees are a wonderful way to flexibly
store dynamic information.
Here's a tree T. Some terminology:
- root: top of the tree
- node: some place in the tree
- key: the value stored in a node
- left child, right child: the nodes immediately beneath a node
- parent: the node immediately above a node
- leaf: childless node
- depth: distance from node to root (depth of a tree is the depth of
the deepest leaf)
- height: distance to furthest leaf (height of a tree is the height
of the root)
What do we know about the height and depth of a tree?
Next: Representing Trees
Up: DYNAMIC PROBLEMS
Previous: Dynamic Operations