Speaking of AVL Tree, I guess most of people with Computer Science(CS) background would not be unfamiliar with it. It's one of most famous self balanced binary search tree exists so far. So for the basic background information, please check on this Wiki Link. One thing very important is every basic action of AVL Tree takes O(logn). That is so wonderful.
I assume people read this blog already knew what Java Generic Programming means, even he/she doesn't know how to implement it. I believe this code is pretty easy to understand.
First of all, What do we store in our tree, so let's define our data type for our data to be stored in our tree. We typically name it as Node.
Basically, this data is comprised of one generic data, one left child and one right child. This is just like the general binary tree, two children with one data to be stored. But we need our generic data can be comparable, so we can search them and have them in order.
Second, let's use this Node structure to build our tree.
For AVLTree class, we need a root node to let user know where this tree starts. Each function works the way as the method name suggested, insert is to insert the new node to our tree, maximum is to get the maximum value of the tree and minimum if to get the minimum value of the tree.
For the insert function, every time we insert a new node, we need to check if every parent of the new node is still balanced. If yes, we'll have no problem with it, otherwise, we have to make some action like rotateLeft, rotateRight to have it rebalanced.
For the search, maximum and minimum function, each use recursive way or non-recursive way to go from root node to leave node to find what they need.
For the PrintTree function, it uses a CS tech called Breadth-First-Search(BFS) to go through our tree level by level. At the same time, it will print each node to system output.
For rotation of AVL Tree, this picture on Wiki explains a lot.
So, for testing our AVL Tree API, I made a simple demo here.
The output of this:
Level 0: 4
Level 1: 2
Level 1: 6
Level 2: 1
Level 2: 3
Level 2: 5
Level 2: 7
To make this more graphically, it will looks like:
/ \ / \
1 3 5 7
This is pretty much what we need.
The user could use other Object type, like String, Double, rather than primitive types like int, double.
For a more clear view, visit my gist page.