( Java code) Design and implement an AVL tree node class that must support “inse
ID: 3852423 • Letter: #
Question
( Java code)
Design and implement an AVL tree node class that must support “insert”, and option-
ally “remove” operations.
Design and implement a Left-Leaning Red-Black tree node class that must support “insert”, and optionally “remove” operations.
Design and implement a main method that does the following:
(a) Create an array that contains a list of integers, in an ascending order, from 1 to a large enough number (e.g., 1000000 so that the running time of building a tree containing those numbers will be at least 1 second).
(b) Create an array that contains a list of integers that is the same as the 1st but in descending order (e.g., from 1000000 to 1).
(c) Create an array that has the same numbers as above, but the order of the numbers (e.g., 1 - 1000000) is random. You can use a random number generator to decide and put a number into the array.
(d) AVL-insert, into a separate AVL tree that is initially empty, the numbers in each array sequentially from the start to the end. Measure and print out the elapsed time of building each tree.
(e) RB-insert, into a separate LLRB tree that is initially empty, the number in each array sequentially from the start to the end. Measure and print out the elapsed time of building each tree.
Deliverables:
Source code.
Performance analysis document that will record, compare, and analyze the running times of building different AVL and LLRB trees.
Explanation / Answer
JAVA code for the given probloem:
package avltreetest;
/* Class to represent nodes of AVL tree*/
class NodeAVLTree
{
NodeAVLTree nodesLeft, nodesRight;
int inData;
int heightNode;
//class constructors
public NodeAVLTree()
{
nodesLeft = null;
nodesRight = null;
inData = 0;
heightNode = 0;
}
public NodeAVLTree(int inData)
{
nodesLeft = null;
nodesRight = null;
inData = inData;
heightNode = 0;
}
}
//class to create the AVL tree
class VAVLTree
{
private NodeAVLTree rootAVL;
public VAVLTree()
{
rootAVL = null;
}
//function to insert a node
public void insertAVLNode(int inData)
{
rootAVL = insertAVLNode(inData, rootAVL);
}
private int heightNode(NodeAVLTree vt )
{
return vt == null ? -1 : vt.heightNode;
}
private int findMax(int heightLeft, int heightRight)
{
return heightLeft > heightRight ? heightLeft : heightRight;
}
//To insert data
private NodeAVLTree insertAVLNode(int dat, NodeAVLTree tree1)
{
if (tree1 == null)
tree1 = new NodeAVLTree(dat);
else if (dat < tree1.inData)
{
tree1.nodesLeft = insertAVLNode( dat, tree1.nodesLeft );
if( heightNode( tree1.nodesLeft ) - heightNode( tree1.nodesRight ) == 2 )
if( dat < tree1.nodesLeft.inData )
tree1 = singleLeftRotation( tree1);
else
tree1 = rightLeftRot( tree1 );
}
else if( dat > tree1.inData )
{
tree1.nodesRight = insertAVLNode( dat, tree1.nodesRight );
if( heightNode( tree1.nodesRight ) - heightNode( tree1.nodesLeft ) == 2 )
if( dat > tree1.nodesRight.inData)
tree1 = rightRotatnSingle( tree1 );
else
tree1 = leftRightRot( tree1 );
}
else
;
tree1.heightNode = findMax( heightNode( tree1.nodesLeft ), heightNode( tree1.nodesRight ) ) + 1;
return tree1;
}
private NodeAVLTree singleLeftRotation(NodeAVLTree n1)
{
NodeAVLTree tempNode = n1.nodesLeft;
n1.nodesLeft = tempNode.nodesRight;
tempNode.nodesRight = n1;
n1.heightNode = findMax( heightNode( n1.nodesLeft ), heightNode( n1.nodesRight ) ) + 1;
tempNode.heightNode = findMax( heightNode( tempNode.nodesLeft ), n1.heightNode ) + 1;
return tempNode;
}
private NodeAVLTree rightRotatnSingle(NodeAVLTree tempNode)
{
NodeAVLTree n1 = tempNode.nodesRight;
tempNode.nodesRight = n1.nodesLeft;
n1.nodesLeft = tempNode;
tempNode.heightNode = findMax( heightNode( tempNode.nodesLeft ), heightNode( tempNode.nodesRight ) ) + 1;
n1.heightNode = findMax( heightNode( n1.nodesRight ), tempNode.heightNode ) + 1;
return n1;
}
private NodeAVLTree rightLeftRot(NodeAVLTree n3)
{
n3.nodesLeft = rightRotatnSingle( n3.nodesLeft );
return singleLeftRotation( n3 );
}
private NodeAVLTree leftRightRot(NodeAVLTree tempNode)
{
tempNode.nodesRight = singleLeftRotation( tempNode.nodesRight );
return rightRotatnSingle( tempNode );
}
public void AVLinord()
{
AVLinord(rootAVL);
}
private void AVLinord(NodeAVLTree treeNod)
{
if (treeNod != null)
{
AVLinord(treeNod.nodesLeft);
System.out.print(treeNod.inData +" ");
AVLinord(treeNod.nodesRight);
}
}
}
//Red Black tree node
class NodeRedBlack
{
NodeRedBlack RBleft, RBRight;
int NodeRBele;
int colorRB;
//class constructors
public NodeRedBlack(int insElem)
{
this( insElem, null, null );
}
public NodeRedBlack(int ele1, NodeRedBlack left1, NodeRedBlack right1)
{
RBleft = left1;
RBRight = right1;
NodeRBele = ele1;
colorRB = 1;
}
}
//Class to create the RB tree
class RBTreeCreat
{
private NodeRedBlack nodeCurr;
private NodeRedBlack nodeParent;
private NodeRedBlack nodeGrant;
private NodeRedBlack nodeGreat;
private NodeRedBlack nodeHead;
private static NodeRedBlack nodeTemp;
static
{
nodeTemp = new NodeRedBlack(0);
nodeTemp.RBleft = nodeTemp;
nodeTemp.RBRight = nodeTemp;
}
static final int COLORBLACK = 1;
static final int COLORRED = 0;
public RBTreeCreat(int verySmall)
{
nodeHead = new NodeRedBlack(verySmall);
nodeHead.RBleft = nodeTemp;
nodeHead.RBRight = nodeTemp;
}
//to insert an item
public void insertRBTree(int itemInser )
{
nodeCurr = nodeParent = nodeGrant = nodeHead;
nodeTemp.NodeRBele = itemInser;
while (nodeCurr.NodeRBele != itemInser)
{
nodeGreat = nodeGrant;
nodeGrant = nodeParent;
nodeParent = nodeCurr;
nodeCurr = itemInser < nodeCurr.NodeRBele ? nodeCurr.RBleft : nodeCurr.RBRight;
//check two childre
if (nodeCurr.RBleft.colorRB == COLORRED && nodeCurr.RBRight.colorRB == COLORRED)
reOrientTree( itemInser );
}
//if already presnt then fails
if (nodeCurr != nodeTemp)
return;
nodeCurr = new NodeRedBlack(itemInser, nodeTemp, nodeTemp);
if (itemInser < nodeParent.NodeRBele)
nodeParent.RBleft = nodeCurr;
else
nodeParent.RBRight = nodeCurr;
reOrientTree( itemInser );
}
private void reOrientTree(int itemInser)
{
nodeCurr.colorRB = COLORRED;
nodeCurr.RBleft.colorRB = COLORBLACK;
nodeCurr.RBRight.colorRB = COLORBLACK;
if (nodeParent.colorRB == COLORRED)
{
nodeGrant.colorRB = COLORRED;
if (itemInser < nodeGrant.NodeRBele != itemInser < nodeParent.NodeRBele)
nodeParent = rotateRBTree( itemInser, nodeGrant ); // Start dbl rotateRBTree
nodeCurr = rotateRBTree(itemInser, nodeGreat );
nodeCurr.colorRB = COLORBLACK;
}
nodeHead.RBRight.colorRB = COLORBLACK;
}
private NodeRedBlack rotateRBTree(int itemInser, NodeRedBlack nodeParent)
{
if(itemInser < nodeParent.NodeRBele)
return nodeParent.RBleft = itemInser < nodeParent.RBleft.NodeRBele ? RBTLeftRotation(nodeParent.RBleft) : RBTRightRotation(nodeParent.RBleft) ;
else
return nodeParent.RBRight = itemInser < nodeParent.RBRight.NodeRBele ? RBTLeftRotation(nodeParent.RBRight) : RBTRightRotation(nodeParent.RBRight);
}
private NodeRedBlack RBTLeftRotation(NodeRedBlack n1)
{
NodeRedBlack tempNode = n1.RBleft;
n1.RBleft = tempNode.RBRight;
tempNode.RBRight = n1;
return tempNode;
}
private NodeRedBlack RBTRightRotation(NodeRedBlack tempNode)
{
NodeRedBlack n1 = tempNode.RBRight;
tempNode.RBRight = n1.RBleft;
n1.RBleft = tempNode;
return n1;
}
}
//class to test
public class AvlTreeTest
{
public static void main(String[] args)
{
VAVLTree obj1 = new VAVLTree();
RBTreeCreat objRB=new RBTreeCreat(-1);
int[] itemArr=new int[100];
for(int tempNode=0;tempNode<100;tempNode++)
{
itemArr[tempNode]=tempNode+1;
}
System.out.println(" Insert: ");
long avl1=System.nanoTime();
for(int tempNode=0;tempNode<100;tempNode++)
{
obj1.insertAVLNode( itemArr[tempNode]);
}
long endAVL=System.nanoTime();
long a1=System.nanoTime();
for(int tempNode=0;tempNode<100;tempNode++)
{
objRB.insertRBTree(itemArr[tempNode]);
}
long RBend=System.nanoTime();
System.out.println("Inserted in Ascending order in AVL tree:"+(endAVL-avl1));
System.out.println("Insertion in RB tree in acending order:"+(RBend-a1));
System.out.println(" Insertion in desceding order ");
int n1=0;
for(int tempNode=100;tempNode>0;tempNode--)
{
itemArr[n1++]=tempNode;
}
avl1=System.nanoTime();
for(int tempNode=0;tempNode<100;tempNode++)
{
obj1.insertAVLNode( itemArr[tempNode]);
}
endAVL=System.nanoTime();
a1=System.nanoTime();
for(int tempNode=0;tempNode<100;tempNode++)
{
objRB.insertRBTree(itemArr[tempNode]);
}
RBend=System.nanoTime();
System.out.println("Insertion in AVL tree desceding"+(endAVL-avl1));
System.out.println("Insertion in RB tree desceding"+(RBend-a1));
}
}
Sample Run:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.