Java AVL Tree Tutorial 🌳

beginner
25 min

Java AVL Tree Tutorial 🌳

Welcome to our deep dive into the world of AVL Trees in Java! In this tutorial, we'll explore what AVL Trees are, why they're useful, and how to create and manipulate them in Java. Let's get started!

Table of Contents

  1. Introduction to AVL Trees 📝

    • Definition and History
    • Advantages and Disadvantages

  2. AVL Tree Structure 🎯

    • Nodes and Height
    • Balance Factor

  3. AVL Tree Rotations 💡

    • Single Rotations
    • Double Rotations

  4. Inserting Nodes into AVL Trees ✅

    • Step-by-step Example

  5. Deleting Nodes from AVL Trees 💡

    • Case Studies

  6. AVL Tree Quiz 🎯

Introduction to AVL Trees 📝

An AVL (Adelson-Velsky and Landis) tree is a self-balancing binary search tree, which was introduced in 1962. The main advantage of AVL trees is that they ensure that the height of the tree is always minimized, making them efficient for search operations.

Advantages and Disadvantages

  • Advantages:
    • Maintains a balanced tree structure, reducing the height and improving search, insert, and delete operations.
    • Guaranteed log(n) time complexity for search, insert, and delete operations.
  • Disadvantages:
    • More complex structure and operations compared to a simple binary search tree.
    • Higher constant factor due to the need for balance checks and rotations.

AVL Tree Structure 🎯

An AVL tree consists of nodes, each containing a key-value pair and a balance factor. The balance factor of a node is used to calculate the height of the subtrees, which helps in maintaining the balance of the tree.

  • Nodes: Contain a key-value pair and a balance factor.
  • Height: Calculated as the maximum height of the left and right subtrees plus 1.
  • Balance Factor: Difference between the heights of the left and right subtrees (left height - right height).

AVL Tree Rotations 💡

To maintain balance in an AVL tree, we perform single and double rotations. These rotations adjust the structure of the tree while preserving the sorted order of keys.

Single Rotations

  • Left Rotation: When a node's right subtree becomes unbalanced.
java
A / \ B D / \ \ C E F // \ / \ G H I J K

Before Rotation:

  • Balance factor of A = 2 (right heavy)
  • Balance factor of D = 2 (right heavy)

After Rotation:

  • Balance factor of B = 0 (balanced)

  • Balance factor of D = 0 (balanced)

  • Right Rotation: When a node's left subtree becomes unbalanced.

java
A / \ B D / \ \ C E F // \ / \ G H I J K

Before Rotation:

  • Balance factor of A = -2 (left heavy)
  • Balance factor of D = -2 (left heavy)

After Rotation:

  • Balance factor of A = 0 (balanced)
  • Balance factor of D = 0 (balanced)

Inserting Nodes into AVL Trees ✅

Inserting a new node in an AVL tree follows the same steps as inserting in a binary search tree, but with additional balance checks and adjustments.

java
// Example of inserting node 10 into an empty AVL tree AVLTree root = null; root = insert(10, root);

Step-by-step Example

  1. Insert node 10 into an empty tree. Balance factor of root is 0 (balanced).
  2. Insert node 20 into the right subtree of 10. Balance factor of 10 becomes 1 (left heavy).
  3. Insert node 15 into the left subtree of 20. Balance factor of 20 becomes -1 (right heavy).
  4. Insert node 12 into the left subtree of 15. Balance factor of 15 becomes 0 (balanced).
  5. Insert node 18 into the right subtree of 20. Balance factor of 20 becomes 0 (balanced).
  6. Insert node 17 into the left subtree of 15. Balance factor of 15 becomes -1 (right heavy).
  7. Perform a right rotation on 15, balancing the tree.

Deleting Nodes from AVL Trees 💡

Deleting a node in an AVL tree involves finding and removing the node, and then adjusting the balance of the tree as needed.

java
// Example of deleting node 10 from an AVL tree AVLTree root = ...; // AVL tree with root node 10 root = delete(10, root);

Case Studies

  1. Deleting a leaf node:
    • Find the node to delete.
    • Remove the node and update its parent's pointers.
    • Balance check and adjustments as needed.
  2. Deleting a node with one child:
    • Find the node to delete.
    • Remove the node and make its child the new parent.
    • Balance check and adjustments as needed.
  3. Deleting a node with two children:
    • Find the node to delete.
    • Replace the node with its in-order successor or predeccessor.
    • Perform balance checks and adjustments as needed.

AVL Tree Quiz 🎯

Quick Quiz
Question 1 of 1

What is the balance factor of an AVL tree node with a left subtree height of 3 and a right subtree height of 1?

That's it for our deep dive into AVL Trees in Java! Remember to practice coding AVL trees to solidify your understanding. Happy coding! 🚀