Pr�ctica 3 de AED2: �rboles Rojo-Negro

Modificar la implementaci�n de �rbol rojo-negro de la clase RedBlackTree del fichero RedBlackTree.java. Para poder compilar dicha clase, se necesitan tambi�n los ficheros: LinkedList.java, ListNode.java, SearchTree.java, Rotations.java, BinaryNode.java, ItemNotFound.java y DuplicateItem.java.

La principal caracter�stica de un �rbol Rojo-Negro es su potencia a la hora de realizar b�squedas basadas en el campo clave del �rbol. Su estructura y organizaci�n permite la localizaci�n de cualquier nodo en el �rbol con un coste O(log(n)), siendo n el n�mero de nodos (claves diferentes) del �rbol.

Utilizaremos la eficiencia de los �rboles Rojo-Negro para la creaci�n de un motor de b�squeda web que sea capaz de indexar todas las palabras contenidas en las p�ginas de un dominio web. El motor realizar� una carga de todas las p�ginas del dominio guardando en el �rbol las palabras que encuentre. Cada palabra encontrada, que ser� el campo clave de un nodo del �rbol, tendr� como dato asociado una lista con las direcciones de todas las p�ginas en las que ha sido encontrada. De esta manera se podr� consultar posteriormente en que p�ginas se encuentran una palabra determinada.

Adem�s del �rbol, utilizaremos una lista auxiliar donde se almacenar�n todas las p�ginas que se van a indexar. En la lista se agregaran aquellos enlaces a nuevas p�ginas que se van encontrando durante la indexaci�n de las p�ginas. La carga del �rbol finalizar� cuando se alcance el final de esta lista auxiliar.

Para eliminar repeticiones en las listas de p�ginas de cada nodo (en el caso de que una palabra se encuentre m�s de una vez en una misma p�gina) y, sobre todo, para evitar bucles infinitos en la indexaci�n que se podr�an producir si se permitieran duplicidades en la lista auxiliar de p�ginas a indexar (se dar�an en el caso de que una p�gina tuviera un v�nculo a una segunda y �sta otra a su vez un v�nculo a la primera), se debe modificar la clase LinkedList.class para que �nicamente se inserte un valor en la lista en el caso de que dicho valor NO se encuentre previamente en la lista.

La estructura de la clase GUVle.java debe ser la siguiente:

Indicar el path completo de la p�gina inicial del portal y almacenarla en la lista de p�ginas a indexar, que estar� vac�a.
Consultar la direcci�n de la siguiente p�gina web de la lista de p�ginas a indexar, abrir la url correspondiente y cargar cada una de las palabras en el �rbol seg�n el siguiente criterio:
1. Si la palabra no se encontraba en el �rbol generar un nuevo nodo en el lugar apropiado del �rbol y agregar a la lista de p�ginas del nodo la p�gina actual
2. Si la palabra se encontraba en el �rbol s�lo hay que agregar a la lista de p�ginas del nodo la p�gina actual
3. Analizar la palabra para ver si contiene la referencia . En caso afirmativo se trata de un enlace a una nueva p�gina, por lo que �sta debe agregarse a la lista de p�ginas a indexar.
Repetir el paso 2 mientras no se alcance el final de la lista de p�ginas a indexar.
Permitir consultar el �rbol con una palabra para conocer las p�ginas donde �sta se encuentra.

Note	Esta pr�ctica dura dos sesiones y debe entregarse a trav�s del aula virtual los ficheros ArbolRojoNegro.java, LinkedList.java y GUVle.java antes del comienzo de la pr�ctica 4