algorithm - rotacion - insertar arbol binario de busqueda

La mejor forma de calcular la altura en un árbol de búsqueda binario?(equilibrando un árbol AVL)

Question

Estoy buscando la mejor manera de calcular un balance de nodos en un AVL-tree . Pensé que lo tenía funcionando, pero después de algunas inserciones / actualizaciones pesadas puedo ver que no funciona correctamente (en absoluto).

Esta es una especie de pregunta en dos partes, la primera parte sería cómo calcular la altura de un subárbol, conozco la definición "La altura de un nodo es la longitud de la trayectoria descendente más larga hacia una hoja desde ese nodo " y lo entiendo, pero no lo logro. Y para confundirme aún más, esta cita se puede encontrar en wikipedia sobre alturas de árbol "Convencionalmente, el valor -1 corresponde a un subárbol sin nodos, mientras que cero corresponde a un subárbol con un nodo".

Y la segunda parte es obtener el factor de equilibrio de un subárbol en un árbol AVL, no tengo problemas para entender el concepto, "obtener la altura de tus L y R y restar R de L " . Y esto se define como algo como esto: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

Leer en wikipedia dice esto en las primeras líneas que describen las inserciones en un árbol AVL: "Si el factor de equilibrio se convierte en -1, 0 o 1, entonces el árbol todavía está en forma AVL, y no se necesitan rotaciones".

Luego continúa, diciendo esto: "Si el factor de equilibrio se convierte en 2 o -2, entonces el árbol enraizado en este nodo está desequilibrado y se necesita una rotación de árbol. A lo más se necesitará una rotación simple o doble para equilibrar el árbol". - que no tengo problemas para entender

Pero (sí, siempre hay un pero).

Aquí es donde se vuelve confuso, el texto dice "Si el factor de equilibrio de R es 1, significa que la inserción se produjo en el lado derecho (externo) de ese nodo y se necesita una rotación hacia la izquierda" . Pero desde mi entendimiento, el texto decía (como lo mencioné) que si el factor de equilibrio estaba dentro de [-1, 1] entonces no había necesidad de equilibrar?

Siento que estoy tan cerca de captar el concepto, he reducido la rotación de árboles, implementado un árbol de búsqueda binaria normal, y al borde de agarrar árboles AVL, pero parece que me falta esa epifanía esencial.

Editar: Los ejemplos de código son preferibles a las fórmulas académicas, ya que siempre me ha resultado más fácil captar algo en código, pero cualquier ayuda es muy apreciada.

Editar: Me gustaría poder marcar todas las respuestas como "aceptadas", pero para mí la respuesta de NIck fue la primera que me hizo decir "aha".

Answer 1

Aquí es donde se vuelve confuso, el texto dice "Si el factor de equilibrio de R es 1, significa que la inserción se produjo en el lado derecho (externo) de ese nodo y se necesita una rotación hacia la izquierda". Pero desde mi entendimiento, el texto decía (como lo mencioné) que si el factor de equilibrio estaba dentro de [-1, 1], ¿entonces no había necesidad de equilibrar?

Bien, tiempo de epifanía.

Considera lo que hace una rotación. Pensemos en una rotación a la 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, lo más importante que tienes que notar aquí - esta rotación a la izquierda NO HA CAMBIADO LA PROFUNDIDAD DEL ÁRBOL. No estamos más equilibrados por haberlo hecho.

Pero, y aquí está la magia en AVL, si rotáramos al niño correcto hacia la derecha PRIMERO, lo que tendríamos es esto ...

 P
/
O
/
LC
/
RC

Y AHORA si giramos O a la izquierda, lo que obtenemos es esto ...

 P
/
LC
/ /
O RC

¡Magia! hemos logrado deshacernos de un nivel del árbol: hemos logrado el equilibrio entre árboles .

Equilibrar el árbol significa eliminar el exceso de profundidad y empaquetar los niveles superiores de forma más completa, que es exactamente lo que acabamos de hacer.

Todo eso de rotaciones simples / dobles es simplemente que tienes que tener tu subárbol como este;

 P
/
O
/
LC
/
RC

antes de girar, y es posible que deba girar a la derecha para entrar en ese estado. Pero si ya estás en ese estado, solo tienes que girar a la izquierda.

Answer 2

Aquí es donde se vuelve confuso, el texto dice "Si el factor de equilibrio de R es 1, significa que la inserción se produjo en el lado derecho (externo) de ese nodo y se necesita una rotación hacia la izquierda". Pero desde mi entendimiento, el texto decía (como lo mencioné) que si el factor de equilibrio estaba dentro de [-1, 1], ¿entonces no había necesidad de equilibrar?

R es el hijo derecho del nodo actual N

Si balance(N) = +2 , entonces necesitas una rotación de algún tipo. Pero, ¿qué rotación usar? Bueno, depende del balance(R) : si el balance(R) = +1 entonces necesitas una rotación a la izquierda en N ; pero si balance(R) = -1 entonces necesitarás una doble rotación de algún tipo.

Answer 3

Parte 1 - altura

Como dice starblue, la altura es recursiva. En pseudo-código:

height(node) = max(height(node.L), height(node.R)) + 1

Ahora la altura se puede definir de dos maneras. Podría ser la cantidad de nodos en la ruta desde la raíz hasta ese nodo, o podría ser la cantidad de enlaces. De acuerdo con la página a la que hace referencia , la definición más común es la cantidad 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 quisiera 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 igual.

Sin embargo, su árbol será mucho más eficiente ( O (ln (n)) ) si almacena y actualiza la información de altura en el árbol, en lugar de calcularla cada vez. ( O (n) )

Parte 2 - equilibrio

Cuando dice "Si el factor de equilibrio de R es 1", está hablando del factor de equilibrio de la rama derecha, cuando el factor de equilibrio en la parte superior es 2. Le indica cómo elegir si hacer una sola rotación o una doble rotación. En pseudocódigo (tipo python):

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

Answer 4

Aquí hay una forma alternativa de encontrar la altura. Agregue 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, haremos un recorrido cruzado simple del árbol y seguiremos actualizando el valor de 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
}

Aclamaciones,

Answer 5

Bueno, puedes 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 . Debe tomarse el tiempo para descubrir por qué esto corresponde a la definición basada en la longitud del camino que cita. Esta función usa cero como la altura del árbol vacío.

Sin embargo, para algo como un árbol AVL, no creo que realmente calcules la altura cada vez que la necesites. En cambio, cada nodo de árbol se aumenta con un campo adicional que recuerda la altura del subárbol enraizado en ese nodo. Este campo debe mantenerse actualizado a medida que el árbol se modifica mediante inserciones y eliminaciones.

Sospecho que, si calcula la altura cada vez en lugar de almacenarla en el árbol como se sugirió anteriormente, la forma del árbol AVL será correcta, pero no tendrá el rendimiento logarítmico esperado.

Answer 6

Esta solución tipo BFS es bastante simple. Simplemente salta niveles uno a 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

Answer 7

No necesita calcular las profundidades de los árboles sobre la marcha.

Puede mantenerlos mientras realiza operaciones.

Además, de hecho no tienes que mantener un seguimiento de las profundidades; simplemente puede realizar un seguimiento de la diferencia entre las profundidades del árbol izquierdo y derecho.

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

Solo el seguimiento del factor de equilibrio (diferencia entre los subárboles izquierdo y derecho) me resulta más fácil desde 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 ...

Answer 8

Proporcione a BinaryTree<T, Comparator>::Node un subtreeHeight miembro de datos, inicializado a 0 en su constructor, y actualice 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 invocan cuando se inserta un nodo (todo probado), 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 elimina un nodo, use una versión diferente de removeLeft y removeRight reemplazando subtreeSize++; con subtreeSize--; . Los algoritmos para rotateLeft y rotateRight se pueden adaptar sin muchos problemas. Lo siguiente fue probado y aprobado:

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;
}
}

dónde

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

Answer 9

• La altura se implementa fácilmente por recursión, tome 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á desequilibrado, supongo.