我在平衡 AVL 树时遇到问题。我一直在寻找如何平衡它们的步骤,但我找不到任何有用的东西。
我知道有4种:
但我就是无法得到如何选择其中之一和 在哪个节点上应用它 !
任何帮助将不胜感激!
最佳答案
这是 java 实现,您将在那里了解算法的概念:
private Node<T> rotate(Node<T> n) {
if(n.getBf() < -1){
if(n.getRight().getBf() <= 0){
return left(n);
}
if(n.getRight().getBf() > 0){
return rightLeft(n);
}
}
if(n.getBf() > 1){
if(n.getLeft().getBf() >= 0){
return right(n);
}
if(n.getLeft().getBf() < 0){
return leftRight(n);
}
}
return n;
}
4 次旋转的单独方法在这里:
/**
* Performs a left rotation on a node
*
* @param n The node to have the left rotation performed on
* @return The new root of the subtree that is now balanced due to the rotation
*/
private Node<T> left(Node<T> n) {
if(n != null){
Node<T> temp = n.getRight();
n.setRight(temp.getLeft());
temp.setLeft(n);
return temp;
}
return n;
}
/**
* Performs a right rotation on a node
*
* @param n The node to have the right rotation performed on
* @return The new root of the subtree that is now balanced due to the rotation
*/
private Node<T> right(Node<T> n) {
if(n != null){
Node<T> temp = n.getLeft();
n.setLeft(temp.getRight());
temp.setRight(n);
return temp;
}
return n;
}
/**
* Performs a left right rotation on a node
*
* @param n The node to have the left right rotation performed on
* @return The new root of the subtree that is now balanced due to the rotation
*/
private Node<T> leftRight(Node<T> n) {
n.setLeft(left(n.getLeft()));
Node<T> temp = right(n);
return temp;
}
/**
* Performs a right left rotation on a node
*
* @param n The node to have the right left rotation performed on
* @return The new root of the subtree that is now balanced due to the rotation
*/
private Node<T> rightLeft(Node<T> n) {
n.setRight(right(n.getRight()));
Node<T> temp = left(n);
return temp;
}
关于data-structures - 平衡 AVL 树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14419180/