No entiendo nada ! de arboles "AVL"

[ivanel93]

Hey hola ya he recibido ayuda de ustedes y de nuevo vengo para eso , resulta que no entiendo un nada un código que mi profe me ha proporcionado, es acerca de los arboles(arboles AVL) y sus rotaciones por medio de listas, pero no le entiendo al código amigos ya me han dicho que es algo arcaico y tiene su complejidad, lo que quisiera saber es como funciona el código y en especial la fucnion de "Rotar a la izquierda" y la de "Insert" y el "main" (como esta estructurado) espero contar con su ayuda, dejo el código es "C"

Código (c) [Seleccionar] Expandir

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct node
{
  int num, bal;
  struct node *izq, *der;
}node;

typedef node *ptr;

void rota_izq(ptr *pp)
{
  ptr p=*pp, r;
  *pp=r=p->der;
  p->der=r->izq;
  r->izq=p;
  p->bal--;
  if(r->bal > 0)
     p->bal -= r->bal;
  r->bal--;
  if(p->bal < 0)
     r->bal += p->bal;
}

void rota_der(ptr * pp)
{
  ptr p=*pp, l;
  *pp = l = p->izq;
  p->izq = l->der;
  l->der = p;
  p->bal++;
  if(l->bal < 0)
     p->bal -= l->bal;
  l->bal++;
  if(p->bal > 0)
     l->bal += p->bal;
}

int insert(ptr *pp, int x)
{
  int deltaH=0;
  ptr p=*pp;
  if(p == NULL)
  {
     *pp = p = (ptr)malloc(sizeof(node));
     if(p==NULL)
puts("Not enough memory"), exit(1);
     p->num = x;
     p->bal=0;
     p->izq = p->der = NULL;
     deltaH = 1;
  }
  else
     if(x > p->num)
     {
if(insert(&p->der, x))
{
   p->bal++;
   if(p->bal == 1)
      deltaH=1;
   else
      if(p->bal ==2)
      {
 if(p->der->bal == -1)
    rota_der(&p->der);
 rota_izq(pp);
      }
}
     }
     else
if(x < p->num)
{
   if(insert(&p->izq, x))
   {
      p->bal--;
      if(p->bal == -1)
 deltaH= 1;
      else
 if(p->bal == -2)
 {
    if(p->izq->bal == 1)
rota_izq(&p->izq);
    rota_der(pp);
 }
   }
}
return deltaH;
}

int delnode(ptr *pp, int x)
{
  ptr p=*pp, *qq;
  int deltaH = 0;
  if(p==NULL)
     return 0;
  if(x < p->num)
  {
     if(delnode(&p->izq, x))
     {
p->bal++;
if(p->bal == 0)
   deltaH=1;
else
   if(p->bal==2)
   {
      if(p->der->bal == -1)
 rota_der(&p->der);
      rota_izq(pp);
      if(p->bal == 0)
 deltaH=1;
   }
     }
  }
  else
     if(x>p->num)
     {
if(delnode(&p->der, x))
{
   p->bal--;
   if(p->bal ==0)
      deltaH=1;
   else
      if(p->bal == -2)
      {
 if(p->izq->bal ==1)
    rota_izq(&p->izq);
 rota_der(pp);
 if(p->bal == 0)
    deltaH = 1;
      }
}
     }
     else
     {
if(p->der == NULL)
{
   *pp = p->izq;
   free(p);
   return 1;
}
else
   if(p->izq == NULL)
   {
      *pp = p->der;
      free(p);
      return 1;
   }
   else
   {
      qq = &p->izq;
      while((*qq)->der != NULL)
 qq = &(*qq)->der;
      p->num=(*qq)->num;
      (*qq)->num=x;
      if(delnode(&p->izq, x))
      {
 p->bal++;
 if(p->bal == 0)
    deltaH = 1;
 else
    if(p->bal ==2)
    {
if(p->der->bal == -1)
  rota_der(&p->der);
rota_izq(pp);
deltaH=1;
    }
      }
}
  }
  return deltaH;
}

void printtree(node *p, int pos)
{
  if(p != NULL)
  {
     printtree(p->der, pos+6);
     printf("%*d %d\n", pos, p->num, p->bal);
     printtree(p->izq, pos+6);
  }
}

main()
{
  int x;
  char ch;
  node *root = NULL;

  clrscr();
  puts("\nCada arbol AVL presentado en el problema tiene\n"
"su raiz en la izq. Girela 90 grados\n"
"en el sentido del reloj para obtener su representacion usual\n");
  for(;;)
  {
     printf("Digite un entero, seguido de I para insertar\n"
    "o por D para borrar, o Q para salir: ");
     if(scanf("%d %c",&x, &ch) != 2)
break;
     ch = toupper(ch);
     if(ch == 'I')
insert(&root, x);
     else
if(ch == 'D')
   delnode(&root, x);
     printtree(root, 6);
  }
  return 0;
}



[ivanel93]

Pueden borrar el tema? ya lo solucione.

[Aprendiz-Oscuro]

Si lo has solucionado deberias postear dicha solución, le podria valer a otros usuarios con un problema similar... de eso trata el foro.


Saludos

[ivanel93]

Ok pero es uno de mis apuntes