It looks like you're new here. If you want to get involved, click one of these buttons!

- 141.2K All Categories
- 103.9K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 40K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 553 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.9K Visual Basic
- 2.6K Game programming
- 317 Console programming
- 93 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 748 Computer Hardware
- 3.5K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 258 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 199 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 605 Jobs Wanted
- 213 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 7 Join the Team
- 356 Comments on this site
- 71 Computer Emulators
- 2.1K General programming
- 188 New programming languages
- 641 Off topic board
- 226 Mobile & Wireless
- 98 Android
- 126 Palm Pilot
- 340 Multimedia
- 156 Demo programming
- 184 MP3 programming
- Bash scripts
- 28 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 371 MS-DOS
- Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 944 Software Development
- 417 Algorithms
- 68 Object Orientation
- 92 Project Management
- 95 Quality & Testing
- 271 Security
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 62 AJAX
- 6 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 37 JQuery
- 310 WEB Servers
- 157 WEB-Services / SOAP

nightsurfer
Member Posts: **272**

in Java

Hi,

I am doing a project for one of my courses, and it involves locating a few data structures that meet required complexities. I decided that the best option is to store the data in two separate structures, and use the appropriate structure for each method to provide the user with the correct structure. The two structures I chose are Hashtable, and AVLTree. Hashtable gives me constant time on find, and AVLTree gives me log(n) time on finding the closest after. On insert(Item) with Hashtable, I get constant time, and with AVLTree, I think it is O(n).

I was looking in my texts for implementations of AVLTree, and found that the only method that really differs from BinarySearchTree is the add method, in that after adding the new item to the tree, it has to rebalance the tree. So if each element contains, in addition to its given information, its height in the tree, and pointers to each of its children, how would I go about rebalancing the tree?

I am assuming that I can create the entire tree as in BinarySearchTree, and that I will have to add to the insert method a call to rebalance the tree, but I am stuck on the actual rebalancing. I was looking in the java.util library for a standard AVL tree, but couldn't find one. Am I missing something here?

Thanks in advance.

There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

I am doing a project for one of my courses, and it involves locating a few data structures that meet required complexities. I decided that the best option is to store the data in two separate structures, and use the appropriate structure for each method to provide the user with the correct structure. The two structures I chose are Hashtable, and AVLTree. Hashtable gives me constant time on find, and AVLTree gives me log(n) time on finding the closest after. On insert(Item) with Hashtable, I get constant time, and with AVLTree, I think it is O(n).

I was looking in my texts for implementations of AVLTree, and found that the only method that really differs from BinarySearchTree is the add method, in that after adding the new item to the tree, it has to rebalance the tree. So if each element contains, in addition to its given information, its height in the tree, and pointers to each of its children, how would I go about rebalancing the tree?

I am assuming that I can create the entire tree as in BinarySearchTree, and that I will have to add to the insert method a call to rebalance the tree, but I am stuck on the actual rebalancing. I was looking in the java.util library for a standard AVL tree, but couldn't find one. Am I missing something here?

Thanks in advance.

There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven

© 1997-2017 Programmersheaven.com - All rights reserved.

## Comments

11From what I remember there are 4 kinds of rotations to rebalance the tree: left-left, left-right, right-right, and right-left.

7

/

4

5.5

After inserting 7,4,5.5 in that order you would need to do a left-right rotation, giving you:

7

/

5.5

/

4 after the first, left rotation and finally:

5.5

/

4 7

The right-left is the opposite. I found my old book so tell me if you still want the code.

272I understand that I have to make 2 rotations whenever a rebalancing is required, but I don't know how to do it. Is there a standard library class that does this, or do you have the code for a normal AVL tree, with each node holding an object that I can specify?

Thanks for your help.

There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

11I don't know of a library that does this but here is what my book says:

private avlinsert( 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;

}

else if(x.compareTo( t.element ) > 0 )

{

// do same but with right instead of left and > instead of <.

}

else; // duplicate element, do nothing

t.height = max( height( t.left), height(t.right) ) + 1;

return t;

}

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;

}

private static avlnode doublewithleftchild( avlnode k3 ){

k3.left= rotatewithrightchild(k3.left);

return rotatewithleftchild(k3);

}

272: : I understand that I have to make 2 rotations whenever a rebalancing is required, but I don't know how to do it. Is there a standard library class that does this, or do you have the code for a normal AVL tree, with each node holding an object that I can specify?

:

: I don't know of a library that does this but here is what my book says:

:

: private avlinsert( 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;

: }

: else if(x.compareTo( t.element ) > 0 )

: {

: // do same but with right instead of left and > instead of <.

: }

: else; // duplicate element, do nothing

: t.height = max( height( t.left), height(t.right) ) + 1;

: return t;

: }

:

: 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;

:

: }

:

: private static avlnode doublewithleftchild( avlnode k3 ){

: k3.left= rotatewithrightchild(k3.left);

: return rotatewithleftchild(k3);

: }

:

:

There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

0✭________ \ http://forcoder.org \ free video tutorials and ebooks about [ PHP Visual Basic .NET Scratch Delphi C# Swift PL/SQL C++ R C Python Java Perl Go MATLAB Assembly Visual Basic Objective-C Ruby JavaScript Hack F# Clojure Transact-SQL Julia Prolog Bash D VBScript Scheme Apex Kotlin Lua ML Crystal Erlang FoxPro Logo Lisp COBOL SAS Ada Fortran ABAP Rust Scala Dart LabVIEW Awk Alice ] _______