AVL树平衡因子的重新计算
在执行旋转以平衡 AVL 树后，在插入后立即更改所有父节点的平衡因子（适当地，按 -1 或 1）？
AVL 树的每个节点都具有以下结构：
typedef struct _avlTree
{
nutbolt part;
int balanceFactor;
struct _avlTree *left,*right;
} *avlTree;
我已根据 Wikipedia< 上给出的定义设置平衡因子/a>.
我需要在每个节点中都有一个指向父节点的指针吗？
After performing a rotation to balance an AVL tree, immediately after an insertion, how can I change the balance factor of all the parent nodes (appropriately, by -1 or 1)?
Each node of the AVL tree has the following structure:
typedef struct _avlTree
{
nutbolt part;
int balanceFactor;
struct _avlTree *left,*right;
} *avlTree;
I have set the balance factor as per the definition given on Wikipedia.
Do I need to have a pointer to the parent node in each node?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您要么需要每个节点的父指针，每当您更改树结构时也需要修改。或者，您需要跟踪从根开始的所有访问过的节点，可以通过递归自动跟踪，也可以在数组中手动跟踪（如果您有迭代方法）。
要深入研究该主题，您不应错过此内容：
http://www.stanford .edu/~blp/avl/
You either need a parent pointer for each node, which will need modification too whenever you change the tree structure. Or you need to keep track of all visited nodes beginning from the root, either automatically by the recursion or manually in an array if you have an iterative approach.
You shouldn't miss this for an in-depth study of the topic:
http://www.stanford.edu/~blp/avl/
也许看看 AVL C 库 寻找灵感？
Maybe have a look at AVL C Library for inspiration?