Ayuda ocupo codigo urgente

[sebas506]

Quisiera saber si alguien tiene algun codigo de eliminar e insertar en un arbol AVL en Java, principalmente el metodo para balancearlo!!!!!

[waltico]

Hola, bueno, sobre tu pregunta de balanceo tengo un codigo que esta echo en Visual C++.

Pues bien tienes que tener presente 2 cosas antes:
1.- El momento de insertar. (verificar el balanceo)
2.- Balancear para la grafica.

///////////////////////////////////////////////////////////////////////////////////
Aqui esta el Codigo del AVLTree.h
#include "AVLNode.h"

class AVLTree
{
AVLNode * m_Root;
bool m_bTaller;
public:
void Draw(CDC* g, int i, int j, int k, int l, int i1, int j1);
AVLNode* RotateLeft(AVLNode* avlnode);
AVLNode* RotateRight(AVLNode* avlnode);
AVLNode* RightBalance(AVLNode *avlnode);
AVLNode* LeftBalance(AVLNode* avlnode);
AVLNode* Insert(AVLNode* avlnode,int i);
void Insert(int i);
AVLTree();
virtual ~AVLTree();
void DeleteNodo(AVLNode* avlnode);

};
///////////////////////////////////////////////////////////////////////////////////
Aqui esta el Codigo del AVLTree.cpp

AVLTree::AVLTree()
{
m_Root = NULL;
m_bTaller = false;
}

AVLTree::~AVLTree()
{

}

void AVLTree::Insert(int i)
{
m_Root = Insert(m_Root,i);
}

AVLNode* AVLTree::Insert(AVLNode *avlnode, int i)
{
if(avlnode == NULL){
avlnode = new AVLNode(i);
m_bTaller = true;
} else
if(i < avlnode->m_iElement)
{
avlnode->m_Left = Insert(avlnode->m_Left,i);
if(m_bTaller)
switch(avlnode->m_iBalance)
{
default:
break;

case 0:
try{
avlnode = LeftBalance(avlnode);
}
catch(...) { }
break;
case 1:
avlnode->m_iBalance = 0;
break;

case 2:
avlnode->m_iBalance = 1;
m_bTaller = false;
break;
}

}else
if(i > avlnode->m_iElement)
{
avlnode->m_Right = Insert(avlnode->m_Right,i);
if(m_bTaller)
switch(avlnode->m_iBalance)
{
default:
break;

case 2:
try{
avlnode = RightBalance(avlnode);
}
catch(...){ }
break;

case 1:
avlnode->m_iBalance = 2;
break;

case 0:
avlnode->m_iBalance = 1;
m_bTaller = false;
break;
}
}
return avlnode;
}

AVLNode* AVLTree::LeftBalance(AVLNode* avlnode)
{
AVLNode *avlnode1 = avlnode->m_Left;
switch(avlnode1->m_iBalance)
{
default:
break;

case 0:
avlnode->m_iBalance = avlnode1->m_iBalance = 1;
avlnode = RotateRight(avlnode);
m_bTaller = false;
break;

case 1:
AfxMessageBox("El arbol ya esta balanceado!");
return NULL;
break;

case 2:
AVLNode* avlnode2 = avlnode1->m_Right;
switch(avlnode2->m_iBalance)
{
case 0:
avlnode->m_iBalance = 2;
avlnode1->m_iBalance = 1;
break;

case 1:
avlnode->m_iBalance = avlnode1->m_iBalance = 1 ;
break;

case 2:
avlnode->m_iBalance = 1;
avlnode1->m_iBalance = 0;
break;
}
avlnode2->m_iBalance = 1;
avlnode->m_Left = RotateLeft(avlnode1);
avlnode = RotateRight(avlnode);
m_bTaller = false;
break;
}
return avlnode;
}

AVLNode* AVLTree::RightBalance(AVLNode *avlnode)
{
AVLNode* avlnode1 = avlnode->m_Right;
switch(avlnode1->m_iBalance)
{
default:
break;

case 2:
avlnode->m_iBalance = avlnode1->m_iBalance = 1;
avlnode = RotateLeft(avlnode);
m_bTaller = false;
break;

case 1:
AfxMessageBox("AVL Tree Error: tree already balaced.");
//return NULL;
break;

case 0:
AVLNode* avlnode2 = avlnode1->m_Right;
switch(avlnode2->m_iBalance)
{
case 2:
avlnode->m_iBalance = 0;
avlnode1->m_iBalance = 1;
break;

case 1:
avlnode->m_iBalance = avlnode1->m_iBalance = 1;
break;

case 0:
avlnode->m_iBalance = 1;
avlnode1->m_iBalance = 2;
break;
}
avlnode2->m_iBalance = 1;
avlnode->m_Right = RotateRight(avlnode1);
avlnode = RotateLeft(avlnode);
m_bTaller = false;
break;
}
return avlnode;
}


AVLNode* AVLTree::RotateLeft(AVLNode *avlnode)
{
AVLNode *avlnode1 = avlnode->m_Right;
avlnode->m_Right = avlnode1->m_Left;
avlnode1->m_Left = avlnode;
return avlnode1;
}


AVLNode* AVLTree::RotateRight(AVLNode *avlnode)
{
AVLNode *avlnode1 = avlnode->m_Left;
avlnode->m_Left = avlnode1->m_Right;
avlnode1->m_Right = avlnode;
return avlnode1;
}

void AVLTree::Draw(CDC *g, int i, int j, int k, int l, int i1, int j1)
{
if(m_Root != NULL)
m_Root->Draw(g,i,j,k,l, i1, j1);
}

///////////////////////////////////////////////////////////////////////////////////
Aqui el codigo del fuente AVLNode.h

#define LEFTHIGHT 0
#define BALANCED 1
#define RIGHTHIGHT 2

class AVLNode
{
public:
CPoint Draw(CDC* g,int i,int j,int k,int l,int i1,int j1);
AVLNode(int i);
virtual ~AVLNode();

int m_iElement;
int m_iBalance;

AVLNode *m_Left;
AVLNode *m_Right;

};


///////////////////////////////////////////////////////////////////////////////////
Aqui el codigo del fuente AVLNode.cpp


AVLNode::AVLNode(int i)
{
m_iElement = i;
m_iBalance = 1;
m_Left = NULL;
m_Right = NULL;
}

AVLNode::~AVLNode()
{

}

CPoint AVLNode::Draw(CDC *g, int i, int j, int k, int l, int i1, int j1)
{
CPoint point(i + ( j * ( k / l )) / 2,i1);
l *= 2;
if(m_Left != NULL){
CPoint point1 = m_Left->Draw(g,point.x,-1,k,l,i1+j1,j1 );
g->MoveTo(point);
g->LineTo(point1);
m_Left->Draw(g,point.x,-1,k,l,i1+j1,j1 );
}
if(m_Right != NULL){
CPoint point2 = m_Right->Draw(g,point.x,1,k,l,i1+j1,j1 );
g->MoveTo(point);
g->LineTo(point2);
m_Right->Draw(g,point.x,1,k,l,i1+j1,j1 );
}
CString str;
RECT rect;
rect.left = point.x - 15;
rect.top = point.y - 15;
rect.bottom = point.y + 15;
rect.right = point.x + 15;
str.Format("%d",m_iElement);
g->Ellipse(&rect);
g->DrawText(str, &rect, DT_CENTER | DT_VCENTER | DT_SINGLELINE); //
return point;
}


Bueno, tienes que crear tu proyecto de MFC
y declarar una variable en tu App de tipo: AVLTree* m_tree;
y una funcion en tu App que se llame Aleatoriamente().

luego la llamas a esa funcion como tu quieras... jiijijii.

void <aplication>::Aleatoriamente()
{
if(m_tree == NULL){
m_tree = new AVLTree();
}
m_tree->Insert(rand()%200);

}

Bien espero que te haya servido de ayuda... si deseas el codigo fuente contactate conmigo.