Perfect Binary Tree and Complete Binary Tree

As per Wikipedia, following are the definitions of Perfect Binary Tree and Complete Binary Tree. http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

# A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. (This is ambiguously also called a complete binary tree.)
# A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
# A full bt --> a binary tree T is full if each node is either a leaf or possesses exactly two child nodes.
# AVL tree*: a binary search tree in which the heights of the left and right subtrees of the root differ by at most 1, and in which the left and right subtrees are themselves AVL trees.
Each AVL tree node has an associated balance factor indicating the relative heights of its subtrees (left-higher, equal, right-higher). Normally, this adds one data element to each tree node and an enumerated type is used.
How effective is this? The height of an AVL tree with N nodes never exceeds 1.44 log N and is typically much closer to log N.

Full Binary Tree Theorem ===> Theorem: Let T be a nonempty, full binary tree Then:
(a) If T has I internal nodes, the number of leaves is L = I + 1.
(b) If T has I internal nodes, the total number of nodes is N = 2I + 1.
(c) If T has a total of N nodes, the number of internal nodes is
I = (N – 1)/2.
(d) If T has a total of N nodes, the number of leaves is L = (N + 1)/2.
(e) If T has L leaves, the total number of nodes is N = 2L – 1.
(f) If T has L leaves, the number of internal nodes is I = L – 1.

Basically, this theorem says that the number of nodes N, the number of leaves
L, and the number of internal nodes I are related in such a way that if you
know any one of them, you can determine the other two.

Theorem: Let T be a binary tree of with      levels. Then the number of leaves is at most 2 -1.

Theorem: Let T be a binary tree of with      levels and L leaves. Then the number of levels is at least log L + 1.

Following Tree is a complete binary tree , but not perfect binary tree.

                      A
                  /     \
                B        C
              / \
            D   E

Following Tree is perfect binary tree , but not complete binary tree.

                      A
                  /     \
                B        C
               /         / \
             F         D   E

A good Source for introducing tree:
http://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=1Fysv60tefW_4QeMPiCVsM8YAEnz10DVCbxr98CwF1hh0IWuOn1IlcEGkx9Mv&hl=en&authkey=CIuUiSg

Array Representation

A complete binary tree has a simple array representation. Suppose we number the nodes from left to right, beginning at the top and ending at the bottom. Then we can store the various data items in the corresponding elements of an array. For example

can be represented by the array

This in fact corresponds to the level order enumeration of the tree. Note that we only use an initial segment of the array. Provided the array is long enough, and we know the number of tree nodes, it doesn't matter how many unused components there are at the end.

Arithmetic of Tree Traversal

An important benefit of the array representation is that we can move around the tree, from parent to children or from child to parent, by simple arithmetic. In general

• the children of node are at and
• the parent of node is at

where division, to obtain the parent, returns the integer part. Of course node may not have any children, or it may only have one child. Suppose there are nodes in the tree. Then node has a left child if and a right child if . Conversely, node has a parent if , otherwise it is the root.

You should note that some authors leave the first element of the array empty, so that the data items are stored in elements . The children are then at and and the parent is at . This might make for slightly more efficient code, but overall our coding will be simpler if we load the array from .

In a BST, insertion is always at the leaf level. Traverse the BST, comparing the new value to existing ones, until you find the right spot, then add a new leaf node holding that value.
Because of the key ordering imposed by a BST, searching resembles the
binary search algorithm on a sorted array, which is O(log N) for an array of N
elements.

Deletion is perhaps the most complex operation on a BST, because the algorithm must result in a BST. The question is: what value should replace the one deleted? As with the general tree, we have cases:
- Removing a leaf node is trivial, just set the relevant child pointer in the parent node to NULL.
- Removing an internal node which has only one subtree is also trivial, just set the relevant child pointer in the parent node to target the root of the subtree.
- Removing an internal node which has two subtrees

Simply removing the node would disconnect the tree. But what value should replace the one in the targeted node?
To preserve the BST property, we must take the smallest value from the right subtree, which would be the closest succcessor of the value being deleted.
Fortunately, the smallest value will always lie in the left-most node of the subtree.

So, we first find the left-most node of the right subtree, and then swap data values between it and the targeted node.
So, we first find the left-most node of the right subtree, and then swap data values between it and the targeted node.
Note that at this point we don't necessarily have a BST. Now we must delete the swapped value from the right subtree.
That looks straightforward here since the node in question is a leaf. However…
- the node will NOT be a leaf in all cases
- the occurrence of duplicate values is a complicating factor (so we might want to have a DeleteRightMinimum() function to clean up at thispoint).


Binary search trees provide O(log N) search times provided that the nodes are distributed in a reasonably "balanced" manner. Unfortunately, that is not always the case and performing a sequence of deletions and insertions can often exacerbate the problem. When a BST becomes badly unbalanced, the search behavior can degenerate to that of a sorted linked list, O(N).
There are a number of strategies for dealing with this problem; most involve adding some sort of restructuring to the insert/delete algorithms. That can be effective only if the restructuring reduces the average depth of a node from the root of the BST, and if the cost of the restructuring is, on average, O(log N).

A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.
(nots that only compare with its children)
(because it's complet,--> can be represented in array,  2k+1, 2k+2)
To build a heap:::The fact that a heap is a complete binary tree allows it to be efficiently
represented using a simple array.

- start with the last internal node (this is by see the lengh of the array, and compare with 2k+1/ or 2k+2, to check one element has the children or not, if has, it's 2k+1/ or 2k+2 will be within the lengh of the array )
- swap the current internal node withits larger child, if necessary
- then follow the swapped node down
- continue until all internal nodes are done

The cost of building a heap of N nodes is O(N) in both comparision and swaps

A list can be sorted by first building it into a heap, and then iteratively deleting the root node from the heap until the heap is empty.  If the deleted roots are  stored in reverse order in an array they will be sorted in ascending order (if a  max heap is used).

A priority queue consists of entries, each of which contains a key field, called the priority of the entry.
Aside from the usual operations of creation, clearing, tests forfull and empty,  and reporting its size, a priority queue has only two operations:
-insertion of a new entry
-removal of the entry having the largest (or smallest) key

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

http://geeksforgeeks.org/forum/topic/perfect-binary-and-complete-binary-trees#post-11378