A melhor maneira de calcular a altura de uma árvore de busca binária? (Equilíbrio entre uma AVL-árvore)
https://stackoverflow.com/questions/575772
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou procurando a melhor maneira de calcular o saldo nós em um AVL-árvore . Eu pensei que eu tinha que trabalhar, mas depois de algum inserção heavy / atualizar eu posso ver que ele não está funcionando correta (em tudo).
Este é um tipo de pergunta em duas partes, a primeira parte seria a forma de calcular a altura de uma sub-árvore, eu sei que a definição "A altura de um nó é o comprimento da mais longa trajectória descendente a uma folha a partir desse nó. " e eu entendo isso, mas eu falhar em sua implementação. E para me confundir ainda mais esta citação pode ser encontrada na wikipedia sobre árvore-alturas "Convencionalmente, o valor -1 corresponde a uma sub-árvore sem nós, enquanto que zero corresponde a uma sub-árvore com um nó."
E a segunda parte está ficando o fator de equilíbrio de uma sub-árvore em uma árvore AVL, eu não tenho nenhum problema em entender o conceito, "obter a altura de seus L e R sub-árvores e R subtrair de L ". E este é definido como algo como isto: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
Leitura na wikipedia diz isso sobre as primeiras linhas descrevendo inserções em uma árvore AVL: "Se o fator de equilíbrio torna-se -1, 0 ou 1, em seguida, a árvore ainda está em forma AVL, e sem rotações são necessárias . "
Em seguida, ele continua, dizendo que esta "Se o fator de equilíbrio torna-se 2 ou -2 então a árvore enraizada neste nó é desequilibrado, e é necessária uma rotação árvore. No máximo será necessária uma rotação simples ou dupla para equilibrar a árvore " -. qual não tenho apego problemas.
Mas (sim, há sempre um mas).
Aqui é onde fica confuso, o texto afirma "Se o fator saldo de R é 1, que significa a inserção ocorreu na (externo) do lado direito desse nó e uma rotação à esquerda é necessária" . Mas a partir de m compreensão do texto disse (como eu citei) que, se o fator de equilíbrio estava dentro [-1, 1] então não havia necessidade de equilibrar?
Eu sinto que estou tão perto de compreender o conceito, eu comecei as rotações de árvore para baixo, implementou uma árvore de busca binária normal, e à beira de agarrar AVL-árvores, mas apenas parecem estar faltando que epifania essencial.
Editar:. Exemplos de código são preferíveis às fórmulas acadêmicas como eu sempre tive um tempo mais fácil agarrar algo em código, mas qualquer ajuda é muito apreciada
Editar:. Eu gostaria de poder marcar todas as respostas como "aceite", mas para mim resposta de Nick foi o primeiro que me fez ir "aha"
Solução
Parte 1 - altura
Como starblue diz, a altura é apenas recursiva. Em pseudo-código:
height(node) = max(height(node.L), height(node.R)) + 1
Agora, a altura pode ser definida de duas maneiras. Poderia ser o número de nós no caminho da raiz para esse nó, ou poderia ser o número de ligações. De acordo com a página você referenciou , a definição mais comum é para o número de ligações. Caso em que o código pseudo completa seria:
height(node):
if node == null:
return -1
else:
return max(height(node.L), height(node.R)) + 1
Se você quisesse o número de nós o código seria:
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
De qualquer maneira, o algoritmo reequilíbrio Acho que deve funcionar da mesma.
No entanto, sua árvore será muito mais eficiente ( O (ln (n)) ) se você armazenar e informação de altura atualização na árvore, em vez de calcular cada vez. ( O (n) )
Parte 2 - equilibrando
Quando se diz "Se o fator saldo de R é 1", ele está falando sobre o fator de equilíbrio do ramo direito, quando o fator de equilíbrio no topo é 2. Ele está dizendo a você como escolher se quer fazer uma rotação único ou uma rotação dupla. In (python similares) Pseudo-código:
if balance factor(top) = 2: // right is imbalanced
if balance factor(R) = 1: //
do a left rotation
else if balance factor(R) = -1:
do a double rotation
else: // must be -2, left is imbalanced
if balance factor(L) = 1: //
do a left rotation
else if balance factor(L) = -1:
do a double rotation
Espero que este sentimento marcas
Outras dicas
-
A altura é facilmente implementada por recursão, tomar o máximo da altura das subárvores mais um.
-
O "fator saldo de R" refere-se à sub-árvore direita da árvore que está fora de equilíbrio, eu suponho.
Você não precisa profundezas árvores calcular em tempo real.
Você pode mantê-los como você executar operações.
Além disso, você não realmente de fato tem que manter o controle de profundidade; você pode simplesmente manter o controle da diferença entre as profundezas de árvore esquerdo e direito.
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Apenas mantendo o controle do fator de equilíbrio (diferença entre subárvores esquerda e direita) é eu achei mais fácil a partir de uma programação POV, exceto que triagem para fora o fator de equilíbrio depois de uma rotação é um PITA ...
Aqui está uma forma alternativa de encontrar a altura. Adicionar um atributo adicional para o seu nó chamado altura:
class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}
Agora, vamos fazer um percurso simples em largura da árvore, e manter a atualização do valor da altura para cada nó:
int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;
q.Enqueue(root);
while(q.Count > 0)
{
lastnode = q.Dequeue();
if (lastnode.left != null){
lastnode.left.height = lastnode.height + 1;
q.Enqueue(lastnode.left);
}
if (lastnode.right != null){
lastnode.right.height = lastnode.height + 1;
q.Enqueue(lastnode.right);
}
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}
Cheers,
Bem, você pode calcular a altura de uma árvore com a seguinte função recursiva:
int height(struct tree *t) {
if (t == NULL)
return 0;
else
return max(height(t->left), height(t->right)) + 1;
}
com uma definição adequada da max() e struct tree. Você deve ter o tempo para descobrir por que isso corresponde à definição baseada no caminho de comprimento que você cita. Esta função usa zero como a altura da árvore vazia.
No entanto, para algo como uma árvore AVL, eu não acho que você realmente calcular a altura de cada vez que você precisar. Em vez disso, cada nó da árvore é aumentada com um campo extra que lembra a altura da subárvore enraizada naquele nó. Este campo tem de ser mantido up-to-date como a árvore é modificado por inserções e deleções.
Eu suspeito que, se você calcular a altura de cada vez, em vez de cache-lo dentro da árvore como sugerido acima, que a forma de árvore AVL será correta, mas não terá o desempenho logarítmica esperado.
Aqui é onde fica confuso, o texto afirma "Se o fator saldo de R é 1, que significa a inserção ocorreu na (externo) do lado direito desse nó e é necessária uma rotação à esquerda". Mas a partir de m compreensão do texto disse (como eu citei) que, se o fator de equilíbrio estava dentro [-1, 1], então não havia necessidade de equilibrar?
R é a criança do lado direito do N nó atual.
Se balance(N) = +2, então você precisa de uma rotação de algum tipo. Mas qual a rotação de usar? Bem, isso depende de balance(R): se balance(R) = +1 então você precisa de uma rotação à esquerda na N; mas se balance(R) = -1 então você vai precisar de um double-rotação de algum tipo.
Aqui é onde fica confuso, o texto afirma "Se o fator saldo de R é 1, ele significa a inserção ocorreu no (externa) do lado direito do referido nó e um esquerdo rotação é necessária". Mas a partir de m compreensão do texto disse (como eu citei) que, se o factor de equilíbrio foi a [-1, 1], em seguida, não houve necessidade de equilibrar?
Ok, hora epifania.
Considere o que uma rotação faz. Vamos pensar sobre uma rotação à esquerda.
P = parent
O = ourself (the element we're rotating)
RC = right child
LC = left child (of the right child, not of ourself)
P
\
O
\
RC
/
LC
P
\
RC
/
O
\
LC
10
\
15
\
20
/
18
10
\
20
/
15
\
18
basically, what happens is;
1. our right child moves into our position
2. we become the left child of our right child
3. our right child's left child becomes our right
Agora, a grande coisa que você tem que observar aqui - esta rotação esquerda não mudou a profundidade da ÁRVORE. Nós não estamos mais equilibrada por ter feito isso.
Mas - e aqui está a mágica na AVL - se girado a criança direito da primeira à direita, o que nós temos é este ...
P
\
O
\
LC
\
RC
E agora, se girar O à esquerda, o que temos é esta ...
P
\
LC
/ \
O RC
Mágica! nós conseguimos livrar-se de um nível da árvore -. fizemos o balanço da árvore
Equilibrar os meios de árvores se livrar do excesso de profundidade, e embalando os níveis superiores mais completamente -. Que é exatamente o que acabou de fazer
Essa coisa toda sobre rotações Single / Double é simplesmente que você tem que ter seu sub parecido com isto;
P
\
O
\
LC
\
RC
antes de girar - e você pode ter que fazer uma rotação direito de entrar naquele estado. Mas se você já está nesse estado, você só precisa fazer a rotação esquerda.
Dê BinaryTree<T, Comparator>::Node um membro de dados subtreeHeight, inicializado a 0 em seu construtor, e atualizar automaticamente a cada vez com:
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
left = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (right)
subtreeHeight = std::max (right->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerLeftSubtreeSize;
subtreeHeight = right ? right->subtreeHeight + 1 : 0;
}
}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
right = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (left)
subtreeHeight = std::max (left->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerRightSubtreeSize;
subtreeHeight = left ? left->subtreeHeight + 1 : 0;
}
}
Note que os membros de dados subtreeSize e depthFromRoot também são atualizados.
Essas funções são chamadas quando inserir um nó (todos testados), por exemplo.
template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
if (!node) {
std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
node = newNode;
return newNode;
}
if (getComparator()(t, node->value)) {
std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
node->setLeft(newLeft);
}
else {
std::shared_ptr<Node> newRight = insert(tree, t, node->right);
node->setRight(newRight);
}
return node;
}
Se a remoção de um nó, use uma versão diferente do removeLeft e removeRight substituindo subtreeSize++; com subtreeSize--;. Algoritmos para rotateLeft e rotateRight pode ser adaptada sem muito problema. O seguinte foi testada e aprovada:
template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) { // The root of the rotation is 'node', and its right child is the pivot of the rotation. The pivot will rotate counter-clockwise and become the new parent of 'node'.
std::shared_ptr<Node> pivot = node->right;
pivot->subtreeSize = node->subtreeSize;
pivot->depthFromRoot--;
node->subtreeSize--; // Since 'pivot' will no longer be in the subtree rooted at 'node'.
const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0; // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
if (pivot->right) {
node->subtreeSize -= pivot->right->subtreeSize; // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
}
else
pivot->subtreeHeight = node->subtreeHeight + 1;
node->depthFromRoot++;
decreaseDepthFromRoot(pivot->right); // Recursive call for the entire subtree rooted at pivot->right.
increaseDepthFromRoot(node->left); // Recursive call for the entire subtree rooted at node->left.
pivot->parent = node->parent;
if (pivot->parent) { // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
if (pivot->parent->left == node)
pivot->parent->left = pivot;
else
pivot->parent->right = pivot;
}
node->setRightSimple(pivot->left); // Since pivot->left->value is less than pivot->value but greater than node->value. We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
pivot->setLeftSimple(node);
if (node == root) {
root = pivot;
root->parent = nullptr;
}
}
onde
inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
if (!node)
return;
node->depthFromRoot += adjustment;
adjustDepthFromRoot (node->left, adjustment);
adjustDepthFromRoot (node->right, adjustment);
}
Aqui está todo o código: http://ideone.com/d6arrv
Este BFS-como solução é bastante simples. Simplesmente salta níveis um por um.
def getHeight(self,root, method='links'):
c_node = root
cur_lvl_nodes = [root]
nxt_lvl_nodes = []
height = {'links': -1, 'nodes': 0}[method]
while(cur_lvl_nodes or nxt_lvl_nodes):
for c_node in cur_lvl_nodes:
for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
nxt_lvl_nodes.append(n_node)
cur_lvl_nodes = nxt_lvl_nodes
nxt_lvl_nodes = []
height += 1
return height
