Пересчет балансового коэффициента в дереве 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

Может быть, посмотрите на AVL C Library для вдохновения?