Data Structures(Binary Search Tree to AVL Tree)ASAP

• April 4th, 2010, 01:06 AM
Data Structures(Binary Search Tree to AVL Tree)ASAP
I posted my code for a binary search tree assignment and the code is a working code...
::::ETAILS TO KNOW ABOUT THE CODE::::::
the program is required to
1. ask user the HEIGHT OF THE TREE which will determine the length of the array..
2.and then ask user to input numbers to be inserted in the tree/array..
3. and lastly, the program will now display the index numbers of the array chronologically with the array's contents on it(numbers entered and inserted)..

I have a GUI version of this code and its working..
Now here's my problem, now that i have my Binary Search Tree(BST) what I need now is a method that will update my BST for HEIGHT DIFFERENCES(pls refer to AVL tree) and whenever the tree is imbalance another method is needed to rebalance the tree..

::::NEEDED:::::
1. method that will chek for height differences of the tree
2. method that will rebalance the tree whenever the height differences is more than 1....

Code :

```import javax.swing.JOptionPane; import java.util.StringTokenizer;   public class BT {   private static int y; private static int[]x=new int[20]; private static int fs; private static int rc=2; private static int lc=1;   private static int length; private static int[]arr; public static void main(String[]args){   int h=Integer.parseInt(JOptionPane.showInputDialog("Enter Height of Tree:")); int c=h; int s=2; while(c>1){ s=(s*2); c--; } length=s-1;     arr=new int[length];//this is the Binary Search Tree array   String v=JOptionPane.showInputDialog("Enter Numbers to Insert on Tree:"); StringTokenizer st = new StringTokenizer(v,", "); int ctr=0; while (st.hasMoreTokens()) { y=Integer.parseInt(st.nextToken()); x[ctr]=y; ctr++; }   for(c=0;c<x.length;c++){ if(x[c]==0){ fs=c; break; } }     int[]f=new int[fs]; // this is the array where numbers inputted by the user is stored     for(c=0;c<f.length;c++){ f[c]=x[c]; }   //prints numbers entered System.out.print("You Entered Numbers: "); for(c=0;c<f.length;c++){ System.out.print(f[c]+" "); } System.out.println("\n");   //positions numbers entered in their proper place in the tree int d=0; for(c=0;c<f.length;c++){ while(arr[d]!=0){ if(f[c]>arr[d]){ d=2*d+2; } if(f[c]<arr[d]){ d=2*d+1; } } arr[d]=f[c]; d=0; }   //prints tree showing array indexes for(c=0;c<arr.length;c++){ System.out.println("Index "+"["+c+"]: "+arr[c]); } } }```
• April 4th, 2010, 10:49 AM
helloworld922
Re: Data Structures(Binary Search Tree to AVL Tree)ASAP
A recursive solution is the simplest to implement.

Pseudocode for finding depth of tree branch:

Code :

```public int depth(Node node)   local_depth = 0 If node doesn't exist: return local_depth If depth(leftNode) > depth(rightNode): local_depth += depth(leftNode) else local_depth += depth(rightNode) return local_depth```

To auto-balance your tree using AVL, compare the depth of the tree using pre-fix (or post-fix) traversal. If the depths differ by more than 1, you will have to "rotate" that branch as many times as it takes to get the depths of the left and right branches within 1 of each other.

To rotate a branch left:
Code :

```public void rotateLeft(Node node, Node parent) create a temporary node that refers to the left child set the right child of the left node to be the left child of the right node set the position of node (whether right or left child of parent) to be the temporary node```

Rotating right has a similar algorithm
• April 5th, 2010, 03:58 AM