java - 二叉搜索树：AVL 树中节点的高度

Question

这是我必须制作的 AVL 树（希望足够大以便看得清楚）

http://oi46.tinypic.com/2426fer.jpg

我知道我的树对于我必须做的事情是正确的，但我不确定 AVL 树的高度以及它是如何工作的，正如您可能在我的绘图中看到的那样。真的希望您能提供帮助，我了解与 AVL 树有关的所有其他概念。谢谢

---

Answer 1

您删除了以前的问题，在该问题中您的 binarySearchTree 有问题。这是我在您删除问题之前写的解决方案。也许会有所帮助。

            if (tree.left == null && tree.right == null) {
                    if (compResult < 0) {
                            tree.left.data = item;
                            return true;
                    }
                    if (compResult > 0) {
                            tree.right.data = item;
                            return true;
                    }
            }
            if (compResult < 0) {
                    if (tree.left == null) {        //RED FLAG 
                            tree.left.data = item;  //BUT tree.left IS NULL!!
                            return true;
                    } else
                            add(tree = tree.left, item, count);
            }
            if (compResult > 0) {
                    if (tree.right == null) {       //RED FLAG
                            tree.right.data = item; //BUT tree.right IS NULL!!
                            return true;
                    } else
                            add(tree = tree.right, item, count);
            }

要解决这些问题，请创建一个新节点，然后将其分配给 tree.left 或 tree.right。

您应该进行迭代添加而不是递归添加，它更快。