10-07-2012, 04:17 PM
Binary Tree
Binary Tree.ppt (Size: 366 KB / Downloads: 130)
Binary Tree Definition
A binary tree T is a finite set of nodes with one of the following properties:
(a) T is a tree if the set of nodes is empty. (An empty tree is a tree.)
(b) The set consists of a root, R, and exactly two distinct binary trees, the left subtree TL and the right subtreeTR. The nodes in T consist of node R and all the nodes in TL and TR.
Opertions
Search the tree and remove item, if it is present; otherwise, take no action. Return the number of elements removed.
Postcondition: If item is located in the tree, the size of the tree decreases by 1.
void erase(iterator pos);
Erase the item pointed to the iterator pos.
Precondition: The tree is not empty and pos points to an item in the tree. If the iterator is invalid, the function throws the referenceError exception.
Postcondition: The tree size decreases by 1.
Binary Trees
Most effective as a storage structure if it has high density §- ie: data are located on relatively short paths from the root. §- A complete binary tree has the highest possible density
- an n-node complete binary tree has depth int(log2n).
- At the other extreme, a degenerate binary tree is equivalent to a linked list and exhibits O(n) access times.