AVL Tree Visualization in JavaFX

This JavaFX application demonstrates the visualization of an AVL Tree (Adelson-Velsky and Landis Tree), a type of self-balancing binary search tree. The application provides functionalities to insert, search, delete, and perform different tree traversals with visual animations.

Dashboard of AVL Tree Visualizer

The AVL Tree maintains a balance factor at each node to ensure the height remains logarithmic, providing efficient operations. Since the AVL tree is a self-balancing binary tree, so whenever the tree will get unbalanced the balancing algorithm will balance the tree.

The balancing of the tree is taken care by different rotations of AVL Tree. There are two types of rotations of an AVL tree, these are:

1. Left Rotation

   Consider the situation of an tree nodes:

   

   To balance this we perform following operations:
   

   • 45 becomes the new root.
   • 13 takes ownership of 45's left child as its right child, or in this case, null.
   • 45 takes ownership of 13 as its left child.

   Now tree will look like:

   

   
   

2. Right Rotation

   Consider the situation of an tree nodes:

   

   To balance this we perform following operations:
   

   • 20 becomes the new root.
   • 30 takes ownership of 20's right child, as its left child. In this case, that value is null.
   • 20 takes ownership of 30, as it's right child.

   Now tree will look like:

   

These two rotaions will take care the following four unbalancing cases of AVL Tree.:

1. Left-Left Unbalancing Case

   This case looks like:

   

   To balance this we'll perform single time right-rotation on 10.

2. Left-Right Unbalancing Case

   This case looks like:

   

   To balance this, we'll perform:

   • First, left-rotation on 10(left-child of current node).
   • Then, right-rotation on 20.

3. Right-Right Unbalancing Case

   This case looks like:

   

   To balance this we'll perform single time left-rotation on 30.

4. Right-Left Unbalancing Case

   This case looks like:

   

   To balance this, we'll perform:

   • First, right-rotation on 30(right-child of current node).
   • Then, left-rotation on 10.

So just by performing these rotations we can balance our binary search tree.

How to Use

1. Insert Nodes: Click the insert button to add nodes to the tree. The tree will automatically balance itself.
2. Search Nodes: Use the search function to locate a specific value in the tree.
3. Delete Nodes: Click the delete button to remove a node and see the balancing in action.
4. Perform Traversals: Choose from different traversal options to see the order of nodes visually.
5. Clear Tree: Reset the tree using the clear function.

Features

Text Box

The node of tree can contain integer value. The integer value can be entered in the given text box, if the value entered will not be valid then it will not accept it.

So the user should input the value ranging from -2,147,483,648 to 2,147,483,647.

But for better visualisation try to insert lower integer values.

Text Box for giving values

1. Operations

• Insertion:

  Add nodes to the AVL Tree, ensuring it remains balanced. Visualize the balancing process with animations.

  Node value can inserted by using insert button on left side below the text-box.

  

  Button for inserting the value

  

  Demonstration of using insert button

• Search:

  Find a node in the tree with visual feedback indicating whether the node exists.

  We can use search button to search the value in AVL Tree. The searching will happen by comparing the value to be searched to the value of current node, and according to the value, the search will go to the left or right subtree of an AVL tree.

  

  Button for inserting the value

  

  Demonstration of searching value 80 in AVL Tree

• Deletion:

  Remove nodes while maintaining the balance of the tree.

  We can use delete button to delete the value in AVL Tree.

  

  Button for deleting the value

  There are four cases of deleting a node:

  1. Node to be deleted is leaf node

     

     Node to be deleted - 80: which is leaf node

  2. Node to be deleted has one child node - only at left

     

     Node to be deleted - 120: which has only left node

  3. Node to be deleted has one child node - only at right

     

     Node to be deleted - 23: which has only right node

  4. Node to be deleted has both of children

     

     Node to be deleted - 30: which has both the child

2. Traversals

• Inorder:

  Traverse the tree in an ascending order.

  

• Preorder:

  Traverse the tree in a root-left-right order.

  

• Postorder:

  Traverse the tree in a left-right-root order.

  

• Level Order:

  Traverse the tree level by level.

  

• DFS:

  Perform a depth-first traversal.

  

• Visual Feedback: Animations for insertion, deletion, and traversal steps to provide an engaging learning experience.

• Clear

  Reset the AVL Tree to an empty state.

  Clear the screen by pressing on clear Tree button.

  

  Clear button

  
  
  

  

  Clearing tree

Code Structure

• Main.java

  It's the main file of application, it loads FXML file and set the scene and then show the stage. Entire application runs from this file.

• AVLTree.java

  Contains all the methods and animation related code to AVL tree. All the drawing and animations are executing from this file.

• AVLNode.java

  This file contains a node structure of an AVL tree. It consists of a methods to set the positions of circle and line.

• Main.fxml

  It is used for basic UI element using scene-builder. AnchorPane, Label, TextBox,..etc elements are used from scene builder.

• Controller.java

  This file contains implementation of all on-action methods required for basic operation. Like insert, search, delete...

See each file for more detailed documentation, and in-depth explanations of how each class functions

Built With

• Programming Langauge: Java 17.0.0
• Library Used: JavaFX 22.0.2

Requirements

• Java Development Kit (JDK) 11 or higher
• JavaFX SDK (included in most modern Java IDEs)

How to Run

1. Clone the repository.
2. Import the project into your Java IDE (like IntelliJ IDEA, Eclipse with e(fx)clipse).
3. Ensure JavaFX is properly configured in your IDE.
4. Run the main class, which initializes the JavaFX application and displays the AVL Tree visualization.

Credits

1. Our Mentor - Deeapak Sir
2. AVL Tree Visualisation - Motivation
3. Youtube tutorial for javafx
4. StackOverflow
5. ChatGPT
6. Javafx docs