在执行旋转以平衡 AVL 树后,在插入后立即如何更改所有父节点的平衡因子(适当地,通过 -1 或 1)?
AVL 树的每个节点具有以下结构:
typedef struct _avlTree
{
nutbolt part;
int balanceFactor;
struct _avlTree *left,*right;
} *avlTree;
我已根据Wikipedia上给出的定义设置了平衡因子。
我需要在每个节点中都有一个指向父节点的指针吗?
您要么需要每个节点的父指针,每当您更改树结构时也需要修改它。或者,您需要跟踪从根开始的所有已访问节点,或者通过递归自动跟踪,或者如果您有迭代方法,则在数组中手动跟踪。
你不应该错过这个主题的深入研究:
也许看看AVL C Library以获得灵感?