Data Structure

♠ Posted by Unknown in Data Structure at 04:22

Binary Tree Array Representation

Binary Tree Represented as Arrays:

     In the Array representation, The binary tree nodes are stored in an array and are not linked by references.

The position of the node in the array corresponds to its position in the tree. The node at index 0 is the root node, the node at index 1 is the root's leftchild, and so on, progressing from left to right along each level of the tree. 

Adding a node at a given position in the tree means inserting the node into the equivalent cell in the array. Cells representing tree positions with no nodes are filled with 0 or null.

With this manner, a node's children and parent can be found by applying some simple arithmetic equation to the node's index number in the array.

For Left-Child : leftchild index = (2*parent index) + 1

For Right-Child : rightchild index = (2*parent index) + 2

For Current Node's Parent : Current Node's parent index = (Current Index - 1) / 2 [Where / represent integer division]


Disadvantage:
     In Delete operation, Unfilled nodes and deleted nodes leave holes in the array, wasting memory. Even worse, when deletion of a node involves moving subtrees, every node in the subtree must be moved to its new location in the array, which is time-consuming in large trees.

     In insert operation, duplicate key value is inserted as right child of its twin. The problem is that the search() method will find only the first two duplicate nodes. To find, more than two duplicates would be somewhat time-consuming.