c - AVLツリーのバランス係数の再計算

Question

回転を実行してAVLツリーのバランスをとった後、挿入直後に、すべての親ノードのバランス係数を（適切には-1または1で）変更するにはどうすればよいですか？

AVLツリーの各ノードの構造は次のとおりです。

typedef struct _avlTree
{
 nutbolt part;
 int balanceFactor;
 struct _avlTree *left,*right;
} *avlTree;

ウィキペディアで与えられた定義に従ってバランス係数を設定しました。

各ノードに親ノードへのポインターが必要ですか？

Answer 1

各ノードの親ポインタが必要です。これは、ツリー構造を変更するたびに変更する必要があります。または、再帰によって自動的に、または反復的なアプローチがある場合は配列内で手動で、ルートから開始してすべての訪問済みノードを追跡する必要があります。

トピックの詳細な調査のためにこれを見逃してはいけません：

http://www.stanford.edu/~blp/avl/

Answer 2

インスピレーションを得るためにAVLCライブラリをご覧ください。