AVL Tree вставка - PullRequest
Новая
       1

AVL Tree вставка

0 голосов
/ 12 октября 2010

Как рассчитать коэффициент баланса для конкретного узла, когда я рекурсивно вызываю функцию вставки для добавления узла в дерево 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) );
  }
                ...
}

Ответы [ 2 ]

1 голос
/ 12 октября 2010

Вот очень простой подход. Если была рекурсивная функция 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/

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

1 голос
/ 12 октября 2010

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

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

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

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

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

...