2-3Tree@ADS(EXP3)

21:54 | Posted by b.phanikrishna |
Experiment No:
3
Name of the Experiment:
To perform various operations i.e., insertions and deletions on 2-3 trees.

Aim: To perform various operations i.e., insertions and deletions on 2-3 trees.
Hardware Software Requirements:
Ø  Intel based desktop PC
Ø  Minimum of 166 MHZ or Faster processor
Ø  At least 256 MB Ram
Ø  At least 512 MB hard-disk with at least 100 MB free of disk place
Ø  C Compiler (Turbo-c) or C++ Compiler (Turbo-C++)
Description:
The 2-3 tree is a B-tree of order 3. It gets its name because each non-root node has either two or three sub-trees (the root may have zero, two, or three sub-trees).
 a 2–3 tree is a type of data structure, a tree where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements

 Properties
Ø  Every non-leaf is a 2-node or a 3-node. A 2-node contains one data item and has two children. A 3-node contains two data items and has 3 children.
Ø  All leaves are at the same level (the bottom level)
Ø  All data are kept in sorted order
Ø  Every leaf node will contain 1 or 2 fields.
Ø  Information (keys and associated data) is stored only at leaves (internal nodes are for organization only).
Ø  Keys at leaves are ordered left to right.
Ø  In addition to child pointers, each internal node stores:
o   the value of the max key in the left subtree (leftMax)
o   the value of the max key in the middle subtree (middleMax)
Ø  If a node only has 2 children, they are left and middle (not left and right) children.








Draw two different 2-3 trees, both containing the letters A through G as key values.

Operations on a 2-3 Tree:
The lookup operation
Recall that the lookup operation needs to determine whether key value k is in a 2-3 tree T. The lookup operation for a 2-3 tree is very similar to the lookup operation for a binary-search tree. There are 2 base cases:
  1. T is empty: return false
  2. T is a leaf node: return true iff the key value in T is k
And there are 3 recursive cases:
  1. k <= T.leftMax: look up k in T's left subtree
  2. T.leftMax < k <= T.middleMax: look up k in T's middle subtree
  3. T.middleMax < k: look up k in T's right subtree
It should be clear that the time for lookup is proportional to the height of the tree. The height of the tree is O(log N) for N = the number of nodes in the tree. You may think this is a problem, since the actual values are only at the leaves. However, the number of leaves is always greater than N/2 (i.e., more than half the nodes in the tree are leaves). So the time for lookup is also O(log M), where M is the number of key values stored in the tree.
The insert operation
The goal of the insert operation is to insert key k into tree T, maintaining T's 2-3 tree properties. Special cases are required for empty trees and for trees with just a single (leaf) node. So the form of insert will be:
           if T is empty replace it with a single node containing k
           else if T is just 1 node m:
                       (a) create a new leaf node n containing k
                               (b) create a new internal node with m and n as its children,
                                   and with the appropriate values for leftMax and middleMax
           else call auxiliary method insert(T, k)
The auxiliary insert method is the recursive method that handles all but the 2 special cases; as for binary-search trees, the first task of the auxiliary method is to find the (non-leaf) node that will be the parent of the newly inserted node.
The auxiliary insert method performs the following steps to find node n, the parent of the new node:
  • base case: T's children are leaves - n is found! (T will be the parent of the new node)
  • recursive cases:
    • k < T.leftMax: insert k into T's left subtree
    • T.leftMax < k < T.middleMax, or T only has 2 children: insert k into T's middle subtree
    • k > T.middleMax and T has 3 children: insert k into T's right subtree
Once n is found, there are two cases, depending on whether n has room for a new child:
Case 1: n has only 2 children
  • Insert k as the appropriate child of n:
    1. if k < n.leftMax, then make k n's left child (move the others over), and fix the values of n.leftMax and n.middleMax. Note that all ancestors of n still have correct values for their leftMax and middleMax fields (because the new value is not the "max" child of n).
    2. if k is between n.leftMax and n.middleMax, then make k n's middle child and fix the value of n.middleMax. Again, no ancestors of n need to have their fields changed.
    3. if k > n.middleMax, then make k n's right child and fix the leftMax or middleMax fields of n's ancestors as needed.
Case 2: n already has 3 children
  • Make k the appropriate new child of n, anyway (fixing the values of n.leftMax and/or n.middleMax as needed). Now n has 4 children.
  • Create a new internal node m. Give m n's two rightmost children and set the values of m.leftMax and m.middleMax.
  • Add m as the appropriate new child of n's parent (i.e., add m just to the right of n). If n's parent had only 2 children, then stop creating new nodes, just fix the values of the leftMax and middleMax fields of ancestors as needed. Otherwise, keep creating new nodes recursively up the tree. If the root is given 4 children, then create a new node m as above, and create a new root node with n and m as its children.
What is the time for insert? Finding node n (the parent of the new node) involves following a path from the root to a parent of leaves. That path is O(height of tree) = O(log N), where N is the number of nodes in the tree (recall that it is also log M, where M is the number of key values stored in the tree).
Once node n is found, finishing the insert, in the worst case, involves adding new nodes and/or fixing fields all the way back up from the leaf to the root, which is also O(log N).
So the total time is O(log N), which is also O(log M).
Draw the 2-3 tree that results from inserting the value "C" into the following 2-3 tree:


=====================================================

Now draw the tree that results from adding the value "F" to the tree you drew for above question

The delete operation
Deleting key k is similar to inserting: there is a special case when T is just a single (leaf) node containing k (T is made empty); otherwise, the parent of the node to be deleted is found, then the tree is fixed up if necessary so that it is still a 2-3 tree.
Once node n (the parent of the node to be deleted) is found, there are two cases, depending on how many children n has:
case 1: n has 3 children
  • Remove the child with value k, then fix n.leftMax, n.middleMax, and n's ancestors' leftMax and middleMax fields if necessary.
case 2: n has only 2 children
  • If n is the root of the tree, then remove the node containing k. Replace the root node with the other child (so the final tree is just a single leaf node).
  • If n has a left or right sibling with 3 kids, then:
    • remove the node containing k
    • "steal" one of the sibling's children
    • fix n.leftMax, n.middleMax, and the leftMax and middleMax fields of n's sibling and ancestors as needed.
  • If n's sibling(s) have only 2 children, then:
    • remove the node containing k
    • make n's remaining child a child of n's sibling
    • fix leftMax and middleMax fields of n's sibling as needed
    • remove n as a child of its parent, using essentially the same two cases (depending on how many children n's parent has) as those just discussed
The time for delete is similar to insert; the worst case involves one traversal down the tree to find n, and another "traversal" up the tree, fixing leftMax and middleMax fields along the way (the traversal up is really actions that happen after the recursive call to delete has finished).
So the total time is 2 * height-of-tree = O(log N).
Question 1: Draw the 2-3 tree that results from deleting the value "X" from the following 2-3 tree:

================================================



Question 2: Now draw the tree that results from deleting the value "H" from the tree you drew for question 1.




2-3 Tree Summary
In a 2-3 tree:
  • keys are stored only at leaves, ordered left-to-right
  • non-leaf nodes have 2 or 3 children (never 1)
  • non-leaf nodes also have leftMax and middleMax values (as well as pointers to children)
  • all leaves are at the same depth
  • the height of the tree is O(log N), where N = # nodes in tree
  • at least half the nodes are leaves, so the height of the tree is also O(log M) for M = # values stored in tree
  • the lookup, insert, and delete methods can all be implemented to run in time O(log N), which is also O(log M)
Summary of Binary-Search Trees vs 2-3 Trees
BST
2-3 Tree
where are values stored
every node
leaves only
extra info in non-leaf nodes
2 child ptrs
leftMax, middleMax, 3 child ptrs
worst-case time for lookup, insert, and delete (N = # values stored in tree)
O(N)
O(log N)
average-case time for lookup, insert, and delete (N = # values stored in tree)
O(log N)
O(log N)



PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define M 5
struct node
{
int n;   
int keys[M-1]; /*array of keys*/
struct node *p[M]; /* (n+1 pointers will be in use) */
}*root=NULL;

enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };

void insert(int key);
void display(struct node *root,int);
void DelNode(int x);
void search(int x);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
enum KeyStatus del(struct node *r, int x);

int main()
{
int key;
int choice;
clrscr();
printf("Creation of B tree for node %d\n",M);
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Search\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("Enter the key : ");
scanf("%d",&key);
insert(key);
break;
case 2:
printf("Enter the key : ");
scanf("%d",&key);
DelNode(key);
break;
case 3:
printf("Enter the key : ");
scanf("%d",&key);
search(key);
break;
case 4:
printf("Btree is :\n");
display(root,0);
break;
case 5:
exit(1);
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
//return 0;
getch();
}/*End of main()*/

void insert(int key)
{
struct node *newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key, &upKey, &newnode);
if (value == Duplicate)
printf("Key already available\n");
if (value == InsertIt)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/

enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
{
struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
enum KeyStatus value;
if (ptr == NULL)
{
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key, &newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than M-1 where M is order of B tree*/
if (n < M - 1)
{
pos = searchPos(newKey, ptr->keys, n);
/*Shifting the key and pointer right for inserting the new key*/
for (i=n; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum and position of node to be inserted is
last*/
if (pos == M - 1)
{
lastKey = newKey;
lastPtr = newPtr;
}
else /*If keys in node are maximum and position of node to be inserted
is not last*/
{
lastKey = ptr->keys[M-2];
lastPtr = ptr->p[M-1];
for (i=M-2; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M - 1)/2;
(*upKey) = ptr->keys[splitPos];

(*newnode)=malloc(sizeof(struct node));/*Right node after split*/
ptr->n = splitPos; /*No. of keys for left splitted node*/
(*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i < (*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n - 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n] = lastPtr;
return InsertIt;
}/*End of ins()*/

void display(struct node *ptr, int blanks)
{
if (ptr)
{
int i;
for(i=1;i<=blanks;i++)
printf(" ");
for (i=0; i < ptr->n; i++)
printf("%d ",ptr->keys[i]);
printf("\n");
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], blanks+10);
}/*End of if*/
}/*End of display()*/

void search(int key)
{
int pos, i, n;
struct node *ptr = root;
printf("Search path:\n");
while (ptr)
{
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf(" %d",ptr->keys[i]);
printf("\n");
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
{
printf("Key %d found in position %d of last dispalyed node\n",key,i);
return;
}
ptr = ptr->p[pos];
}
printf("Key %d is not available\n",key);
}/*End of search()*/

int searchPos(int key, int *key_arr, int n)
{
int pos=0;
while (pos < n && key > key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/

void DelNode(int key)
{
struct node *uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf("Key %d is not available\n",key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
break;
}/*End of switch*/
}/*End of delnode()*/

enum KeyStatus del(struct node *ptr, int key)
{
int pos, i, pivot, n ,min;
int *key_arr;
enum KeyStatus value;
struct node **p,*lptr,*rptr;

if (ptr == NULL)
return SearchFailure;
/*Assigns values of node*/
n=ptr->n;
key_arr = ptr->keys;
p = ptr->p;
min = (M - 1)/2;/*Minimum number of keys*/

pos = searchPos(key, key_arr, n);
if (p[0] == NULL)
{
if (pos == n || key < key_arr[pos])
return SearchFailure;
/*Shift keys and pointers left*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
}/*End of if */

if (pos < n && key == key_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
while(1)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
break;
qp = qp1;
}/*End of while*/
key_arr[pos] = qp->keys[nkey-1];
qp->keys[nkey - 1] = key;
}/*End of if */
value = del(p[pos], key);
if (value != LessKeys)
return value;

if (pos > 0 && p[pos-1]->n > min)
{
pivot = pos - 1; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pos];
/*Assigns values for right node*/
rptr->p[rptr->n + 1] = rptr->p[rptr->n];
for (i=rptr->n; i>0; i--)
{
rptr->keys[i] = rptr->keys[i-1];
rptr->p[i] = rptr->p[i-1];
}
rptr->n++;
rptr->keys[0] = key_arr[pivot];
rptr->p[0] = lptr->p[lptr->n];
key_arr[pivot] = lptr->keys[--lptr->n];
return Success;
}/*End of if */
if (pos > min)
{
pivot = pos; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pivot+1];
/*Assigns values for left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
key_arr[pivot] = rptr->keys[0];
lptr->n++;
rptr->n--;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] = rptr->keys[i+1];
rptr->p[i] = rptr->p[i+1];
}/*End of for*/
rptr->p[rptr->n] = rptr->p[rptr->n + 1];
return Success;
}/*End of if */

if(pos == n)
pivot = pos-1;
else
pivot = pos;

lptr = p[pivot];
rptr = p[pivot+1];
/*merge right node with left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
lptr->n = lptr->n + rptr->n +1;
free(rptr); /*Remove right node*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys;
}/*End of del()*/
OUTPUT:
Creation of B tree for node 5
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 2
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 4
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 7
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 10
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 12
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 15
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 20
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 1
Enter the key : 30

1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 4
Btree is :
7 15
          2 4
          10 12
          20 30
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 3
Enter the key : 12
Search path:
 7 15
 10 12
Key 12 found in position 2 of last dispalyed node
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 3
Enter the key : 15
Search path:
 7 15
Key 15 found in position 2 of last dispalyed node

1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 2
Enter the key : 30
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice : 4
Btree is :
7
          2 4
          10 12 15 20
1.Insert
2.Delete
3.Search
4.Display
5.Quit
Enter your choice :

For downloading:  Download
also View: ADS@LAB Full details
                  




Labels: , , , ,

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Copyright © . All Rights Reserved.

Blogger Template created with Artisteer by Patricia P..