Latest Tutorials| Questions and Answers|Ask Questions?|Site Map



Home Answers Viewqa Java-Beginners Avl tre problem code
Login         

View Questions and Answers by Category

Advertisements


 
Have Programming Question? Ask it here!
 
 
 


Fatma
Avl tre problem code
0 Answer(s)      4 years and 11 months ago
Posted in : Java Beginners


package DataStructures;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order

/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
package org.apache.commons.collections.list;

import java.util.AbstractList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;

import org.apache.commons.collections.OrderedIterator;
public class avl{

/**
* A List implementation that is optimised for fast insertions and
* removals at any index in the list.
*
* This list implementation utilises a tree structure internally to ensure that
* all insertions and removals are O(log n). This provides much faster performance
* than both an ArrayList and a LinkedList where elements
* are inserted and removed repeatedly from anywhere in the list.
* public class TreeList extends AbstractList {
// add; toArray; iterator; insert; get; indexOf; remove
// TreeList = 1260;7360;3080; 160; 170;3400; 170;
// ArrayList = 220;1480;1760; 6870; 50;1540; 7200;
// LinkedList = 270;7360;3350;55860;290720;2910;55200;

/** The root node in the AVL tree */
private AVLNode root;

/** The current size of the list */
private int size;

//-----------------------------------------------------------------------
/**
* Constructs a new empty list.
*/
public TreeList() {
super();

}

/**
* Constructs a new empty list that copies the specified list.
*
* @param coll the collection to copy
* @throws NullPointerException if the collection is null
*/
public TreeList(Collection coll) {
super();
addAll(coll);
}

//-----------------------------------------------------------------------
/**
* Gets the element at the specified index.
*
* @param index the index to retrieve
* @return the element at the specified index
*/
public Object get(int index) {
checkInterval(index, 0, size() - 1);
return root.get(index).getValue();
}

/**
* Gets the current size of the list.
*
* @return the current size
*/
public int size() {
return size;
}

/**
* Gets an iterator over the list.
*
* @return an iterator over the list
*/
public Iterator iterator() {
// override to go 75% faster
return listIterator(0);
}

/**
* Gets a ListIterator over the list.
*
* @return the new iterator
*/
public ListIterator listIterator() {
// override to go 75% faster
return listIterator(0);
}

/**
* Gets a ListIterator over the list.
*
* @param fromIndex the index to start from
* @return the new iterator
*/
public ListIterator listIterator(int fromIndex) {
// override to go 75% faster
// cannot use EmptyIterator as iterator.add() must work
checkInterval(fromIndex, 0, size());
return new TreeListIterator(this, fromIndex);
}

/**
* Searches for the index of an object in the list.
*
* @return the index of the object, -1 if not found
*/
public int indexOf(Object object) {
// override to go 75% faster
if (root == null) {
return -1;
}
return root.indexOf(object, root.relativePosition);
}

/**
* Searches for the presence of an object in the list.
*
* @return true if the object is found
*/
public boolean contains(Object object) {
return (indexOf(object) >= 0);
}

/**
* Converts the list into an array.
*
* @return the list as an array
*/
public Object[] toArray() {
// override to go 20% faster
Object[] array = new Object[size()];
if (root != null) {
root.toArray(array, root.relativePosition);
}
return array;
}

//-----------------------------------------------------------------------
/**
* Adds a new element to the list.
*
* @param index the index to add before
* @param obj the element to add
*/
public void add(int index, Object obj) {
modCount++;
checkInterval(index, 0, size());
if (root == null) {
root = new AVLNode(index, obj, null, null);
} else {
root = root.insert(index, obj);
}
size++;
}

/**
* Sets the element at the specified index.
*
* @param index the index to set
* @param obj the object to store at the specified index
* @return the previous object at that index
* @throws IndexOutOfBoundsException if the index is invalid
*/
public Object set(int index, Object obj) {
checkInterval(index, 0, size() - 1);
AVLNode node = root.get(index);
Object result = node.value;
node.setValue(obj);
return result;
}

/**
* Removes the element at the specified index.
*
* @param index the index to remove
* @return the previous object at that index
*/
public Object remove(int index) {
modCount++;
checkInterval(index, 0, size() - 1);
Object result = get(index);
root = root.remove(index);
size--;
return result;
}

/**
* Clears the list, removing all entries.
*/
public void clear() {
modCount++;
root = null;
size = 0;
}

//-----------------------------------------------------------------------
/**
* Checks whether the index is valid.
*
* @param index the index to check
* @param startIndex the first allowed index
* @param endIndex the last allowed index
* @throws IndexOutOfBoundsException if the index is invalid
*/
private void checkInterval(int index, int startIndex, int endIndex) {
if (index < startIndex || index > endIndex) {
throw new IndexOutOfBoundsException("Invalid index:" + index + ", size=" + size());
}
}
}

public class AvlTree

{
private AvlTree t;
/**
* Construct the tree.
*/
public AvlTree( )
{
root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( Comparable x )
{
root = insert( x, root );
}

/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( Comparable x )
{
System.out.println( "Sorry, remove unimplemented" );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( )
{
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public Comparable findMax( )
{
return elementAt( findMax( root ) );
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x )
{
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}

/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}

/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( AvlNode t )
{
return t == null ? null : t.element;
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
*/
private AvlNode insert( Comparable x, AvlNode t )
{
if( t == null )
t = new AvlNode( x, null, null );
else if( x.compareTo( t.element ) < 0 )
{
t.left = insert( x, t.left );
if( height( t.left ) - height( t.right ) == 2 )
if( x.compareTo( t.left.element ) < 0 )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( x.compareTo( t.element ) > 0 )
{
t.right = insert( x, t.right );
if( height( t.right ) - height( t.left ) == 2 )
if( x.compareTo( t.right.element ) > 0 )
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private AvlNode findMin( AvlNode t )
{
if( t == null )
return t;

while( t.left != null )
t = t.left;
return t;
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private AvlNode findMax( AvlNode t )
{
if( t == null )
return t;

while( t.right != null )
t = t.right;
return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private AvlNode find( Comparable x, AvlNode t )
{
while( t != null )
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match

return null; // No match
}

/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( AvlNode t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}

/**
* Return the height of node t, or -1, if null.
*/
private static int height( AvlNode t )
{
return t == null ? -1 : t.height;
}

/**
* Return maximum of lhs and rhs.
*/
private static int max( int lhs, int rhs )
{
return lhs > rhs ? lhs : rhs;
}

/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then return new root.
*/
private static AvlNode rotateWithLeftChild( AvlNode k2 )
{
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = max( height( k1.left ), k2.height ) + 1;
return k1;
}

/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then return new root.
*/
private static AvlNode rotateWithRightChild( AvlNode k1 )
{
AvlNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = max( height( k2.right ), k1.height ) + 1;
return k2;
}

/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then return new root.
*/
private static AvlNode doubleWithLeftChild( AvlNode k3 )
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}

/**
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child.
* For AVL trees, this is a double rotation for case 3.
* Update heights, then return new root.
*/
private static AvlNode doubleWithRightChild( AvlNode k1 )
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}

/** The tree root. */
private AvlNode root;


// Test program
public static void main( String [ ] args )
{
AvlTree t = new AvlTree( );

final int NUMS = 4000;
final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new MyInteger( i ) );

if( NUMS < 40 )
t.printTree( );
if( ((MyInteger)(t.findMin( ))).intValue( ) != 1 ||
((MyInteger)(t.findMax( ))).intValue( ) != NUMS - 1 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 1; i < NUMS; i++ )
if( ((MyInteger)(t.find( new MyInteger( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );
}
}

Advertisement
View Answers

Related Tutorials/Questions & Answers:
Avl tre problem code - Java Beginners
Avl tre problem code   package DataStructures... /** * Implements an AVL tree. * Note that all "matching" is based on the compareTo...; import org.apache.commons.collections.OrderedIterator; public class avl
project on avl tree and hashing
data i must write code that i building avl tree and in every node there are info...project on avl tree and hashing   I want to make graphical interface... code
Advertisements
project on avl tree and hashing
data i must write code that i building avl tree and in every node there are info...project on avl tree and hashing   I want to make graphical interface... code
Project on avl tree and hashing
data i must write code that i building avl tree and in every node...Project on avl tree and hashing   I want to make graphical interface... order ,,,and every button must run thats mean i want to write whole code please help
about avl tree and hashing
i must write code that i building avl tree and in every node there are three...about avl tree and hashing   I want to make graphical interface... ,,,and every button must run thats mean i want to write whole code
project on avl tree and hashing
data i must write code that i building avl tree and in every node there are info...project on avl tree and hashing   I want to make graphical interface... code
about avl tree and hashing
must write code that i building avl tree and in every node there are three...about avl tree and hashing  I want to make graphical interface... ,,,and every button must run thats mean i want to write whole code
project on avl tree and hashing
code that i building avl tree and in every node there are info about bank name... ,,,and every button must run thats mean i want to write whole code
code problem:ajax - Ajax
code problem:ajax  Hi,I am using ajax to populate a select box.for this I am writing out.write("ONE"); like that.it runs fine in firefox.bt not in IE.Can anyone help me out this... thanks
Hibernate code problem - Hibernate
Hibernate code problem  Hi, This is Birendra Pradhan.I want... in the DAO.Can it be possibe. Please send some sample code.. thanks & Regards Birendra  Hi friend, For solving the problem visit
problem with code - Ajax
problem with code  hi friends i am sending a code in that when we... to use ajax i wrote the code of jsp and the remaning code by using ajax is not wrritened by observing these below code please try the remainning ajax code its
code problem - Java Beginners
code problem  Dear sir, my problem is that I've a string value if this String value has "quit" then output should be "bye". i want to make this program using SWITCH CASE statement. how to implement String value in Switch plz
code problem - Java Beginners
code problem  Dear sir, I'm havin a problem that suppose i've got... java script j2ee j2me sql plz help me to sort out this problem. thnx   Hi Friend, Please try the following sample code to solve your problem
code problem - Java Beginners
code problem  Dear sir, My problem is that i have some string value and in some case i want to remove all the value of this string, i tried this code- Response.str.clear(); but it shows some error called "response package
hibernate code problem - Hibernate
/selectclause.shtml If you have any problem this send me detail and source code...hibernate code problem  suppose i want to fetch a row from the table through a value which i got from the jsp page. how can i do it and iterate
Hibernate code problem - Hibernate
problem please send me code. Visit for more information. http...Hibernate code problem  Hi This is Raju.I tried the first example........How can i solve this problem. Am i need to Kept any other jars in path. 
Problem with code - Java Beginners
Problem with code  Hi Deepak. Im a newbie here at your forum. I have got a simple code of mine which is having a little problem. When I compile it, i get an...,identifier expected'...error. Could you help me out? Thank you
code problem - Java Beginners
code problem  Dear sir, my problem is given below: suppose a file Carries the following lines- Name: john age: 45 Address: goa phone...; Hi friend, Code to help in solving the problem : import java.io.
code problem - Java Beginners
code problem  Dear sir, my question was actually how to find a particual line's contain, example if a file contains- hy, how r u? regrd, john... your problem in details. Which keyword search the line. Thanks
code problem - Java Beginners
of program. thnx  Hi friend, Code to help in solving the problem...code problem  Dear sir, I've some integer value in ArrayList like- 10 40 30 i want to add them and print should be like- "total value
code problem - Java Beginners
code problem  Dear sir, I have an excel file in D: drive called today.xls, i want to open it thru java program, what code would be compatible plz help me  Hi friend, Code to help in solving the problem : import
code problem - Java Beginners
code problem  Dear sir, my problem is that, i have two Combobox one.... plz tell how to code this program.   Hi Friend, You can use the following code: ComboBox var arr = new Array(); arr[0] = new
Project about hashing and Avl TREES
Read data i must write code that i building avl tree and in every node...Project about hashing and Avl TREES   I want to make graphical... whole code
code problem - Java Beginners
; Hi friend, Code to help in solving the problem : import java.io....code problem  Dear Sir, I've to make a program where there are 10 lines of a particular file i've to display every Line's contains, example- Line1
code problem - Java Beginners
code problem  Dear sir, I've some string called "JohnSon" that has to be crypted first and then decrypted, how to crypt and decrypt data plz tell me.  Hi friend, Code to help in solving the problem : public
Application context problem code
Application context problem code   now i am posting my code here . i..."); // code to set test action environment createAction("/create", "Test", "list"); // code to execute test action String result = proxy.execute(); // code
code problem - Struts
code problem  hi friends i have 1 doubt regarding how to write the code of opensheet in action class i have done it as the action class code...(); System.out.println(conn); //Code to generate new sheet i.e login time IS NULL
code problem - Java Beginners
code problem  My code is below: import java.io.*; class FileRead...()); } } } Dear sir, my problem is that suppose i enter line number: 3 if line... your code and then again try it : import java.io.*; class FileRead
problem:struts code - Struts
problem:struts code  Hi, Am using struts1.2.I wrote a form(dynavalidator form)with validation after completing the form if we press submit its call the action class,in action class i gave forward to same form,the problem is if i
code problem - Java Beginners
code problem  i've to send a login packet( username & password..., what code should be compatible, as i heared with UDP programing there is no Guarantee of packet's delevery so send me code made of TCP, plz help me
combo box code problem
combo box code problem  in this my problem related to : when i select state MP then i wil open the its corresponding city but in database it only stores the option value no like MP at option value 10 then it will stores the 10
 

 

 

DMCA.com