Вставка AVL дерева

Question

Как рассчитать коэффициент баланса для определенного узла, когда я рекурсивно вызываю функцию вставки для добавления узла в дерево AVL. Я не начал по логике вращения. Я просто хочу рассчитать коэффициенты баланса.

В моей текущей попытке я вынужден хранить высоты левых & правых поддеревов, так как я не могу найти коэффициент останова без них.

typedef struct _avlTree 
{ 
int num; 
int balFactor; 
int height[2]; // left & right subtree heights 
struct _avlTree *left,*right; 
} *avlTree; 


int avlAdd(avlTree a,avlTree aNew) 
{ 
       ... 
    if(a->left == NULL) // left subtree insertion case 
    { 
    a->left = aNew; 
    return(1); 
    } 
    else 
    { 
    a->height[0] = avlAdd(a->left,aNew); 
    a->balFactor = a->height[0] - a->height[1]; 
    return((a->height[0]>a->height[1]) ? (a->height[0]+1) : (a->height[1]+1)); 
    } 
       ... 
} 

Answer 1

Коэффициент баланса представляет собой разность высот между правым и левым поддеревьями узла.

При создании нового узла инициализируйте коэффициент баланса равным нулю, так как он сбалансирован (у него нет поддеревьев).

Если вы вставляете новый узел вправо, увеличить коэффициент баланса на 1.

Если вы вставляете новый узел влево, уменьшить коэффициент баланса на 1.

После восстановления равновесия (вращение), если вы увеличиваете высоту поддерева на этом узле, рекурсивно распространяйте увеличение высоты на родительский узел.

Answer 2

Вот очень простой подход. Если есть рекурсивная height() функция, то коэффициент баланса может быть вычислена просто как

node->balFactor = height(node->right) - height(node->left); 

Это не самый лучший подход, хотя, так как сложность этого подхода заключается в том O(h) где h является высота node в AVL дерево. Для лучшего подхода, большая дискуссия требуется :)

Есть множество ресурсов на AVL дерева в Интернете, избранный немногие: осуществление

1. http://en.wikipedia.org/wiki/AVL_tree
2. C: http://www.stanford.edu/~blp/avl/libavl.html
3. Анимация: http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html
4. Анимация: http://www.strille.net/works/media_technology_projects/avl-tree_2001/

BTW, функция avlAdd() выглядит неправильно. Я не вижу, где aNew->num сравнивается с a->num. Должно зависеть от того, идти ли левое поддерево или правое поддерево. Данный код, кажется, добавляет к левому поддереву безоговорочно.