AVL балансовый коэффициент

Question

AVL балансовый коэффициент

у меня есть класс дерева AVL, я хочу найти коэффициент баланса каждого узла ( balance_factor: node->Left_child->height - node->right_Child->height )

вот мой код

int tree::findBalanceFactor(node p){

int a;
if( p.lchild)   p.lchild->balance_factor=findBalanceFactor( *p.lchild );
if( p.rchild)   p.rchild->balance_factor=findBalanceFactor( *p.rchild );

if( p.rchild && p.lchild )          a=p.balance_factor = p.lchild->height - p.rchild->height ;
if( p.rchild && !p.lchild )         a=p.balance_factor = 0 - p.rchild->height;
if( !p.rchild && p.lchild )         a=p.balance_factor = p.lchild->height;
if( !p.rchild && !p.lchild )        a=p.balance_factor = 0;

cout << "md" << a << endl;
return a;

но в основной функции, когда я печатаю root->balance_factor это показывает мне всегда номер ноль
balance_factor является публичной переменной и в конструкторе я присвоил ноль к этому
что не так с моим кодом ?!

заранее спасибо 🙂

0

avl-tree c++recursion tree

Решение

Другие решения

Есть много более простой способ сделать это, чем тестирование каждой перестановки lchild и rchild:

int tree::findBalanceFactor(node &n) {
int lheight = 0;
int rheight = 0;

if (n.lchild) {
findBalanceFactor(*n.lchild);
lheight = n.lchild->height;
}
if (n.rchild) {
findBalanceFactor(*n.rchild);
rheight = n.rchild->height;
}
n.balance_factor = lheight - rheight;
std::cout << "md " << n.balance_factor << std::endl;
return n.balance_factor;
}

0

Источник

Accepted Answer

Я предполагаю, что причина, почему balance_factor корневого узла всегда 0 из-за этих 2 строк кода в tree::findBalanceFactor метод:

if( p.lchild)   p.lchild->balance_factor=findBalanceFactor( *p.lchild );
if( p.rchild)   p.rchild->balance_factor=findBalanceFactor( *p.rchild );

Я полагаю, что node Структура / класс выглядит примерно так:

struct node {
struct node *lchild;
struct node *rchild;
int balance_factor;
int height;
};

Что происходит в findBalanceFactor( *p.lchild ) а также findBalanceFactor( *p.rchild ) это то, что мы проходим новые копии из p.lchild а также p.rchild в findBalanceFactor (как видно из разыменования указателя), и, следовательно, balance_factor атрибут оригинала p.lchild а также p.rchild не обновляются.

Решение будет заключаться в изменении tree::findBalanceFactor способ принять в указатели на узел, вот так (я позволил себе немного улучшить код):

int tree::findBalanceFactor(node *p) {
int a;
if (p->lchild) {
findBalanceFactor(p->lchild);
}
if (p->rchild) {
findBalanceFactor(p->rchild);
}

if (p->rchild && p->lchild) {
a = p->balance_factor = p->lchild->height - p->rchild->height;
} else if (p->rchild && !p->lchild) {
a = p->balance_factor = 0 - p->rchild->height;
} else if (!p->rchild && p->lchild) {
a = p->balance_factor = p->lchild->height;
} else {
// this is the case for !p->rchild && !p->lchild
a = p->balance_factor = 0;
}

cout << "md" << a << endl;
return a;
}

За p->lchild а также p->rchildнам не нужно устанавливать их balance_factor в другой раз, так как balance_factor каждого node уже установлен в одном из 4 возможных случаев очень if заявление.

0