Estructura De Datos Avanzados

5/17/2007

Estructuras de datos y algoritmos
Estructuras de datos avanzadas

Contenido
n

En esta sección se presentarán algunas estructuraras de datos avanzadas tales como:
n n n n n n

Árboles rojo-negro Listas de salto deterministicas Árboles AA Treaps Árboles k-d Heaps apareados.

1

5/17/2007

Árboles rojo-negro
n n n

Los árboles rojo-negro son una alternativa a losárboles AVL. Las operaciones en árboles rojo-negro toman O(log N) en el peor caso. Un árbol rojo-negro es un árbol binario de búsqueda con las siguientes propiedades:
1. 2. 3. 4.

Cada nodo se colorea rojo o negro. La raíz es negra. Si un nodo es rojo, sus hijos son negros. Todas la rutas desde un nodo hasta una referencia nula o una hoja tienen la misma cantidad de nodos negros.

n

Comoconsecuencia de esta reglas la altura de un árbol rojo-negro es cuando mucho 2 log(N+1).

Un árbol rojo-negro
30

15 10 20 60

70

85 65 80

5

50 40 55

90

Secuencia de inserción: 10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55

2

5/17/2007

Inserción de abajo hacia arriba
n

n n

n

Para insertar un nodo en un árbol rojo-negro se agrega una hoja en la ubicacióncorrespondiente. Esta hoja se colorea roja para evitar violar la regla 4. Si el padre es negro la inserción ha terminado. De lo contrario, se esta violando la regla 3. En este caso se debe ajustar el árbol mediante rotaciones y cambios de color hasta dar cumplimiento a todas las reglas.

Árboles rojo-negro de arriba hacia abajo
n

n

n

El procedimiento de inserción de abajo hacia arribarequiere mantener la ruta recorrida en una pila o tener enlaces de los hijos a los padres. Para evitar esto, se usara un algoritmo que reestructura el árbol a medida que desciende hasta el punto de inserción. Si se encuentra un nodo X cuyos hijos son rojos se hace X rojo y sus hijos negros. Si lo anterior produce una violación de la regla 3 esta se resuelve mediante las rotaciones apropiadas.

35/17/2007

Rotaciones en árboles rojo-negro
G P X A B G P X A B1 B2 S C A B1 B2 S C P S C X A B X G P G S C

Nodos rojo-negro
class RedBlackNode { // Constructors RedBlackNode( Comparable theElement ) { this( theElement, null, null ); } RedBlackNode(Comparable theElement, RedBlackNode lt, RedBlackNode rt) { element = theElement; left = lt; right = rt; color = RedBlackTree.BLACK; } //Friendly data; accessible by other package routines Comparable element; // The data in the node RedBlackNode left; // Left child RedBlackNode right; // Right child int color; // Color }

4

5/17/2007

Clase RedBlackTree
public class RedBlackTree { private RedBlackNode header; private static RedBlackNode nullNode; static // Static initializer for nullNode { nullNode = new RedBlackNode( null); nullNode.left = nullNode.right = nullNode; } static final int BLACK = 1; // Black must be 1 static final int RED = 0; // Used in insert routine and its helpers private static RedBlackNode current; private static RedBlackNode parent; private static RedBlackNode grand; private static RedBlackNode great; public RedBlackTree( Comparable negInf ) { header = new RedBlackNode( negInf ); header.left =header.right = nullNode; }

Clase RedBlackTree
public void insert( Comparable item ) { current = parent = grand = header; nullNode.element = item; while( current.element.compareTo( item ) != 0 ) { great = grand; grand = parent; parent = current; current = item.compareTo( current.element ) < 0 ? current.left : current.right; // Check if two red children; fix if so if( current.left.color == RED &¤t.right.color == RED ) handleReorient( item ); } if( current != nullNode ) // Insertion fails if already present return; current = new RedBlackNode( item, nullNode, nullNode ); if( item.compareTo( parent.element ) < 0 ) // Attach to parent parent.left = current; else parent.right = current; handleReorient( item ); }

5

5/17/2007

Clase RedBlackTree
private void handleReorient(...