<分区>
我正在研究 AVL 树，但似乎找不到有关删除的引用代码(通过谷歌搜索或从我手边的几本教科书中找到)。
我不确定这是为什么，但是您知道在 Java 中删除 AVL 的任何引用/示例吗？
(我只找到这个:avl tree removal，它在链接中声明它在测试中失败)
<分区>
我正在研究 AVL 树，但似乎找不到有关删除的引用代码(通过谷歌搜索或从我手边的几本教科书中找到)。
我不确定这是为什么，但是您知道在 Java 中删除 AVL 的任何引用/示例吗？
(我只找到这个:avl tree removal，它在链接中声明它在测试中失败)
最佳答案
我有一个 AVL Tree in Java 的实现已经过很好的测试，如果你想用它作为引用。它基于维基百科的描述，并且评论非常好。
就像您在常规 BST 插入后必须保持平衡一样。您像 BST 一样删除节点，然后根据以下算法进行平衡。
BST 删除后平衡的情况是(节点是用于替换删除节点的节点的父节点):
... remove code ...
// Re-balance the tree all the way up the tree
while (nodeToRefactor != null) {
nodeToRefactor.updateHeight();
balanceAfterDelete(nodeToRefactor);
nodeToRefactor = (AVLNode<T>) nodeToRefactor.parent;
}
... remove code ...
... balance code ...
int balanceFactor = node.getBalanceFactor();
if (balanceFactor==-2 || balanceFactor==2) {
if (balanceFactor==-2) {
AVLNode<T> ll = (AVLNode<T>) node.lesser.lesser;
int lesser = ll.height;
AVLNode<T> lr = (AVLNode<T>) node.lesser.greater;
int greater = lr.height;
if (lesser>=greater) {
rightRotation(node);
} else {
leftRotation(node.lesser);
rightRotation(node);
}
} else if (balanceFactor==2) {
AVLNode<T> rr = (AVLNode<T>) node.greater.greater;
int greater = rr.height;
AVLNode<T> rl = (AVLNode<T>) node.greater.lesser;
int lesser = rl.height;
if (greater>=lesser) {
leftRotation(node);
} else {
rightRotation(node.greater);
leftRotation(node);
}
}
}
关于java - 从 AVL 树中删除示例代码，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10773013/