Árbol binario de búsqueda

Árbol binario de búsqueda

Es una estructura de datos no lineal similar a las listas doblemente enlazadas, estructura ramificada con aspecto de árbol, sirve como árbol de decisiones

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.

Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo

'A' es padre de 'B', 'C' y 'D'.

En cuanto a la posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.

Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L',

'M', 'N' y 'O'.

Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C','D', 'E', 'G' y 'J'.

Restricciones

Los árboles con los que trabajará tienen otra característica importante: cada

nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.

Utilidad de los arboles binarios

Es un algoritmo de búsqueda que sirve de base para muchas bases de datos. Por ejemplo, la indexación de la base de datos Oracle, SybaseydeMSSQL se basan enarboles binarios de búsqueda .Internamente guardan una raiz que es el punto de entrada y si el índice buscado es menor, siguen una rama, si es mayor siguen la siguiente. Y así hasta llegar al nodo buscado. Se ha determinado incluso variaciones de este algoritmo que permiten búsquedas mas rápidas y mejor acceso a disco y mas ahorro de espacio de almacenamiento

PREORDEN

INORDEN

POSTORDEN

CLASE 1 2 3 4 5 6 7 8 9 10

PREORDEN 14 8 5 13 12 19 16 63 25 71

INORDEN 5 8 12 13 14 16 19 25 63 71

POSTORDEN 5 12 13 8 16 25 71 63 19 14

...