Wikipedia

Diferencia entre revisiones de «Árbol AA»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Traducción del pseudocódigo.
Línea 64:
La inserción comienza con la búsqueda normal en un árbol binario y su procedimiento de inserción. Después, a medida que se desenrolla la pila de llamadas, es fácil comprobar la validez del árbol y realizar las rotaciones que se precisen. Si aparece un enlace horizontal izquierdo, se realiza una torsión, y si aparecen dos enlaces horizontales derechos, se realiza una división, posiblemente incrementando el nivel del nuevo nodo raíz del subárbol correspondiente. Observe que el código de muestra realiza un incremento de nivel(T). Lo que hace necesario continuar comprobando la validez del árbol a medida que las modificaciones suben desde las hojas.
 
'''function''' insert '''is'''▼
'''input:''' X, the value to be inserted, and T, the root of the tree to insert it into.
'''output:''' A balanced version T including X.
▲ '''functionfunción''' insertinsertar '''ises'''
''Do the normal binary tree insertion procedure. Set the result of the
'''entrada:''' X, el valor a ser insertado, y T, la raíz del árbol en el cual se insertará.
recursive call to the correct child in case a new node was created or the
'''salida:''' Una versión balanceada de T que incluye a X.
root of the subtree changes.''
'''if''' nil(T) '''then'''▼
''Create a new leaf node with X.''▼
'''return''' node(X, 1, Nil, Nil)▼
'''else if''' X < value(T) '''then'''▼
left(T) := insert(X, left(T))▼
'''else if''' X > value(T) '''then'''
right(T) := insert(X, right(T))▼
'''end if'''▼
''Note that the case of X == value(T) is unspecified. As given, an insert
will have no effect. The implementor may desire different behavior.''
''Haz el procedimiento normal de inserción de un árbol de búsqueda binario.
''Perform skew and then split. The conditionals that determine whether or
Asigna al hijo correcto el resultado de la llamada recursiva en caso de que
not a rotation will occur or not are inside of the procedures, as given
un nodo nuevo fue creado o la raíz del subárbol cambió.''
above.''
T'''si''' := skewnil(T) '''entonces'''
▲ ''CreateCrea auna newnueva leafhoja node withcon X.''
T := split(T)▼
▲ '''returndevuelve''' nodenodo(X, 1, Nil, Nil)
▲ '''ifsi no si''' nilX < valor(T) '''thenentonces'''
▲ rightizquierda(T) := insertinsertar(X, rightizquierda(T))
▲ '''elsesi ifno si''' X <> valuevalor(T) '''thenentonces'''
▲ leftderecha(T) := insertinsertar(X, leftderecha(T))
▲ '''endfin ifsi'''
''Note que el caso X == valor(T) no está especificado. En esta implementación,
no tendrá ningún ejemplo. Se puede cambiar el comportamiento dependiendo de
la implementación.''
''Haz la torsión y luego la división. Las condiciones de si serán hechas ambas
'''return T'''▼
acciones están dentro de los procedimientos ya descritos arriba.''
'''end function'''
▲ T := splittorsión(T)
T := división(T)
▲ '''returndevuelve T'''
'''fin de la función'''
 
== Borrado ==
Obtenido de «https://es.wikipedia.org/wiki/Árbol_AA»