平衡 AVL 树 (C++)
我正在努力弄清楚如何为我的班级平衡 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;
}
我的计划是调用balance() 检查树是否需要平衡,然后根据需要进行平衡。问题是,我什至不知道如何遍历树来找到正确的不平衡节点。我知道如何递归地遍历树,但我似乎无法将该算法转化为找到最低的不平衡节点。我在编写迭代算法时也遇到了麻烦。任何帮助将不胜感激。 :)
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:
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. :)
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
您可以测量给定点的树枝的高度来计算不平衡度
(请记住,高度(级别)的差异 >= 2 表示您的树不平衡)
根据不均匀程度,您可以根据需要旋转
现在我们知道如何旋转,假设您想在树中插入一个值...首先我们检查是否树是否为空
当树不为空时,我们使用递归来遍历树并到达需要的地方
您应该始终检查平衡(并且必要时进行旋转)在修改树时,没有必要等到树一团糟的时候才去平衡它。这只会让事情变得复杂......
更新
您的实现中有一个错误,在下面的代码中您没有正确检查树是否不平衡。您需要检查高度是否等于 2(因此不平衡)。因此,下面的代码...
应该成为...
一些资源
You can measure the
height
of a branch at a given point to calculate the unbalance(remember a difference in height (levels) >= 2 means your tree is not balanced)
Depending on the unevenness then you can rotate as necessary
Now that we know how to rotate, lets say you want to insert a value in the tree... First we check whether the tree is empty or not
When the tree is not empty we use recursion to traverse the tree and get to where is needed
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...
Should become...
Some Resources
等等,等等,等等。
每次插入东西时,您实际上不会检查每个分支的“高度”,是吗?
测量高度意味着横穿所有的支线。意味着 - 每次插入到这样的树中都会花费 O(N)。如果是这样 - 你需要这样一棵树做什么?您也可以使用排序数组:它提供 O(N) 插入/删除和 O(log N) 搜索。
正确的 AVL 处理算法必须存储每个节点的左/右高度差。然后,在每次操作(插入/删除)之后 - 您必须确保受影响的节点不会有太多不平衡。为此,您需要进行所谓的“旋转”。在此期间,您实际上不会重新测量高度。您只是不必这样做:每次旋转都会将受影响节点的平衡改变一些可预测的值。
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.
A correct AVL handling algorithm must store the 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't actually re-measure the heights. You just don't have to: every rotation changes the balance of the affected nodes by some predictable value.
转到 http://code.google.com/p/self-balancing-avl -tree/ ,实现了所有常用操作,如添加、删除,以及连接和分割
goto http://code.google.com/p/self-balancing-avl-tree/ , all usual operations like add, delete are implemented, plus concat and split
注释掉的是上面的右旋转和左旋转的代码,下面是我的工作右旋转和我的工作左旋转。我认为上面旋转的逻辑是相反的:
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: