La mejor manera de calcular la altura de un árbol de búsqueda binaria? (AVL equilibrio de un árbol)
https://stackoverflow.com/questions/575772
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy buscando la mejor manera de calcular un balance de los nodos en un AVL-árbol . Pensé que tenía que trabajar, pero después de algún pesado inserción / actualización Veo que no está funcionando correctamente (en absoluto).
Esto es una especie de pregunta de dos partes, la primera parte sería la forma de calcular la altura de un sub-árbol, sé la definición "La altura de un nodo es la longitud de la trayectoria descendente más larga a una hoja de ese nodo ". y lo entiendo, pero fallan en su aplicación. Y para confundirme aún más esta cita se puede encontrar en Wikipedia sobre árboles alturas "Convencionalmente, el valor -1 corresponde a un subárbol con ningún nodo, mientras que cero corresponde a un subárbol con un nodo."
Y la segunda parte es conseguir que el factor de equilibrio de un sub-árbol en un árbol AVL, no tengo problemas para entender el concepto, "obtener la altura de sus L y R sub-árboles y restar R de L ". Y esto se define como algo parecido a esto: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
Lectura en la wikipedia dice esto en las primeras líneas que describen inserciones en un árbol AVL: "Si el factor de equilibrio se convierte en -1, 0 o 1, entonces el árbol está todavía en forma de AVL, y no hay rotaciones son necesarias . "
A continuación, pasa, diciendo que esto "Si el factor de equilibrio se convierte en 2 o -2 entonces el árbol arraigado en este nodo está desequilibrado, y se necesita una rotación de árboles. A lo sumo será necesaria una rotación simple o doble para equilibrar el árbol " -. lo que no tengo problemas para comprender.
Pero (sí, siempre hay un pero).
Aquí es donde se pone confuso, el texto "Si el factor de equilibrio de R es 1, significa que la inserción se produjo en el lado derecho (externa) de ese nodo y es necesaria una rotación izquierda" . Pero a partir de la comprensión del texto m dijo (como he citado) que si el factor de equilibrio estaba dentro [-1, 1] entonces no había necesidad de equilibrar?
Me siento muy cerca de alcanzar el concepto, he recibido las rotaciones del árbol hacia abajo, implementó un árbol binario de búsqueda normal, y al borde de captar AVL-árboles, pero sólo parece que faltan que epifanía esencial.
Editar:. Los ejemplos de código son preferibles a las fórmulas académicas, ya que siempre he tenido un tiempo más fácil agarrar algo en el código, pero cualquier ayuda es muy apreciada
Editar Me gustaría poder marcar todas las respuestas como "aceptada", pero para mí la respuesta de Nick era el primero que me hizo ir "AHA"
.Solución
Parte 1 - Altura
Como starblue dice, la altura es sólo recursiva. En pseudo-código:
height(node) = max(height(node.L), height(node.R)) + 1
Ahora altura puede definirse de dos maneras. Podría ser el número de nodos en el camino desde la raíz a ese nodo, o podría ser el número de enlaces. De acuerdo con la página al que hizo referencia , la definición más común es que el número de enlaces. En cuyo caso el pseudo código completo sería:
height(node):
if node == null:
return -1
else:
return max(height(node.L), height(node.R)) + 1
Si desea la cantidad de nodos el código sería:
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
De cualquier manera, el algoritmo de reequilibrio Creo que debería funcionar de la misma.
Sin embargo, su árbol será mucho más eficiente ( O (ln (n)) ) si almacena información de altura y actualización en el árbol, en lugar de calcular cada vez. ( O (n) )
Parte 2 - equilibrio
Cuando se dice: "Si el factor de equilibrio de R es 1", se está hablando del factor de equilibrio de la rama derecha, cuando el factor de equilibrio en la parte superior es de 2. Se le está diciendo cómo elegir si hacer una sola rotación o un doble rotación. En (pitón 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 esto tenga sentido
Otros consejos
-
Altura se implementa fácilmente por recursión, tomar el máximo de la altura de los subárboles más uno.
-
El "factor de equilibrio de R" se refiere al subárbol derecho del árbol que está fuera de equilibrio, supongo.
No es necesario para calcular profundidades de árboles sobre la marcha.
Puede mantenerlas a medida que realiza las operaciones.
Por otra parte, no en realidad, de hecho, tiene que mantener un registro de profundidades; sólo tiene que llevar la cuenta de la diferencia entre las profundidades del árbol izquierdo y derecho.
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Simplemente no perder de vista el factor de equilibrio (diferencia entre los subárboles izquierdo y derecho) es más fácil que encontré de un Punto de vista de programación, excepto que la clasificación del factor de equilibrio después de una rotación es un PITA ...
Esto es una forma alternativa de encontrar altura. Añadir un atributo adicional a su nodo llamado altura:
class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}
Ahora, vamos a hacer un simple recorrido primero en amplitud del árbol, y mantener la actualización del valor de la altura para cada nodo:
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
}
Saludos,
Bueno, se puede calcular la altura de un árbol con la siguiente función recursiva:
int height(struct tree *t) {
if (t == NULL)
return 0;
else
return max(height(t->left), height(t->right)) + 1;
}
con una definición apropiada de max() y struct tree. Usted debe tomar el tiempo para averiguar por qué esto corresponde a la definición basada en la longitud del recorrido que usted cita. Esta función utiliza cero a medida que la altura del árbol vacío.
Sin embargo, para algo como un árbol AVL, no creo que realmente calcular la altura cada vez que lo necesite. En su lugar, cada nodo del árbol se ve aumentada con un campo adicional que recuerda la altura del subárbol con raíz en ese nodo. Este campo tiene que ser mantenido hasta a la fecha que el árbol es modificado por las inserciones y deleciones.
Sospecho que, si calcular la altura cada vez que el almacenamiento en caché en lugar de dentro del árbol, como se sugirió anteriormente, que la forma del árbol AVL será correcta, pero no va a tener el rendimiento esperado logarítmica.
Aquí es donde se pone confuso, el texto afirma: "Si el factor de equilibrio de R es 1, significa que la inserción se produjo en el lado derecho (externa) de ese nodo y es necesaria una rotación izquierda". Pero a partir de la comprensión del texto m dijo (como he citado) que si el factor de equilibrio estaba dentro de [-1, 1] entonces no había necesidad de equilibrar?
R es el hijo de la derecha de la N nodo actual.
Si balance(N) = +2, entonces necesita una rotación de algún tipo. Pero el que la rotación de usar? Bueno, depende de balance(R): si balance(R) = +1 entonces usted necesita una izquierda-rotación sobre N; pero si balance(R) = -1 entonces se necesita un doble giro de algún tipo.
Aquí es donde se vuelve confuso, el texto afirma: "Si el factor de equilibrio de R es 1, se significa la inserción se produjo en el lado derecho (externo) de ese nodo y una izquierda es necesaria la rotación". Pero a partir de la comprensión del texto m dijo (como he citado) que si el factor de equilibrio estaba dentro de [-1, 1] entonces no había necesidad de equilibrar?
Bueno, es hora epifanía.
Tenga en cuenta lo que hace un giro. Vamos a pensar en una rotación izquierda.
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
Ahora, la gran cosa que hay que notar aquí - esta rotación izquierda no ha cambiado la profundidad del árbol. No somos más equilibrada por haberlo hecho.
Pero - y aquí está la magia en AVL - si rotamos el hijo derecho a la derecha primer lugar, lo que tendríamos es esto ...
P
\
O
\
LC
\
RC
Y ahora, si rotamos O Izquierda, lo que obtenemos es esto ...
P
\
LC
/ \
O RC
Magia! hemos conseguido deshacerse de un nivel del árbol -. Hemos hecho el balance del árbol
El equilibrio entre los medios de árboles deshacerse del exceso de profundidad, y el embalaje de los niveles superiores más completo - que es exactamente lo que acabamos de hacer
.Esa cosa entera sobre rotaciones simple / doble es simplemente que usted tiene que tener su subárbol con este aspecto;
P
\
O
\
LC
\
RC
antes de girar - y puede que tenga que hacer girar a la derecha para entrar en ese estado. Pero si usted ya está en ese estado, sólo tiene que hacer la izquierda Rotación.
Da BinaryTree<T, Comparator>::Node un miembro de datos subtreeHeight, inicializado a 0 en su constructor, y actualizar automáticamente cada vez con:
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;
}
}
Tenga en cuenta que los miembros de datos subtreeSize y depthFromRoot también se actualizan.
Estas funciones se llaman cuando se inserta un nodo (todo Tested), por ejemplo.
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;
}
Si la eliminación de un nodo, utilizar una versión diferente de removeLeft y removeRight mediante la sustitución de subtreeSize++; con subtreeSize--;. Algoritmos para rotateLeft y rotateRight pueden adaptarse sin mucho problema. El siguiente se ensayó y se pasó a:
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;
}
}
donde
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);
}
Aquí está el código completo: http://ideone.com/d6arrv
Esta solución BFS-como es bastante sencillo. Simplemente saltos niveles, uno por uno.
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
