Un árbol exponencial es casi idéntico a un árbol de búsqueda binario , con la excepción de que la dimensión del árbol no es la misma en todos los niveles. En un árbol de búsqueda binario normal, cada nodo tiene una dimensión ( d ) de 1 y tiene 2 d hijos. En un árbol exponencial, la dimensión es igual a la profundidad del nodo, y el nodo raíz tiene d = 1. Entonces, el segundo nivel puede contener cuatro nodos, el tercero puede contener ocho nodos, el cuarto 16 nodos, y así sucesivamente.
|
árbol |
1995 |
Arne Andersson |
|
Algoritmo | | Promedio | Peor de los casos |
---|
Espacio | | O ( n ) | O ( n ) |
---|
Buscar | | O (min ( √ log n , log n / log w + log log n , log w log log n )) | O (min ( √ log n , log n / log w + log log n , log w log log n )) |
---|
Insertar | | O (min ( √ log n , log n / log w + log log n , log w log log n )) | O (min ( √ log n , log n / log w + log log n , log w log log n )) |
---|
Borrar | | O (min ( √ log n , log n / log w + log log n , log w log log n )) | O (min ( √ log n , log n / log w + log log n , log w log log n )) |
---|
|