La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. El maximo número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log2(N+1)] y N, siendo N el número de nodos. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.
METODOS DE BUSQUEDA.
• Búsqueda secuencial: Este método sirve para cualquier tipo de array. Consiste en ir recorriendo el contenido del array hasta que se encuentre el dato buscado o se llegue al final. Este método no es muy efectivo, puesto que al enfrentarse a un alto numero de información, si el dato buscado no se encuentra al principio, resulta muy lento.
Ej:
PROGRAM Secuencial;
CONST
Max= 20;
TYPE
Rango= 1..max;
Vector= ARRAY [Rango] of integer;
VAR
V: vector;
Num: Integer;
Pos, cont: Rango;
BEGIN
Pos:=0;
Cont:=pos;
Repeat
Cont:=Cont+1;
If v[cont]=num then
Pos:=cont;
Until (cont=max) OR (pos<>0);
END.
• Búsqueda binária: Este método de búsqueda solo puede utilizarse con un array ordenado. Es más eficaz que la búsqueda secuencial. Consiste en un procedimiento recursivo que compara el elemento buscado con el elemento que ocupe la posición media de un rango comprendido entre el principio y el final de la estructura. Si el elemento buscado es mayor que el comparado se redefinirá el rango entre el elemento que ocupa la posición media y el elemento que ocupa el final del rango, sí no, hace lo mismo pero entre la mitad del rango y el principio. Y así hasta dar con el dato buscado o no encontrarlo.
Ej:
PROCEDURE Binaria (Ini, fin, num: Integer; V:Vector; Var pos:Integer);
Var
Med, Rango: Integer;
Begin
Rango:= (Fin-Ini)+1;
Med:=Rango DIV 2;
Med:=Ini+Med;
IF Rango > 1 Then
If V[Med]= num then
Pos:= med
Else
If num> V[Med] then
Binaria (med+1, fin, num, v, pos)
Else
Binaria (Ini, med-1, num, v, pos)
Else
IF num=V[med] then
Pos:=med
Else
Pos:=0;
End;
METODOS DE ORDENACIÓN.
• Método de la burbuja: Consiste en recorrer el array buscando el nº mayor y colocándolo en la última posición. Después la variable que indica la última posición del array decrementaría una posición y es en esta donde colocaríamos el siguiente nº que se considere mayor.
7
8
2
5
Mayor = 8
7
2
5
8
Mayor = 7
2
5
7
8
Ej:
PROCEDURE Burbuja (n:Integer; Var a: Datos);
Var
Aux, i, k:Integer;
Begin
For k:=1 to n-1 do
Begin
i:=1;
Repeat
If a > a then
Begin
Aux:= a;
A:=a;
A:=aux;
End;
I:= i+1;
Until i > n-k;
End;
End;
Una mejora sobre el algoritmo es hacer que salga del bule si no se ha hecho ninguna modificación al recorrer el array.
No hay comentarios:
Publicar un comentario