- AVL tree is self-balance binary search tree. The goal of this project is to implement the AVL tree data structure using Java programing language. After each element insert to the AVL Tree, the output information that print out in the command line should show the details of AVL tree.
-
Steps
1.Download the java source file, which named "AVLTreeTeste.java", to your desktop directory.
2.Go to the command line. (For Windows user, please press Win+R keys and type "cmd" then press enter key. For MacOs user, please press command+space keys and type "terminal" and press enter key).
3.Type "cd desktop" in command line.
4.Type "javac AVLTreeTester.java" in command line.
5.Type "java AVLTreeTester" in command line.
-
Explaination for rotate_left and rotate_right fucntion
There are two prototypes for each function rotate_left and rotate_right. The function only takes one parameter is designed to perform single rotate left or rotate right. The function takes two parameters that are used to perform rotate left then rotate right operation. For example, when we insert elements 1,3 and 5 to the AVL tree, we just need to make the tree balance by one rotate operation, which is to rate left. Therefore, we just need to make the tree balance by calling the rotate_left function with only one parameter.
In some situations, when we try to perform the two operations to make the AVL tree balance, we need to make one of the children of the Node point to either the left side or right side of the Node’s parent. Therefore, the function with two parameters is needed in this situation. For example,when we insert elements 10,20,30,40,50 and 25 to the AVL tree, we need to do the rotate right then rotate left operation to make the AVL tree balance. In this case, we need to make 25 points to the right of the 20.
-
Explaination for balance fucntion As you can see in the picture below, the function, which named balance, use the post-order traversal to travel each node in the AVL tree and balance each node from the bottom of the tree to the top of the tree. The balance function use the height of each node to figure out which operations need to be performed.
-
Insert 1,3,5,7,2,4,6,8,9,11,13 to the AVL tree and remove 13 at the end.
-
Insert 1,3,5,7,2,4,6,8,9,11,13 to the AVL tree and remove 7(the root) at the end.
-
Insert 1,3,5,7,2,4,6,8,9,11,13 to the AVL tree and remove 9 and 3 at the end.
-
An empty AVL tree and try to remove 10.
-
Insert elements 10,20,30,40,50,25 and remove 20 at the end.
- Hing Li