如何实现没有父指针的AVL树的插入?
我看到一些关于AVL的rebalance()
函数实现的文章。
每次插入后,我们应该检查插入节点的祖先是否平衡。
所以我认为,为了检查祖先的余额,我必须了解插入节点的父节点。
但是,我想知道是否有其他方法可以在不使用父指针的情况下做到这一点?
例如,节点结构:
struct Node {
int data;
struct Node *lchild, *rchild; //*parent;
};
I saw some articles about the implementation of AVL's rebalance()
function.
After each insertion, we should check the insertion Node's ancestors for balance.
So I think, in order to check ancestors' balance, I got to know the insertion Node's parent.
But, I wonder is there any other way to do that without having to use the parent pointer?
e.g., the node struct:
struct Node {
int data;
struct Node *lchild, *rchild; //*parent;
};
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
如果我没记错我的数据结构作业:
您所做的是将平衡因子作为 int 存储在节点本身中,它是:
insert(Node subtree) 函数返回一个布尔值,如果插入使子树的高度增加,则该值为 true。当您从递归 insert() 调用返回时,您可以更新平衡因子并重新平衡树。
这可能可以用几个例子来最好地解释:
如果当前节点处于平衡因子 -1 处,则您将插入到右子树中,并且 insert(rchild) 返回true,则:
如果您要插入任一子树,并且 insert(...) 返回 false:
如果当前节点的平衡因子为0,则您将插入到左子树中,并且 insert(lchild) 返回true:
(类似地,如果插入到右子树,平衡因子将变为1.)
如果当前节点的平衡因子为-1,则插入到左子树中,并且 insert(lchild) 返回true :
平衡因子将更改为-2,这意味着您必须通过进行适当的旋转来重新平衡节点。我承认我对四次旋转中的每一次对平衡因子的影响以及插入(当前)将返回的内容一无所知,希望前面的示例充分解释了跟踪节点平衡的方法。
If I remember my data structures homework correctly:
What you do is store the balance factor in the node itself as an int that's either:
You insert(Node subtree) function returns a boolean, which is true if the insertion made the height of subtree increased. You update the balance factor and rebalance the tree as you return from the recursive insert() calls.
This is probably best explained with a few examples:
If the current node is at balance factor -1, you're inserting into the right subtree, and insert(rchild) returns true, you:
If you're inserting into either subtree, and insert(…) returns false:
If the current node's balance factor is 0, you're inserting into the left subtree, and insert(lchild) returns true:
(Analogously, if inserting into the right subtree, the balance factor will change to 1.)
If the current node's balance factor is -1, you're inserting into the left subtree, and insert(lchild) returns true:
The balance factor would change to -2, which means you have to rebalance the node by doing the appropriate rotation. I'll admit I'm drawing a blank at what each of the four rotations will do to the balance factor and what insert(current) will return, hopefully the previous examples explain the approach to tracking the nodes' balance sufficiently.
当你遍历树的时候,你可以维护一个到当前节点的栈
,当你遍历到一个新的节点时,将它添加到栈中,然后你就有了你的祖先。
当处理完一个节点后,将其从堆栈中弹出。
** 编辑 **
对齐注释的详细说明:
创建子项时,这样做:
You can maintain a stack to the current node while you are traversing the tree
When you traverse to a new node, add it to the stack, and then you have your ancestry.
When you finish processing a node, pop it from the stack.
** Edit **
Elaboration for the alignment comment:
when creating children, do it this way:
使用双指针(或对 C++ 要求的指针的引用)应该完全消除对父指针的需要。
Using double pointers (or references to pointers as you asked for C++) should completely eliminate the need for parent pointers.
由于这个问题没有完整的实现,我决定添加一个。这可以通过使用返回当前节点的递归插入来完成。所以,这是代码:
As there's no complete implementation for this question I've decided to add one. It could be done by using a recursive
insert
returning a current node. So, here's the code:我编码的方式是,当您在树中搜索要删除的元素时,临时将您遍历(左或右)的子链接更改为遍历节点堆栈中的链接(实际上是临时父指针) 。然后从该堆栈中弹出每个节点,恢复子指针,并重新平衡。
对于 C++ 编码,请参阅 https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.h 。
对于 C 编码,请参阅 http: 中的宏调用 L__(remove) 生成名称的函数: //wkaras.webs.com/gen_c/cavl_impl_h.txt 。
我认为父指针对于插入没有任何用处。
如果您想删除由节点指针而不是唯一键标识的节点,那么我认为使用父指针可能会更快。
The way I coded it is, as you're searching the tree for the element to delete, temporarily change the child link that you traverse (left or right) to be a link in a stack of traversed nodes (effectively a temporary parent pointer). Then pop each node from this stack, restore the child pointer, and rebalance.
For a C++ encoding, see the remove member function (currently at line 882) in https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.h .
For a C encoding, see the function whose name is generated by the macro invocation L__(remove) in http://wkaras.webs.com/gen_c/cavl_impl_h.txt .
I don't think having a parent pointer is of any use for inserting.
If you want to delete a node identified by a node pointer rather than a unique key, then it will perhaps be faster I think with parent pointers.