AVL Tree program in Java

与红黑树类似，AVL 树是 Java 中另一种自平衡 BST（二叉搜索树）。在 AVL 树中，左右子树的高度差对于所有节点都不会超过 1。执行 BST 的搜索、最大值、最小值、插入和删除操作的时间复杂度为 O(h)，其中 h 是二叉搜索树的高度。

让我们举一个 AVL 树和一棵非 AVL 树的例子来理解它们之间的区别，

图 (1) 是 AVL 树的一个例子，因为左右子树的高度差为 1。图 (2) 不是 AVL 树，因为左右子树的高度差不为 1。

算法

让我们来理解一下在 AVL 树中插入节点的算法。

假设 newNode 是 AVL 树中新插入的节点。

1. 我们将通过执行标准的 BST 插入操作将 newNode 插入到 AVL 树中。
2. 我们将从 newNode 开始遍历 AVL 树，并检查哪个节点不平衡。假设 unBalNode 是第一个不平衡的节点，childNode 是 unBalNode 的子节点，它位于从 newNode 到 unBalNode 的路径上，而 newNode 是 unBalNode 的孙子节点，也位于从 newNode 到 unBalNode 的路径上。
3. 之后，我们在以 unBalNode 为根的子树上执行适当的旋转来重新平衡 AVL 树。以下是需要处理的四种情况：
   1. 当 childNode 是 unBalNode 的左子节点，而 newNode 是 childNode 的左子节点时。这种情况称为左左情况。
   2. 当 childNode 是 unBalNode 的左子节点，而 newNode 是 childNode 的右子节点时。这种情况称为左右情况。
   3. 当 childNode 是 unBalNode 的右子节点，而 newNode 是 childNode 的右子节点时。这种情况称为右右情况。
   4. 当 childNode 是 unBalNode 的右子节点，而 newNode 是 childNode 的左子节点时。这种情况称为右左情况。
4. 在我们上面讨论的所有情况中，只需要重新平衡以 unBalNode 为根的子树。之后，整个树将恢复平衡，与插入之前的情况相同。

AVLTreeExample.java

输出