Creación de un árbol de búsqueda binaria equilibrada

Question

¿Existe algún método para crear un árbol de búsqueda binaria equilibrado?

Ejemplo:

1 2 3 4 5 6 7 8 9 

     5 
    /\ 
    3 etc 
    /\ 
    2 4 
/
1 

Estoy pensando que hay un método para hacer esto, sin necesidad de utilizar los árboles más complejos autobalanceados. De lo contrario, puedo hacerlo por mi cuenta, pero alguien probablemente ya lo haya hecho :)

---

¡Gracias por las respuestas! Este es el código Python definitiva:

def _buildTree(self, keys): 
    if not keys: 
     return None 

    middle = len(keys) // 2 

    return Node(
     key=keys[middle], 
     left=self._buildTree(keys[:middle]), 
     right=self._buildTree(keys[middle + 1:]) 
     ) 

Answer 1

Para cada sub-árbol:

• encontrar el elemento central de la sub-árbol y poner que en la parte superior del árbol.
• Encuentra todos los elementos antes del elemento medio y utiliza este algoritmo recursivamente para obtener el subárbol izquierdo.
• Encuentra todos los elementos después del elemento intermedio y utiliza este algoritmo recursivamente para obtener el subárbol correcto.

Si ordena sus elementos primero (como en su ejemplo) encontrar el elemento medio de un subárbol se puede hacer en tiempo constante.

Este es un algoritmo simple para construir un árbol equilibrado de una sola vez. No es un algoritmo para un árbol de auto-equilibrio.

Aquí hay un código fuente en C# que se puede probar por ti mismo:

public class Program 
{ 
    class TreeNode 
    { 
     public int Value; 
     public TreeNode Left; 
     public TreeNode Right; 
    } 

    TreeNode constructBalancedTree(List<int> values, int min, int max) 
    { 
     if (min == max) 
      return null; 

     int median = min + (max - min)/2; 
     return new TreeNode 
     { 
      Value = values[median], 
      Left = constructBalancedTree(values, min, median), 
      Right = constructBalancedTree(values, median + 1, max) 
     }; 
    } 

    TreeNode constructBalancedTree(IEnumerable<int> values) 
    { 
     return constructBalancedTree(
      values.OrderBy(x => x).ToList(), 0, values.Count()); 
    } 

    void Run() 
    { 
     TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9)); 
     // displayTree(balancedTree); // TODO: implement this! 
    } 

    static void Main(string[] args) 
    { 
     new Program().Run(); 
    } 
} 

Answer 2

Este documento explica en detalle:

árbol Reequilibrio en Optimal tiempo y el espacio
http://www.eecs.umich.edu/~qstout/abs/CACM86.html

También aquí:

One- Tiempo binario Árbol de búsqueda de equilibrio: El algoritmo Day/Stout/Warren (DSW)
http://penguin.ewu.edu/~trolfe/DSWpaper/

Si realmente desea hacerlo sobre la marcha, necesita un árbol de auto-equilibrio.

Si solo quiere construir un árbol simple, sin tener que tomarse la molestia de equilibrarlo, simplemente aleatorice los elementos antes de insertarlos en el árbol.

Answer 3

Hacer la mediana de los datos (o más precisamente, el elemento más cercano en su conjunto a la mediana) la raíz de la árbol. Y así sucesivamente de forma recursiva.