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