AYUDA CON EL METODO DE ELIMINAR EN UN ARBOL AVL
Publicado por roberto (1 intervención) el 01/06/2020 22:56:44
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class AVLNode { AVLNode izquierda, derecha;String letra;
int altura;
/* Constructor vacio */public AVLNode() {
} /* Constructor lleno */public AVLNode(String n) {
izquierda = null; derecha = null; letra = n; altura = 0; }}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
public class AVLTree {AVLNode raiz;
/* Constructor */public AVLTree() {
raiz = null; } /* Metodo que checa si el arbol esta vacio */public boolean esVacio() {
return raiz == null;
} /* Hace el arbol logicamente vacio */public void hacerVacio() {
raiz = null; } /* Metodo para insertar dato */public void insertar(String letra) {
raiz = insertar(letra, raiz);
} /* Metodo para obtener el factor de equlibrio */public int FE(AVLNode t) {
if (t == null) {
return -1;} else {
return t.altura; } } /* Metodo complementario de FE para obtener la altura maxima izquierda/derecha del nodo */public int max(int lhs, int rhs) {
if (lhs > rhs) {
return lhs;
} else {
return rhs;
} } /* Metodo para insertar datos recursivamente */public AVLNode insertar(String x, AVLNode t) {
if (t == null) {
t = new AVLNode(x);
} else if (x.compareTo(t.letra) < 0) {
t.izquierda = insertar(x, t.izquierda);
if (FE(t.izquierda) - FE(t.derecha) == 2) {
if (x.compareTo(t.izquierda.letra) < 0) {
t = rotacionIzquierda(t);
} else {
t = dobleIzquierda(t);
} }} else if (x.compareTo(t.letra) > 0) {
t.derecha = insertar(x, t.derecha);
if (FE(t.derecha) - FE(t.izquierda) == 2) {
if (x.compareTo(t.derecha.letra) > 0) {
t = rotacionDerecha(t);
} else {
t = dobleDerecha(t);
} } } else ; // Duplicado; no hace nadat.altura = max(FE(t.izquierda), FE(t.derecha)) + 1;
return t;
} /* Rotacion izquierda */public AVLNode rotacionIzquierda(AVLNode k2) {
AVLNode k1 = k2.izquierda;
k2.izquierda = k1.derecha;
k1.derecha = k2;
k2.altura = max(FE(k2.izquierda), FE(k2.derecha)) + 1;
k1.altura = max(FE(k1.izquierda), k2.altura) + 1;
return k1;
} /* Rotacion derecha */public AVLNode rotacionDerecha(AVLNode k1) {
AVLNode k2 = k1.derecha;
k1.derecha = k2.izquierda;
k2.izquierda = k1;
k1.altura = max(FE(k1.izquierda), FE(k1.derecha)) + 1;
k2.altura = max(FE(k2.derecha), k1.altura) + 1;
return k2;
} /* Rotacion doble iquierda */public AVLNode dobleIzquierda(AVLNode k3) {
k3.izquierda = rotacionDerecha(k3.izquierda);
return rotacionIzquierda(k3);
} /* Rotacion doble derecha */public AVLNode dobleDerecha(AVLNode k1) {
k1.derecha = rotacionIzquierda(k1.derecha);
return rotacionDerecha(k1);
} /* Recorrido inOrden */public void inorden() {
inorden(raiz);
}public void inorden(AVLNode r) {
if (r != null) {
inorden(r.izquierda);
System.out.print(r.letra + " ");
inorden(r.derecha);
} } /* Recorrido en preOrden */public void preorden() {
preorden(raiz);
}public void preorden(AVLNode r) {
if (r != null) {
System.out.print(r.letra + " ");
preorden(r.izquierda);
preorden(r.derecha);
} } /* Recorrido postOrden */public void postorden() {
postorden(raiz);
}public void postorden(AVLNode r) {
if (r != null) {
postorden(r.izquierda);
postorden(r.derecha);
System.out.print(r.letra + " ");
} }}Valora esta pregunta
0