// Este código fuente viene de diversas fuentes traducidas y modificadas
// por diversos programadores. Entre ellos están:
// - Georgi Maximovich Adelson-Velskii (Гео́ргий Макси́мович Адельсо́н-Ве́льский)
// - Yevgueni Mijáilovich Landis (Евгений Михайлович Ландис)
// - A. Colin Day
// - Quentin F. Stout
// - Bette L. Warren
// - Timothy Rolfe
// - Robert Sedgewick
// - Alfons González
// La teoría del árbol binario optimizado (auto balanceable) es de Adelson-Velskii y Landis.
// El código de Colin Day sobre rotaciones y árboles degenerados (vines) fue escrito 
// en Fortran y traducido a Pascal por Stout y Warren.
// Timothy Rolfe tradujo el código Pascal de Stout y Warren a C y lo integró con el resto de
// los algoritmos de Adelson-Velskii y Landis, también en C.
// Mark Weiss y Frank Carrano aportaron algoritmos para atravesar el árbol de forma óptima.
// Sedgewick mejoró el código, optimizándolo especialmente lo relativo al AVL.
// Alfons González ha adaptado el código para compilar con Visual C++ .NET 2008
// en Unicode, eliminando librerías y funciones no soportadas, convirtiendo structs en clases
// y añadiendo funciones concretas para transformarlo en una extended stored
// procedure de SQL Server.
// Parte del código se ha publicado en "Algorithms in C++, Third Edition,"
// de Robert Sedgewick, Addison-Wesley, 1999.
// Otra parte se ha publicado en "Tree Rebalancing in Optimal Time and Space",
// de Quentin F. Stout and Bette L. Warren
// Communications of the ACM, Vol. 29, No. 9
// (September 1986), p. 904.


#ifndef AVL_H        // evitar includes múltiples
#define AVL_H

#include "BST.h"

class AVL : public BST
{  
public:
      AVL(void) : BST() 
	  { 
		  //No hacer nada de momento 
	  }
//    Comprobar si el estado en curso es válido
      int   Valid(void) // La función que trabaja en realidad es privada
      {  
		  return Valid(Root); 
	  }
//    Redefinir (override) las funciones públicas insert y delete para 
//    enlazar con las correspondientes funciones privadas.
      void  Insert(wchar_t * V, int U)
      {  
		  Insert ( Root, V, U ); 
	  }
      void  Delete(wchar_t * V)
      {  
		  Delete ( Root, V ); 
	  }

   private:
//    Redefinir (override) las funciones Insert y Delete 
//    del árbol de búsqueda BST.
      void Insert(BasePtr, wchar_t *, int nUtil);
      void Delete(BasePtr, wchar_t *);
      int  Valid (BasePtr);
//    Reorganizar altura
      void HtAdjust(BasePtr);
//    Si es necesario, realizar rotaciones para reorganizar el árbol
      void AVLadjust(BasePtr);
//    Funciones de rotación (que también tocan alturas)
      void RotateLeft (BasePtr);
      void RotateRight(BasePtr);
public:
	int GetDepth();
	void InOrderFind(wchar_t * szKey, int * pnFoundResults, SRV_PROC *srvproc, FILE * pFile);
	void InOrderDelete(wchar_t *szKey, wchar_t * wszDST, int *pnFoundResults, SRV_PROC *srvproc, FILE * pFile);
	int GetItems();
};

#endif

