Búsqueda e inserción en arboles binarios en búsqueda

Supongamos que T es un árbol binario de búsqueda. Esta sección discute las operaciones básicas de búsqueda e inserción sobre T, de hecho, la búsqueda e inserción se darán por único algoritmo de búsqueda e inserción. La operación de borrado se trata en la siguiente sección. El recorrido de T es el mismo de un recorrido de binario.

Supongamos un ITEM de información dado. El siguiente algoritmo encuentra la posición de ITEM en el árbol binario de búsqueda T o inserta ITEM como un nuevo nodo en su sitio apropiado en el árbol.

(a) comparar ITEM con el nodo RAIZ N del árbol

                (i) si ITEM

                (ii) si ITEM>N proceder con el hijo derecho de N

(b) repetir el paso (a) hasta que se dé una de las siguientes condiciones.

                 (i) se encuentra un nodo N tal que ITEM=N en este caso se a                  

                  Completado la búsqueda.

                 (ii) se encuentra un subárbol vacio, lo que indica que la búsqueda ha                      

                    Sido infructuosa, y se inserta ITEM en el subárbol vacio.

En otras palabras, se procede hacia abajo desde la raíz R por el árbol T hasta que se encuentra ITEM en T o hasta insertar ITEM como un nodo terminal de T.

Ejemplo   7-14:

(a) Considere el árbol binario de búsqueda T de la figura 7-21. Suponga que se da ITEM=20 simulando el algoritmo anterior, tendríamos los siguientes pasos.

1.- se compra ITEM=20 con la raíz, 38, del árbol T. como 20<38, se procede con el hijo derecho de 38, que es 14.

2.- se compra ITEM=20 con 14. Como 20>14, se procede con el hijo derecho de 14, que es 23.

3.- se compra ITEM=20 con 23. Como 20<23, se procede con el hijo izquierdo de 23, que es 18.

4.- se compra ITEM=20 con 18. Como 20>18 y 18  no tiene hijo derecho, se inserta 20 como hijo derecho de 18.