平衡 AVL 树 (C++)
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4219743/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
balancing an AVL tree (C++)
提问by gregghz
I'm having the hardest time trying to figure out how to balance an AVL tree for my class. I've got it inserting with this:
我最难的是弄清楚如何为我的班级平衡 AVL 树。我已经把它插入了：
Node* Tree::insert(int d)
{
cout << "base insert\t" << d << endl;
if (head == NULL)
return (head = new Node(d));
else
return insert(head, d);
}
Node* Tree::insert(Node*& current, int d)
{
cout << "insert\t" << d << endl;
if (current == NULL)
current = new Node(d);
else if (d < current->data) {
insert(current->lchild, d);
if (height(current->lchild) - height(current->rchild)) {
if (d < current->lchild->getData())
rotateLeftOnce(current);
else
rotateLeftTwice(current);
}
}
else if (d > current->getData()) {
insert(current->rchild, d);
if (height(current->rchild) - height(current->lchild)) {
if (d > current->rchild->getData())
rotateRightOnce(current);
else
rotateRightTwice(current);
}
}
return current;
}
My plan was to have the calls to balance() check to see if the tree needs balancing and then balance as needed. The trouble is, I can't even figure out how to traverse the tree to find the correct unbalanced node. I know how to traverse the tree recursively, but I can't seem to translate that algorithm into finding the lowest unbalanced node. I'm also having trouble writing an iterative algorithm. Any help would be appreciated. :)
我的计划是调用 balance() 检查树是否需要平衡，然后根据需要进行平衡。问题是，我什至不知道如何遍历树来找到正确的不平衡节点。我知道如何递归遍历树，但我似乎无法将该算法转化为找到最低的不平衡节点。我也无法编写迭代算法。任何帮助，将不胜感激。:)
回答by Carlos
You can measure the heightof a branch at a given point to calculate the unbalance
您可以测量height给定点的分支以计算不平衡
(remember a difference in height (levels) >= 2 means your tree is not balanced)
（请记住高度（级别）的差异 >= 2 表示您的树不平衡）
int Tree::Height(TreeNode *node){
int left, right;
if(node==NULL)
return 0;
left = Height(node->left);
right = Height(node->right);
if(left > right)
return left+1;
else
return right+1;
}
Depending on the unevenness then you can rotateas necessary
根据不平整度，您可以根据需要旋转
void Tree::rotateLeftOnce(TreeNode*& node){
TreeNode *otherNode;
otherNode = node->left;
node->left = otherNode->right;
otherNode->right = node;
node = otherNode;
}
void Tree::rotateLeftTwice(TreeNode*& node){
rotateRightOnce(node->left);
rotateLeftOnce(node);
}
void Tree::rotateRightOnce(TreeNode*& node){
TreeNode *otherNode;
otherNode = node->right;
node->right = otherNode->left;
otherNode->left = node;
node = otherNode;
}
void Tree::rotateRightTwice(TreeNode*& node){
rotateLeftOnce(node->right);
rotateRightOnce(node);
}
Now that we know how to rotate, lets say you want to inserta value in the tree... First we check whether the tree is emptyor not
现在我们知道如何旋转，可以说你要插入树的值...首先，我们检查树是否为空或不
TreeNode* Tree::insert(int d){
if(isEmpty()){
return (root = new TreeNode(d)); //Is empty when root = null
}
else
return insert(root, d); //step-into the tree and place "d"
}
When the tree is not empty we use recursionto traverse the tree and get to where is needed
当树不为空时，我们使用递归遍历树并到达需要的地方
TreeNode* Tree::insert(TreeNode*& node, int d_IN){
if(node == NULL) // (1) If we are at the end of the tree place the value
node = new TreeNode(d_IN);
else if(d_IN < node->d_stored){ //(2) otherwise go left if smaller
insert(node->left, d_IN);
if(Height(node->left) - Height(node->right) == 2){
if(d_IN < node->left->d_stored)
rotateLeftOnce(node);
else
rotateLeftTwice(node);
}
}
else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger
insert(node->right, d_IN);
if(Height(node->right) - Height(node->left) == 2){
if(d_IN > node->right->d_stored)
rotateRightOnce(node);
else
rotateRightTwice(node);
}
}
return node;
}
You should always check for balance (and do rotations if necessary)when modifying the tree, no point waiting until the end when the tree is a mess to balance it. That just complicates things...
在修改树时，您应该始终检查平衡（并在必要时进行旋转），没有必要等到树一团糟时再平衡它。那只会让事情复杂化...
UPDATE
更新
There is a mistake in your implementation, in the code below you are not checking correctly whether the tree is unbalanced. You need to check whether the height is equals to 2 (therefore unbalance). As a result the code bellow...
您的实现中有一个错误，在下面的代码中，您没有正确检查树是否不平衡。您需要检查高度是否等于 2（因此不平衡）。结果是下面的代码......
if (height(current->lchild) - height(current->rchild)) { ...
if (height(current->rchild) - height(current->lchild)) {...
Should become...
应该变成...
if (height(current->lchild) - height(current->rchild) == 2) { ...
if (height(current->rchild) - height(current->lchild) == 2) {...
Some Resources
一些资源
回答by valdo
Wait, wait, wait. You aren't really going to check the "height" of every branch each time you're inserting something, are you?
等等，等等，等等。每次插入内容时，您不会真的要检查每个分支的“高度”，是吗？
Measuring the height means transversing all the sub-branch. Means - every insert into such a tree will cost O(N). If so - what do you need such a tree? You may use a sorted array as well: it gives O(N) insertion/deletion and O(log N) search.
测量高度意味着横穿所有的支线。意味着 - 每次插入这样的树都将花费 O(N)。如果是这样 - 你需要这样一棵树吗？您也可以使用排序数组：它提供 O(N) 插入/删除和 O(log N) 搜索。
A correct AVL handling algorithm must storethe left/right height difference at each node. Then, after every operation (insert/remove) - you must make sure none of the affected nodes will be too much unbalanced. To do this you do the so-called "rotations". During them you don'tactually re-measure the heights. You just don't have to: every rotation changes the balance of the affected nodes by some predictable value.
正确的 AVL 处理算法必须存储每个节点的左/右高度差。然后，在每次操作（插入/删除）之后 - 您必须确保受影响的节点都不会太不平衡。为此，您需要进行所谓的“旋转”。在它们期间，您实际上并没有重新测量高度。您只是不必：每次旋转都会通过一些可预测的值改变受影响节点的平衡。
回答by cos
goto http://code.google.com/p/self-balancing-avl-tree/, all usual operations like add, delete are implemented, plus concat and split
转到http://code.google.com/p/self-balancing-avl-tree/，实现了所有常用的添加、删除等操作，加上 concat 和 split
回答by Alex Spencer
Commented out is the code right rotate above and left rotate, below is my working right rotate and my working left rotate. I think the logic in the rotate above is inversed:
注释掉的是上面右旋和左旋的代码，下面是我的工作右旋和我的工作左旋。我认为上面旋转中的逻辑是相反的：
void rotateRight(Node *& n){
//Node* temp = n->right;
//n->right = temp->left;
//temp->left = n;
//n = temp;
cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE RIGHT}}}}}}}}}}}}}}}}}}}}}" << endl;
Node *temp = n->left;
n->left = temp->right;
temp->right = n;
n = temp;
}
void rotateLeft(Node *& n){
//Node *temp = n->left;
//n->left = temp->right;
//temp->right = n;
//n = temp;
cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE LEFT}}}}}}}}}}}}}}}}}}}}}" << endl;
Node* temp = n->right;
n->right = temp->left;
temp->left = n;
n = temp;
}
