Binary trees -- traversal, insertion, deletion, and balancing.

这一章比较纠结，可浅可深。既然是伪技术总结，就只提一提要点就好了。

1. Traversal

i) Breadth First: The key is to use a queue to maintain the traversal...two steps as follow.
a) Enqueue root.
b) while (queue != null)
        {
         qPointer = Dequeue;
         visit qPointer;
         Enqueue left and right children of the qPointer.
}

ii) Depth First: Inorder, Preorder and Post order.
L - Left sub tree; R- Right sub-tree; V = visit (access) the node;

Easy in using recursion,
Inorder = LVR.
Preorder = VLR.
Postorder = LRV.

A bit complicated in using non-recursive methods.
a) by maintaining a stack, traversal can be implemented using iterations.
b) using a threaded tree can avoid the stack.
c) Morris's algorithm can avoid both a) and b) to traversal a tree through tree transformation. (complicated...)

In general, recursive methods has better readable code with marginal cost of performance. However, for certain cases, e.g., ultimate performance to be achieve or suffering stack overflow, non-recursive methods or Morris's algorithms has to apply!!

2. Insertion in threaded tree and deletions.

i) insertion.
the key points are using two pointers, prev and p. Consider element el to be inserted. Keep going until these three stop criterion.

a) if (el < p -> el) prev = p and p go left (p = p -> left) until p == nullptr;
b) if (el > p -> el and thread indicator == 0) prev = p and go right until p == nullptr;
c) if (el > p -> el and thread indicator == 1) stop;

How to insert:
a) if (el < prev -> el) insertion is the left child of prev, successor of the child is prev.
b) else if (prev -> successor) means parent of the insertion is not the rightmost node, so, prev -> right = insertion. make parent's successor the insertion's successor.
c) else prev -> right = insertion. (prev is the rightmost node, just insert new node to the right side.)

This is important and very easy to make mistakes when assigning the successor indicator....


ii) deletion.
By merging or copying we could delete a node that has sub-trees on both of its left and right side.

Merging increases the tree depth significantly while copying method has to consider the balancing issue in those problems of many deletion and insertion operations.

3. Balancing
AVL and black-red trees are similar. Specifically, black-red tree is the underlying implementation of (sorted) map and set in STL in C++!!