Weiss Ch. 4.1 - 4.

Trees' ubiquity and utility: expression and evaluation (parse trees, expression trees), dictionaries for O(logN) search, insertion, deletion. Binary and k-ary trees.

Many definitions, most analogous to Western family relationships,
except for the *root* and *leaves*.

CS Trees are notoriously recursive in structure, so the "branches" are
called *subtrees*.

*Path* between nodes is the sequence of nodes leading (through
successors or children) from one to the other; its *length* is the
number of nodes - 1, so node has 0-length path to self. *Depth* of node
is length of unique path (else it's a graph) from
root. *Height* of a node is length of longest path from it to a
leaf. Height of empty tree is -1.

There are some cute tree implementations that use arrays (e.g. full binary trees), but generally think of structures (classes) and pointers. For k-ary trees with small k, works to have pointers to explicit (left, middle, right...) children in the node, but an easy extension to deal with arbitrary numbers of children is the "first child, next sibling" implementation (fig. 4.4), in which each's nodes children are in a linked list.

*Binary Tree More Explicitly:*

*Binary Tree Java:*

A rooted tree has only one root, but really trees have sub-trees that look just like trees. They are thus naturals for recursive techniques and arguments.

So: To traverse (visit all nodes in) tree, first visit the root, then visit all the children. Or vice-versa. (pseudocode Fig. 4.6). We need to see that visiting the root is not the same as visiting the children. The first (root) is the recursion-ending base case, and the second (child) is a recursive call that descends a recursive level. Also "visit" is short for "do necessary work on".

With binary trees, there are three common and useful O(N) recursive
methods: *Preorder* (do root, do left child, do right child), *Inorder *
(left, root, right), and *postorder* (left, right, root). For the perverse,
inverting left and right gives more traversals.

Preorder allows a natural way to list files in a UNIX directory -- UNIX directory also has . and .., (self- and back-pointers) so not a pure tree. To get cumulative disk usage we need postorder. To compute the height of each node also need postorder. Another sometimes-useful traversal is level-order, which lists all nodes at depth 0, 1, 2, 3....and works iteratively with a queue of children to print.

W. 4.2.2 introduces shows expression trees (see also the relevant lecture PPTs), which are a natural notation for arithmetic expressions and can be traversed by inorder -- produce parenthesized expression of left subtree, then emit the operator, then the parenthesized expr. for right subtree. Or can print out (left, right, operator -- postorder) and get postfix notation out, or a preorder traversal gives a polish prefix expression. Or can traverse (inorder most natural) to evaluate the expression and get an answer.

Construction of a tree from a postfix expression is just like evaluation of the postfix using a stack. Look one char at a time, if it's an operand then make a one-node tree and put it on stack, if an operator, pop two trees and make a new tree.

Constructive Solid Geometry (CSG) 3-D models. leaves are
primitive solids, internal nodes are set operators. Ray casting and
Boundary evaluation. Hardware implementation.

*The Idea:*

* In Practice (POV-Ray)*

Don't want to do linear search through an array or list to locate an item. Hence trees: ideally need log(N) levels for N items, so maximum path to any item is log(N).

Make sure you understand last sentence. Balanced (full, ideal) Binary Trees: N elts at one level means 2N
at next level, so with k levels (∑_{k} 2^{k}) -1
elts in tree (1, 3, 7, 15,...), add one to each and thus show
the depth is (just) > the log of the number of elts.

BUT naive methods for inserting and deleting can yield trees with O(N) path-lengths (e.g. no right children). Hence the interesting insertion and deletion algorithms that have been created by smart people over decades...

Weiss fig. 4.17 shows his ADT for trees: the most basic functionality
is
`insert` and `: also we've got: print,
contains (a
boolean), min, max
(for trees of comparable elts), makeEmpty, isEmpty.
Weiss discusses his code for all this at length with us: nice
fireside chat --- mighty relaxin'. 113-120. Along the way, salient
points about duplicates, fact that in data structures deletes are
often harder than inserts, lazy deletion, other nuggets.
`

In a BST, for any node X, *all the items in X's left subtree* are
smaller than X and all those in its right subtree are larger. The
obvious way to find something that's not the current node is:

**want smaller, visit left subtree;
want larger, visit right**.

The BST property is not local to a node and its children:

`Contains`: Need to test nodes: if null, return false (not there); if
equal to desired, return true.
Else
recursively call `contains` on L or R subtree depending on comparison. Note
these are tail-recursive calls so can be replaced by while loops!

`FindMin, FindMax`: go all the way down to left or right. Recursively
or iteratively.

`Insert X`: Proceed as for `Contains`: if find X, do what you want about
duplicates; otherwise insert X at last spot traversed. (fig. 4.21)

`Delete X`; Easy if node is leaf or has only one child. Two children:
replace with smallest value in right subtree, which gets deleted (and
it only can have one child or it wouldn't be smallest, right?).

W. 4.3.5 is quite a fun little section. For BSTs, average case analysis is possible -- a rare treat. We can characterize useful tree statistics if all insertion sequences are equally likely.

The relevant statistic for search is the average (hence the total) path length in
a tree; called its *internal path length* D(N).

The math of the analysis points ahead to *recurrence equations*,
which we'll deal with later. For now, read this little section
"for pleasure". The two figures illustrate a probably
"unintended consequence" (nasty surprise) of the delete algorithm.

Can you explain the problem?

Properties of simple BSTs motivate the two approaches:

1: being careful
to construct and maintain balance in the tree (e.g. AVL trees,
red-black trees, 2-3 trees...) to
guarantee logN lookup every time. Clever algorithms, tougher
implementations.
OR

2: to guarantee no sequence of long (O(N)) lookups can happen by
modifying ("self-adjusting") the tree upon each lookup (e.g. promoting whoever's found to be
the new root!): Splay trees. This idea aims at good
*amortized*
(averaged over time)
performance (since each bad case leads to immediate
improvement).

Last update: 7/15/13