Árbol de juego

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de septiembre de 2016; las comprobaciones requieren 19 ediciones .
árbol en expansión
Tipo de Madera
año de invención 1985
Autor Daniel Slitor y Robert André Tarjan
Complejidad en los símbolos O
Promedio Lo peor
Consumo de memoria En) En)
Búsqueda O (registro n) O (registro n)
Insertar O (registro n) O (registro n)
Eliminación O (registro n) O (registro n)

Un  árbol splay o skew tree es un árbol de búsqueda binaria que mantiene la propiedad de equilibrio. Este árbol pertenece a la clase de "árboles autorreguladores" que mantienen el equilibrio necesario de ramificación del árbol para garantizar que las búsquedas, adiciones y eliminaciones se puedan realizar en tiempo logarítmico a partir del número de elementos almacenados. Esto se hace sin utilizar ningún campo adicional en los nodos del árbol (como, por ejemplo, en árboles rojo-negro o árboles AVL)., donde los vértices almacenan, respectivamente, el color del vértice y la profundidad del subárbol). En su lugar, la operación de separación, de la que forman parte las rotaciones, se realiza cada vez que se accede al árbol.

El costo contable por una operación con un árbol es.

El árbol en expansión fue inventado por Robert Tarjan y Daniel Slator en 1983.

Operaciones

Splay (expansión)

Funcionamiento básico del árbol. Consiste en trasladar el vértice a la raíz mediante la ejecución secuencial de tres operaciones: Zig, Zig-Zig y Zig-Zag. Denotemos el vértice que queremos mover a la raíz como x , su padre - p , y el padre p (si existe) - g .

Zig: se ejecuta cuando p es la raíz. El árbol se gira a lo largo de un borde entre x y p . Existe solo como un caso límite y solo se ejecuta una vez al final, cuando la profundidad inicial de x era impar.

Zig-Zig: se ejecuta cuando tanto x como p son hijos izquierdos (o derechos). El árbol se rota a lo largo del borde entre g y p , y luego a lo largo del borde entre p y x .

Zig-Zag: se ejecuta cuando x es un hijo derecho y p  es un hijo izquierdo (o viceversa). El árbol se gira a lo largo del borde entre p y x y luego a lo largo del borde entre x y g .

Buscar (buscar un elemento)

La búsqueda se realiza como en un árbol de búsqueda binaria normal. Cuando se encuentra un elemento, lanzamos Splay para él.

Insertar (agregar un elemento)

Ejecute Split() en el elemento que se agrega (consulte Split(), recordatorio: utiliza el elemento mayor o igual más cercano del árbol existente) y cuelgue los árboles resultantes por el elemento que se agregará.

Eliminar (borrar un elemento)

Encontramos un elemento en el árbol, hacemos un Splay para él, hacemos que sus elementos secundarios sean el árbol Merge actual.

Fusionar (fusionar dos árboles)

Para fusionar los árboles T1 y T2, en los que todas las claves en T1 son menores que las claves en T2, hacemos Splay para el elemento máximo de T1, entonces la raíz de T1 no tendrá un hijo derecho. Después de eso, hacemos que T2 sea el hijo derecho de T1.

Split (dividir un árbol en dos partes)

Para dividir el árbol por x, encuentre el elemento más pequeño que sea mayor o igual que x y haga un Splay para él. Después de eso, nos separamos de la raíz del hijo izquierdo y devolvemos los 2 árboles resultantes.

Implementación

Una implementación de un árbol en expansión sería una implementación que usa 3 punteros en cada vértice: un puntero a los hijos derecho e izquierdo, y también al padre. Esto evita la implementación recursiva que, a su vez, ahorrará memoria. La desventaja en este caso es un mayor número de asignaciones para actualizar punteros, lo que puede afectar el rendimiento final.

A continuación se muestra una implementación de un árbol en expansión que utiliza 3 punteros por nodo. Además, en esta implementación, la operación Splay se utiliza en todas las operaciones básicas realizadas en el árbol: al insertar, eliminar y buscar para lograr un mejor equilibrio del árbol.

#ifndef SPLAYTREE_H #define SPLAYTREE_H plantilla < nombre de tipo T > clase SplayTree { privado : estructura SplayNode { Nodo * hijo izquierdo ; Nodo * hijo derecho Nodo * padre ; datos T ; Nodo ( const T & clave = T ()) : hijo izquierdo ( punto nulo ), hijo derecho ( punto nulo ), padre ( punto nulo ), clave ( clave ) {} ~ Nodo () { eliminar hijo izquierdo ; eliminar hijo derecho ; } } * raíz ; privado : SplayNode * _Sucesor ( SplayNode * localRoot ) const { SplayNode * sucesor = localRoot ; if ( sucesor -> hijo derecho != punto nulo ) { sucesor = _Minimum ( sucesor -> hijo derecho ); } más { while ( sucesor != raíz || sucesor != sucesor -> padre -> hijo izquierdo ) { sucesor = sucesor -> padre ; } } volver sucesor ; } SplayNode * _Predecesor ( SplayNode * localRoot ) const { SplayNode * predecesor = localRoot ; if ( predecesor -> hijo izquierdo ! = nullptr ) { predecesor = _Maximum ( predecesor -> hijo izquierdo ); } más { while ( predecesor ! = raíz || predecesor != predecesor -> padre -> hijo derecho ) { predecesor = predecesor -> padre ; } } devolver predecesor ; } SplayNode * _Minimum ( SplayNode * localRoot ) const { SplayNode * mínimo = raíz local ; while ( mínimo -> hijo izquierdo ! = nullptr ) mínimo = mínimo -> hijo izquierdo ; retorno mínimo ; } SplayNode * _Maximum ( SplayNode * localRoot ) const { SplayNode * máximo = raíz local ; while ( máximo -> hijo derecho ! = nullptr ) máximo = máximo -> hijo derecho ; retorno máximo ; } SplayNode * _Buscar ( const T & clave ) { SplayNode * elemento buscado = root ; while ( elemento buscado ! = nullptr ) { if ( ElementoBuscado -> datos < clave ) ElementoBuscado = ElementoBuscado -> HijoDerecho ; else if ( clave < elemento buscado -> datos ) elemento buscado = elemento buscado -> hijo izquierdo ; else if ( elemento buscado -> datos == clave ) { _Splay ( elemento buscado ); volver elemento buscado ; } } devuelve punto nulo ; } void _LeftRotate ( SplayNode * localRoot ) { SplayNode * rightChild = localRoot -> rightChild ; raíz local -> hijo derecho = hijo derecho -> hijo izquierdo ; if ( hijo derecho -> hijo izquierdo != nullptr ) hijo derecho -> hijo izquierdo -> padre = raíz local ; _Transplant ( localRoot , rightChild ); hijo derecho -> hijo izquierdo = localRoot ; hijo derecho -> hijo izquierdo -> padre = hijo derecho ; } void _RightRotate ( SplayNode * localRoot ) { SplayNode * hijo izquierdo = localRoot -> hijo izquierdo ; raíz local -> hijo izquierdo = hijo izquierdo -> hijo derecho ; if ( hijoizquierdo -> hijoderecho != nullptr ) hijoizquierdo -> hijoderecho -> padre = localRoot ; _Transplant ( raíz local , hijo izquierdo ); hijo izquierdo -> hijo derecho = localRoot ; hijoizquierdo -> hijoderecho -> padre = hijoizquierdo ; } void _Transplant ( SplayNode * localParent , SplayNode * localChild ) { if ( localParent -> parent == nullptr ) root = localChild ; else if ( padre local == padre local -> padre -> hijo izquierdo ) padre local -> padre -> hijo izquierdo = hijo local ; else if ( padre local == padre local -> padre -> hijo derecho ) padre local -> padre -> hijo derecho = hijo local ; if ( localChild != nullptr ) niño local -> padre = padre local -> padre ; } void _Splay ( SplayNode * pivotElement ) { while ( elemento pivote ! = raíz ) { if ( pivotElement -> padre == raíz ) { if ( elemento pivote == elemento pivote -> padre -> hijo izquierdo ) { _RightRotate ( pivotElement -> padre ); } else if ( elemento pivote == elemento pivote -> padre -> hijo derecho ) { _LeftRotate ( pivotElement -> padre ); } } más { // Paso en zig-zig. if ( pivotElement == pivotElement -> padre -> hijo izquierdo && pivotElement -> padre == pivotElement -> padre -> padre -> hijo izquierdo ) { _RightRotate ( pivotElement -> padre -> padre ); _RightRotate ( pivotElement -> padre ); } else if ( elemento pivote == elemento pivote -> padre -> hijo derecho && pivotElement -> padre == pivotElement -> padre -> padre -> hijo derecho ) { _LeftRotate ( pivotElement -> padre -> padre ); _LeftRotate ( pivotElement -> padre ); } // Paso en zig-zag. else if ( pivotElement == pivotElement -> padre -> rightChild && pivotElement -> padre == pivotElement -> padre -> padre -> hijo izquierdo ) { _LeftRotate ( pivotElement -> padre ); _RightRotate ( pivotElement -> padre ); } else if ( pivotElement == pivotElement -> padre -> hijo izquierdo && pivotElement -> padre == pivotElement -> padre -> padre -> hijo derecho ) { _RightRotate ( pivotElement -> padre ); _LeftRotate ( pivotElement -> padre ); } } } } público : SplayTree () { raíz = nullptr ; } virtual ~ SplayTree () { eliminar raíz ; } void Insertar ( const T & clave ) { SplayNode * preInsertPlace = nullptr ; SplayNode * insertPlace = root ; while ( insertar lugar ! = nullptr ) { preInsertarLugar = insertarLugar ; if ( insertar lugar -> datos () < clave ) insertar lugar = insertar lugar -> hijo derecho ; else if ( key <= insertPlace -> data ) insertPlace = insertPlace -> leftChild ; } SplayNode * insertElement = new SplayNode ( clave ); insertElement -> parent = preInsertPlace ; if ( preInsertPlace == nullptr ) root = insertElement ; else if ( preInsertPlace -> data < insertElement -> data ) preInsertPlace -> rightChild = insertElement ; else if ( insertarElemento -> datos < preInsertPlace -> datos ) preInsertPlace -> leftChild = insertElement ; _Splay ( insertarElemento ); } anular Eliminar ( const T & clave ) { SplayNode * removeElement = _Search ( clave ); if ( removeElement != nullptr ) { if ( removeElement -> rightChild == nullptr ) _Transplant ( removeElement , removeElement -> leftChild ); else if ( removeElement -> leftChild == nullptr ) _Transplant ( removeElement , removeElement -> rightChild ); más { SplayNode * newLocalRoot = _Minimum ( removeElement -> rightChild ); if ( nuevaRaízLocal -> padre != eliminarElemento ) { _Transplant ( newLocalRoot , newLocalRoot -> rightChild ); newLocalRoot -> rightChild = removeElement -> rightChild ; newLocalRoot -> rightChild -> parent = newLocalRoot ; } _Transplant ( removeElement , newLocalRoot ); newLocalRoot -> hijo izquierdo = removeElement -> hijo izquierdo ; nuevaRaízLocal -> hijo izquierdo -> padre = nuevaRaízLocal ; _Splay ( nuevaRaízLocal ); } eliminar removeElement ; } } bool Buscar ( const T & tecla ) { return _Search ( clave ) != nullptr ; } bool isEmpty () const { return root == nullptr ; } Sucesor T ( const T y clave ) { if ( _Sucesor ( _Buscar ( clave )) != nullptr ) { return _Sucesor ( _Buscar ( clave )) -> getValue (); } más { devolver -1 ; } } T Predecesor ( const T & clave ) { if ( _Predecesor ( _Buscar ( clave )) != nullptr ) { return _Predecessor ( _Search ( key )) -> getValue (); } más { devolver -1 ; } } }; #endif //SPLAYTREE_H

Nota

Un árbol en expansión proporciona una estructura que se modifica a sí misma, una estructura caracterizada por una tendencia a mantener los nodos a los que se accede con frecuencia cerca de la parte superior del árbol, mientras que los nodos a los que se accede con poca frecuencia se acercan a las hojas. Por lo tanto, el tiempo de acceso a los nodos visitados con frecuencia será menor y el tiempo de acceso a los nodos visitados con poca frecuencia será más largo que el promedio.

Un árbol en expansión no tiene ninguna función de equilibrio explícita, pero el proceso de sesgar los nodos hacia la raíz ayuda a mantener el árbol equilibrado.

Véase también

  • Árboles equilibrados (autoequilibrados):
  • Lista de estructuras de datos (árboles)

Literatura

  • Thomas H. Kormen et al.Algoritmos : construcción y análisis. - 2ª ed. - M. : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
  • Daniel Sleater, Robert Tarjan. Una estructura de datos para árboles dinámicos. - Revista de Ciencias de la Computación y Sistemas, 1983. - S. 262-391.