|
Table of Contents
|
binary search tree, children on the left < x < children on right side
insertion and search complexity O(logN) delete is complicated.
illustration http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/
java code refer : http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/
c++ code refer: http://en.literateprograms.org/Binary_search_tree_(C)
hashing: http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic12/
One advantage balanced binary search trees have over hash tables is that they also retain a relative ordering among their contents. While the other operations aren't quite as fast as a hash table (refer to the table below), logarithmic time is certainly not bad by any means. However, if you're not interested in the ordering of its items or frequent iterating, a hash table is certainly the way to go.
http://horizon.ece.utexas.edu/~jacome/ee360cN/lectures/
balanced tree : http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic19/
tree
http://www.mathcs.duq.edu/drozdek/DSinCpp/genBST.h
http://hi.baidu.com/hbmubai/blog/item/0f7712019ea809d1277fb5f3.html
preorder recrusive or not
public void iterativePreorder() {
BSTNode<E> p = root;
Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
if (p != null) {
stack.push(p);
while (!stack.isEmpty()) {
p = (BSTNode<E>) stack.pop();
visit(p);
if (p.right != null)
stack.push(p.right);
if (p.left != null)
stack.push(p.left);
}
}
}
inorder non recursive
public void iterativeInorder() { BSTNode<E> p = root; Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>(); while (p != null) { while (p != null) { if (p.right != null) stack.push(p.right); stack.push(p); p = p.left; } p = (BSTNode<E>) stack.pop(); while (!stack.isEmpty() && p.right == null) { visit(p); p = (BSTNode<E>) stack.pop(); } visit(p); if (!stack.isEmpty()) { p = (BSTNode<E>) stack.pop(); } else { p = null; } } }
iterative post order
approach -1
// left-to-right postorder = right-to-left preorder
public void iterativePostorder() {
IntBSTNode p = root;
Stack travStack = new Stack(); //trace用堆疊
output = new Stack(); //結果堆疊
if (p != null) { // left-to-right postorder = right-to-left preorder LRV
travStack.push(p);
while (!travStack.isEmpty()) {
p = (IntBSTNode) travStack.pop();
output.push(p);
if (p.left != null) travStack.push(p.left);
if (p.right != null) travStack.push(p.right);
} //while
while (!output.isEmpty()) {
p = (IntBSTNode) output.pop();
p.visit();
}
} //if
}
approach 2:
public void iterativePostorder() {
BSTNode<E> p = root, q = root;
Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
while (p != null) {
while (p.left != null{
stack.push(p);
p = p.left;
}
while (p != null && (p.right == null || p.right == q)) {
visit(p);
q = p;
if (stack.isEmpty())
return;
p = (BSTNode<E>) stack.pop();
}
stack.push(p);
p = p.right;
}
}
misc
- 一對中序順序(inorder sequence)及前序順序(preorder sequence)可唯一決定一個二元樹。
- 一對中序順序(inorder sequence)及後序順序(postorder sequence)亦可唯一決定一個二元樹。
- 一對前序順序(preorder sequence)及後序順序(postorder sequence)無法決定唯一一個二元樹
有一個前序順序為：ABCDEFGHI 中序順序為：BCAEDGHFI 則其相對應的二元樹為何？
解：前序追蹤的第一個字元A一定是樹根，再從中序追蹤知在A之前的節點BC是左子樹，在A之後的節點EDGHFI是右子樹，由此我們可以大略的建立出其相對應的二元樹形狀。
再由前序追蹤的第二個字元B知其為樹根，從中序追蹤知B的左子樹是空的，右子樹是C，因此其進一步結果如下
http://www.google.com/url?sa=t&source=web&ct=res&cd=9&url=http%3A%2F%2Ftmue.edu.tw%2F~lai%2Faf-teach%2Faf-algorithm-DS%2FDSinjava%2FDS-Trees.ppt&ei=Zb6dSo_nOJ6-tAOhvODaBg&rct=j&q=iterativepostorder+bst&usg=AFQjCNFb5ZLU6wt3rrxX_ymcJ8gJRQABHQ
breadth traversal
void Tree::LevelOrder()
{
Queue Q;
TreeNode *currentNode = root;
while (currentNode)
{
Visit(currentNode);
if (currentNode->leftChild) Q.Push(currentNode->leftChild);
if (currentNode->rightChild) Q.Push(currentNode->rightChild);
if (Q.IsEmpty()) return;
currentNode = Q.Pull();
}
}
insert
void BinarySearchTree::insert(int d) { tree_node* t = new tree_node; tree_node* parent; t->data = d; t->left = NULL; t->right = NULL; parent = NULL; // is this a new tree? if(isEmpty()){ root = t; } else { //Note: ALL insertions are as leaf nodes tree_node* curr = root; while(curr) { parent = curr; if(t->data > curr->data) curr = curr->right; else curr = curr->left; } if(t->data < parent->data) parent->left = t; else parent->right = t; } }
struct node* insert(struct node* node, int data) { // 1. If the tree is empty, return a new, single node if (node == NULL) { return(newNode(data)); } else { // 2. Otherwise, recur down the tree if (data <= node->data) node->left = insert(node->left, data); else node->right = insert(node->right, data); return(node); // return the (unchanged) node pointer } }
delete
Tree-Delete(T, z) /* Determine which node to splice out: either z or z’s successor. */ if left[z] = NIL or right[z] = NIL then y = z else y = Tree-Successor[z] /* Get x as descendant of y. */ if left[y] != NIL then x = left[y] else x = right[y] /* y is removed from the tree by manipulating pointers of p[y] and x */ if x != NIL then p[x] = p[y] if p[y] = NIL then root[T] = x else if y = left[p[i]] then left[p[y]] = x else right[p[y]] = x /* copy y's data into z and delete y*/ if y != z then key[z] = key[y] copy y’s data into z. delete y;
precedendor
successor
Tree-Successor(x) 1. if right[x] != NIL 2. then return Tree-Minimum(right[x]) 3. y = p[x] 4. while y != NIL and x = right[y] 5. do x = y 6. y = p[y] 7. return y
version-1 + 2 c code and splice code
min value
int minValue(struct node* node)
{
struct node* current = node;
while (current->left != NULL)
{
current = current->left;
}
return(current->data);
}
Write C code to check if a given binary tree is a binary search tree or not?
int isThisABST(struct node* mynode)
{
if (mynode==NULL) return(true);
if (node->left!=NULL && maxValue(mynode->left) > mynode->data)
return(false);
if (node->right!=NULL && minValue(mynode->right) <= mynode->data)
return(false);
if (!isThisABST(node->left) || !isThisABST(node->right))
return(false);
return(true);
}
deepest common ancestor
Find the deepest common ancestor of two leaves in a binary search tree;
Do not traverse from the leaves. Instead, locate the node top/down.
How about finding the shallowest common ancestor of two leaves?
找shallowest的 trivial，就是root。
找deepest的,比较两个叶节点的值，小的p，大的q。从根节点起，当前节点x。
void deepest(node * x) { if(x==null) return; push_into_queue(x); if(x.value> p.value && x.value < q.value) return; if(x.value> q.value) deepest(x->left); if(x.value< p.value) deepest(x->right); }
convert a binary tree into a linked list
struct Tree { int i; struct Tree* left; struct Tree* right; }; Tree * Convert_to_list (Tree* T) { Tree * T1, T2, temp; if (T != NULL) { T1 = Convert_to_list(T->left) T2 = Convert_to_list(T->right) T->right = T2; if (T1!= NULL) { temp = T1; while (temp->right) temp = temp->right; temp->right = T; return T1; } else return T; } else return NULL; }
Threaded Tree
insert
public void threadedInsert(int el) {
IntThreadedNode newNode = new IntThreadedNode(el);
If (root == null) { // tree is empty
root = newNode;
return;}
IntThreadedNode p = root, prev = null;
while (p != null) { // find a place to insert newNode;
prev = p;
if (el < p.key)
p = p.left;
else if (!p.Successor) // go to the right only if it is
p = p.right; // a descendant, not a successor;
else break; // don't follow successor link;
}
if (el < prev.key) { // if newNode is left child of
prev.left = newNode; // its parent, the parent
newNode.Successor = true;// also becomes its successor;
newNode.right = prev; }
else if (prev.Successor) { // if parent of the newNode
newNode.Successor = true;// is not the rightmost node,
prev.Successor = false; // make parent's successor
newNode.right = prev.right; // newNode’s successor,
prev.right = newNode;}
else prev.right = newNode; // otherwise it has no successory;
} //
inorder
protected void threadedInorder( ) {
IntThreadedNode prev, p = root;
if (p != null) { //process only nonempty trees;
while (p.left != null) // go to the leftmost node;
p = p.left;
while (p !=null) {
p.visit( );
prev = p;
p = p.right; //go to the right node
if (p != null && !prev.successor) // if it is a descendant,go to the leftmost node,
while (p.left != null) p = p.left;
}// while (p !=null)
} // if
}
