algorithm - what - random forest tutorial

Equilibrar un BST

Question

Referencia: me hicieron esta pregunta @MS SDE interview, 3rd round. Y no es un problema de tarea. También lo pensé y mencioné mi enfoque a continuación.

Pregunta: Modifique una BST para que esté lo más equilibrada posible. No hace falta mencionar que debes hacerlo lo más eficiente posible.

Sugerencia: el entrevistador dijo que esta es una pregunta lógica, si piensas diferente, obtendrás la respuesta. No hay codificación difícil involucrada.
-> Dicho esto, no creo que esperara que señalara AVL / RB Trees.

Mi solución: propuse que, en el recorrido de un árbol, tome el elemento medio como raíz del árbol nuevo (vamos a llamarlo nueva raíz). Luego vaya a la parte izquierda del elemento medio, tome su elemento medio como raíz del subárbol izquierdo de la nueva raíz con raíz de árbol. Del mismo modo, hazlo por la parte correcta. Hacer esto recursivamente dará la BST balanceada óptima.

¿Por qué lo estoy publicando aquí ?: Pero no estaba satisfecho con la respuesta :( Entonces, ¿hay realmente una manera de hacer esto sin ir por la estrategia de colorear pesos / RB, o solo estaba engañando conmigo? Por favor, ponga tus pensamientos expertos

¿Duplicar? ¡No! Sé que existe esta question pero la solución propuesta por el solicitante es demasiado complicada, y otra habla de los árboles AVL.

Answer 1

"Equilibrado como sea posible" = árbol binario completo (o completo) ¹ . No puedes tener más equilibrio que eso.

La solución es simple: construya un árbol binario completo "vacío" e itere el árbol nuevo y el árbol de entrada (simultáneamente) en inorder-travelling para completar el árbol completo.

Cuando haya terminado, tendrá el árbol más equilibrado que pueda obtener, y la complejidad temporal de este enfoque es O(n) .

EDITAR:
Esto debe hacerse siguiendo estos pasos:

1. Construye un árbol completo ficticio con n nodos. Todos los valores de cada nodo se inicializarán a algún valor de basura.
2. Cree dos iteradores: (1) originalIter para el árbol original, (2) newIter para el árbol nuevo (inicializado con basura). Ambos iteradores devolverán los elementos en el recorrido en orden.

3. Haga lo siguiente para llenar el árbol con los valores del original:

    while (originalIter.hasNext()):
         newIter.next().value = originalIter.next().value

(1) (De Wikipedia): Un árbol binario completo es un árbol binario en el que cada nivel, excepto posiblemente el último, está completamente lleno, y todos los nodos están lo más a la izquierda posible

Answer 2

El algoritmo DSW puede resolver que este es el tiempo O (n). El algoritmo es el siguiente:

1] Using right-rotation operations, turn the tree into a linked list
   (a.k.a. backbone or vine)
2] Rotate every second node of the backbone about its parent to turn
   the backbone into a perfectly balanced BST. 

Reference

Answer 3

Es posible que desee examinar el algoritmo Day-Stout-Warren , que es un algoritmo O (n) -time, O (1) -space para remodelar un árbol de búsqueda binario arbitrario en un árbol binario completo. Intuitivamente, el algoritmo funciona de la siguiente manera:

1. Usando rotaciones de árboles, convierta el árbol en una lista vinculada degenerada.
2. Al aplicar rotaciones selectivas a la lista vinculada, convierte la lista nuevamente en un árbol completamente balanceado.

La belleza de este algoritmo es que se ejecuta en tiempo lineal y requiere solo una carga de memoria constante; de hecho, simplemente cambia la forma del árbol subyacente, en lugar de crear un nuevo árbol y copiar los datos anteriores. También es relativamente simple codificar.

¡Espero que esto ayude!