Repository: TheAlgorithms/Java
Pull request #6058 (2024-10-29 05:15:01)

refactor: Enhance docs, add tests in AVLTree
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6058?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `85.18519%` with `4 lines` in your changes missing coverage. Please review.
> Project coverage is 72.94%. Comparing base [(`bca8d0e`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/bca8d0efe0097423110276a3d540a2be97de5154?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`ce975a4`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/ce975a45d49466dab065821bbb15960861520f46?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6058?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...om/thealgorithms/datastructures/trees/AVLTree.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6058?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Ftrees%2FAVLTree.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy90cmVlcy9BVkxUcmVlLmphdmE=) | 85.18% | [2 Missing and 2 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6058?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #6058      +/-   ##
============================================
+ Coverage     72.40%   72.94%   +0.54%     
- Complexity     4983     5021      +38     
============================================
  Files           653      653              
  Lines         17574    17569       -5     
  Branches       3386     3385       -1     
============================================
+ Hits          12724    12816      +92     
+ Misses         4371     4262     -109     
- Partials        479      491      +12     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6058?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 1fc9ec0c..0f7184cd 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -912,6 +912,7 @@
               * [StackArrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/stacks/StackArrayTest.java)
               * [StackOfLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/stacks/StackOfLinkedListTest.java)
             * trees
+              * [AVLTreeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/AVLTreeTest.java)
               * [BinaryTreeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/BinaryTreeTest.java)
               * [BoundaryTraversalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/BoundaryTraversalTest.java)
               * [BSTFromSortedArrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/BSTFromSortedArrayTest.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/AVLTree.java b/src/main/java/com/thealgorithms/datastructures/trees/AVLTree.java
index 7b959b08..77ee5d5f 100644
--- a/src/main/java/com/thealgorithms/datastructures/trees/AVLTree.java
+++ b/src/main/java/com/thealgorithms/datastructures/trees/AVLTree.java
@@ -1,11 +1,19 @@
 package com.thealgorithms.datastructures.trees;
 
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Represents an AVL Tree, a self-balancing binary search tree.
+ * In an AVL tree, the heights of the two child subtrees of any node
+ * differ by at most one. If they differ by more than one at any time,
+ * rebalancing is performed to restore this property.
+ */
 public class AVLTree {
 
     private Node root;
 
-    private class Node {
-
+    private static class Node {
         private int key;
         private int balance;
         private int height;
@@ -17,8 +25,18 @@ public class AVLTree {
             key = k;
             parent = p;
         }
+
+        public Integer getBalance() {
+            return balance;
+        }
     }
 
+    /**
+     * Inserts a new key into the AVL tree.
+     *
+     * @param key the key to be inserted
+     * @return {@code true} if the key was inserted, {@code false} if the key already exists
+     */
     public boolean insert(int key) {
         if (root == null) {
             root = new Node(key, null);
@@ -31,7 +49,6 @@ public class AVLTree {
                 }
 
                 parent = n;
-
                 boolean goLeft = n.key > key;
                 n = goLeft ? n.left : n.right;
 
@@ -49,8 +66,32 @@ public class AVLTree {
         return true;
     }
 
+    /**
+     * Deletes a key from the AVL tree.
+     *
+     * @param delKey the key to be deleted
+     */
+    public void delete(int delKey) {
+        if (root == null) {
+            return;
+        }
+
+        // Find the node to be deleted
+        Node node = root;
+        Node child = root;
+        while (child != null) {
+            node = child;
+            child = delKey >= node.key ? node.right : node.left;
+            if (delKey == node.key) {
+                delete(node);
+                return;
+            }
+        }
+    }
+
     private void delete(Node node) {
         if (node.left == null && node.right == null) {
+            // Leaf node
             if (node.parent == null) {
                 root = null;
             } else {
@@ -64,6 +105,8 @@ public class AVLTree {
             }
             return;
         }
+
+        // Node has one or two children
         Node child;
         if (node.left != null) {
             child = node.left;
@@ -80,26 +123,49 @@ public class AVLTree {
         delete(child);
     }
 
-    public void delete(int delKey) {
-        if (root == null) {
-            return;
+    /**
+     * Returns a list of balance factors for each node in the tree.
+     *
+     * @return a list of integers representing the balance factors of the nodes
+     */
+    public List<Integer> returnBalance() {
+        List<Integer> balances = new ArrayList<>();
+        returnBalance(root, balances);
+        return balances;
+    }
+
+    private void returnBalance(Node n, List<Integer> balances) {
+        if (n != null) {
+            returnBalance(n.left, balances);
+            balances.add(n.getBalance());
+            returnBalance(n.right, balances);
         }
-        Node node = root;
-        Node child = root;
+    }
 
-        while (child != null) {
-            node = child;
-            child = delKey >= node.key ? node.right : node.left;
-            if (delKey == node.key) {
-                delete(node);
-                return;
-            }
+    /**
+     * Searches for a key in the AVL tree.
+     *
+     * @param key the key to be searched
+     * @return true if the key is found, false otherwise
+     */
+    public boolean search(int key) {
+        Node result = searchHelper(this.root, key);
+        return result != null;
+    }
+
+    private Node searchHelper(Node root, int key) {
+        if (root == null || root.key == key) {
+            return root;
         }
+
+        if (root.key > key) {
+            return searchHelper(root.left, key);
+        }
+        return searchHelper(root.right, key);
     }
 
     private void rebalance(Node n) {
         setBalance(n);
-
         if (n.balance == -2) {
             if (height(n.left.left) >= height(n.left.right)) {
                 n = rotateRight(n);
@@ -143,7 +209,6 @@ public class AVLTree {
         }
 
         setBalance(a, b);
-
         return b;
     }
 
@@ -169,7 +234,6 @@ public class AVLTree {
         }
 
         setBalance(a, b);
-
         return b;
     }
 
@@ -197,53 +261,9 @@ public class AVLTree {
         }
     }
 
-    public void printBalance() {
-        printBalance(root);
-    }
-
-    private void printBalance(Node n) {
-        if (n != null) {
-            printBalance(n.left);
-            System.out.printf("%s ", n.balance);
-            printBalance(n.right);
-        }
-    }
-
     private void reheight(Node node) {
         if (node != null) {
             node.height = 1 + Math.max(height(node.left), height(node.right));
         }
     }
-
-    public boolean search(int key) {
-        Node result = searchHelper(this.root, key);
-        return result != null;
-    }
-
-    private Node searchHelper(Node root, int key) {
-        // root is null or key is present at root
-        if (root == null || root.key == key) {
-            return root;
-        }
-
-        // key is greater than root's key
-        if (root.key > key) {
-            return searchHelper(root.left, key); // call the function on the node's left child
-        }
-        // key is less than root's key then
-        // call the function on the node's right child as it is greater
-        return searchHelper(root.right, key);
-    }
-
-    public static void main(String[] args) {
-        AVLTree tree = new AVLTree();
-
-        System.out.println("Inserting values 1 to 10");
-        for (int i = 1; i < 10; i++) {
-            tree.insert(i);
-        }
-
-        System.out.print("Printing balance: ");
-        tree.printBalance();
-    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/AVLTreeTest.java b/src/test/java/com/thealgorithms/datastructures/trees/AVLTreeTest.java
new file mode 100644
index 00000000..6aa5dc9e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/trees/AVLTreeTest.java
@@ -0,0 +1,101 @@
+package com.thealgorithms.datastructures.trees;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.List;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class AVLTreeTest {
+    private AVLTree avlTree;
+
+    @BeforeEach
+    public void setUp() {
+        avlTree = new AVLTree();
+    }
+
+    @Test
+    public void testInsert() {
+        assertTrue(avlTree.insert(10));
+        assertTrue(avlTree.insert(20));
+        assertTrue(avlTree.insert(5));
+        assertFalse(avlTree.insert(10)); // Duplicate
+    }
+
+    @Test
+    public void testSearch() {
+        avlTree.insert(15);
+        avlTree.insert(25);
+        assertTrue(avlTree.search(15));
+        assertFalse(avlTree.search(30)); // Not in the tree
+    }
+
+    @Test
+    public void testDeleteLeafNode() {
+        avlTree.insert(10);
+        avlTree.insert(20);
+        avlTree.insert(30);
+        avlTree.delete(30);
+        assertFalse(avlTree.search(30));
+    }
+
+    @Test
+    public void testDeleteNodeWithOneChild() {
+        avlTree.insert(20);
+        avlTree.insert(10);
+        avlTree.insert(30);
+        avlTree.delete(10);
+        assertFalse(avlTree.search(10));
+    }
+
+    @Test
+    public void testDeleteNodeWithTwoChildren() {
+        avlTree.insert(20);
+        avlTree.insert(10);
+        avlTree.insert(30);
+        avlTree.insert(25);
+        avlTree.delete(20);
+        assertFalse(avlTree.search(20));
+        assertTrue(avlTree.search(30));
+        assertTrue(avlTree.search(25));
+    }
+
+    @Test
+    public void testReturnBalance() {
+        avlTree.insert(10);
+        avlTree.insert(20);
+        avlTree.insert(5);
+        List<Integer> balances = avlTree.returnBalance();
+        assertEquals(3, balances.size()); // There should be 3 nodes
+        assertEquals(0, balances.get(0)); // Balance for node 5
+        assertEquals(0, balances.get(1)); // Balance for node 10
+        assertEquals(0, balances.get(2)); // Balance for node 20
+    }
+
+    @Test
+    public void testInsertAndRebalance() {
+        avlTree.insert(30);
+        avlTree.insert(20);
+        avlTree.insert(10); // This should cause a right rotation
+        assertTrue(avlTree.search(20));
+        assertTrue(avlTree.search(10));
+        assertTrue(avlTree.search(30));
+    }
+
+    @Test
+    public void testComplexInsertionAndDeletion() {
+        avlTree.insert(30);
+        avlTree.insert(20);
+        avlTree.insert(10);
+        avlTree.insert(25);
+        avlTree.insert(5);
+        avlTree.insert(15);
+
+        avlTree.delete(20); // Test deletion
+        assertFalse(avlTree.search(20));
+        assertTrue(avlTree.search(30));
+        assertTrue(avlTree.search(25));
+    }
+}