TREE DATA STRUCTURE
Definition: A tree is a finite set of one or more nodes such that:�(1) There is a specially designated node called the root.�(2) The remaining nodes are partitioned into n > 0 disjoint sets T1, • • Tn , where each of these sets is a tree. We call T1, • • Tn the subtrees of the root �
Representation of the Tree
BINARY TREES �
Definition: A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree
typedef struct node tree_pointer;�typedef struct node
{�int data;�tree_pointer left_child;
tree_pointer right_chiId;�};
A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d
A strictly binary tree of
struct node *deleteElement(struct node *tree, int val)
{
struct node *cur, *parent, *suc, *psuc, *ptr;
if(tree–>left==NULL)
{
printf("\n The tree is empty "); return(tree);
}
parent = tree; cur = tree–>left;
while(cur!=NULL && val!= cur–>data) {
parent = cur;
cur = (val<cur–>data)? cur–>left:cur–>right; }
if(cur == NULL) {
printf("\n The value to be deleted is not present in the tree"); return(tree);
}
if(cur–>left == NULL) ptr = cur–>right;
else if(cur–>right == NULL)
ptr = cur–>left;
else {
// Find the in–order successor and its parent psuc = cur;
cur = cur–>left;
while(suc–>left!=NULL) {
psuc = suc; suc = suc–>left;
}
if(cur==psuc)
{
// Situation 1
suc–>left = cur–>right;
} else {
// Situation 2
suc–>left = cur–>left; psuc–>left = suc–>right; suc–>right = cur–>right;
}
ptr = suc;
}
// Attach ptr to the parent node
if(parent–>left == cur)
parent–>left=ptr; else
parent–>right=ptr; free(cur);
return tree; } �
Delete Node From BST
void inorder(tree_ointer ptr)�/ * In order tree traversal * /�{�if (ptr)
{�inorder(ptr->left_child);�printf("%d", ptr->data) ;�inorder(ptr->right_child);�}�}
void preorder(tree_pointer ptr)�/ * preorder tree traversal */ �{�if (ptr) {�printf(“%d", ptr->data) ; �preorder(ptr—>left_child) ;�preorder(ptr—>right_child) ;
}
}�
void postorder{tree_pointer ptr)�/ * postorder tree traversal */�{�if (ptr)
{�postorder(ptr->left_child);�postorder(ptr->right_child) ;�printf {"%d'‘, ptr->data) ;�}�} �
void iter_inorder(tree_pointer node)
{
int top = -1; / * initialize stack */
tree_pointer stack[MAX_STACK_SIZE];
for (;;)
{
for(; node; node=node->left_child)
add(&top, node);
node = delete(&top);
if (!node) break;
printf("%d", node->data);
node =node—>right_child;
}
}
Level Order Traversing
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
tree_pointer copy(tree_pointer original)
/*this function returns a tree—pointer to an exact copy of the original tree*/
{
tree_pointer temp;
if (original) {
temp=(tree_pointer) malloc(sizeof(node));
if (IS_FULL(temp))
{
fprintf(stderr, "The memory is full\n");
exit(1);
}
temp->left_child = copy(original->left_child);
temp->right_child = copy(original->right_child);
temp->data = original->data;
return temp;
}
return NULL;
}
tree_pointer swap(tree_pointer original)
/*this function returns a tree—pointer to swapped copy original tree*/
{
tree_pointer temp;
if (original) {
temp=(tree_pointer) malloc(sizeof(node));
if (IS_FULL(temp))
{
fprintf(stderr, "The memory is full\n");
exit(1);
}
temp->left_child = swap(original->right_child);
temp->right_child = swap(original->left_child);
temp->data = original->data;
return temp;
}
return NULL;
}
WINNER TREE
LOSER Tree
Counting Binary Trees
Advantages of Threaded Binary Tree
1. It enables linear traversal of elements in the tree.
2. Linear traversal eliminates the use of stacks which in turn consume a lot of memory space and computer time.
3. It enables to find the parent of a given element without explicit use of parent pointers.
4. Since nodes contain pointers to in-order predecessor and successor, the threaded tree enables forward and backward traversal of the nodes as given by in-order fashion.
AVL TREES
AVL tree is a self-balancing binary search tree invented by G.M. Adelson-Velsky and E.M. Lendis
In an AVL tree, the heights of the two sub-trees of a node may differ by at most one.
Due to this property, the AVL tree is also known as a height-balanced tree.
Balance factor = Height (left sub-tree) – Height (right sub-tree)
AVL tree stores an additional variable called the Balance Factor at every node.
Every node has a balance factor associated with it
A binary search tree in which every node has a balance factor of –1, 0, or 1 is said to be height balanced �Left-heavy : Balance factor is 1 ( Left side up by 1 level)
Right-heavy : Balance factor is -1 ( Right side is up by 1 level)
LL rotation The new node is inserted in the left sub-tree of the left sub-tree of the critical node.
RR rotation The new node is inserted in the right sub-tree of the right sub-tree of the critical node.
LR rotation The new node is inserted in the right sub-tree of the left sub-tree of the critical node.
RL rotation The new node is inserted in the left sub-tree of the right sub-tree of the critical node
R0 Rotation: Performe3d to delete a node which has balance factor 0 ( Similar to LL rotation)
R1 Rotation: Is applied to delete a node having balance factor 1
R-1 Rotation: Is applied to delete a node having balance factor -1 close to critical node
RED-BLACK TREEs
A red-black tree is a self-balancing binary search tree
A red-black tree is a binary search tree in which every node has a colour which is either red or black.
The red-black tree has the following additional requirements:
1. The colour of a node is either red or black.
2. The colour of the root node is always black.
3. All leaf nodes are black.
4. Every red node has both the children coloured in black.
5. Every simple path from a given node to any of its leaf nodes has an equal number of black
nodes.
A splay tree is a self-balancing binary search tree with an additional property that recently accessed elements can be re-accessed fast. It is said to be an efficient binary tree because it performs basic operations such as insertion, search, and deletion in O(log(n)) amortized time.
A splay tree consists of a binary tree, with no additional fields �
When a node in a splay tree is accessed, it is rotated or ‘splayed’ to the root, thereby changing the structure of the tree �
frequently accessed node is always moved closer to the starting point of the search �
Splaying
When we access a node N, splaying is performed on N to move it to the root �Each splay step depends on three factors: ∑ Whether N is the left or right child of its parent P, ∑ Whether P is the root or not, and if not,
Whether P is the left or right child of its parent, G (N’s grandparent).
Zig step The zig operation is done when P (the parent of N)
is the root of the splay tree. In the zig step, the tree is rotated on the edge between N and P.
Zig-zig step The zig–zig operation is performed when P is not the root. In addition to this, N and P are either both right or left children of their parents. �
Zig-zag step The zig–zag operation is performed when P is not the root. In addition to this, N is the right child of P and P is the left child of G or vice versa.