22. Árboles Binarios de Búsqueda#
Definición de Árbol Binario de Búsqueda
Un árbol binario de búsqueda es un árbol binario que cumple con las siguientes propiedades para cada nodo N:
Todos los nodos en el subárbol izquierdo de N tienen valores menores que el valor de N.
Todos los nodos en el subárbol derecho de N tienen valores mayores que el valor de N.
Ambos subárboles (izquierdo y derecho) deben ser también árboles binarios de búsqueda.
En la siguiente figura se muestran dos árboles binarios, el de la izquierda cumple con la propiedad de ABB y por lo tanto es un árbol binario de búsqueda, mientras que el de la derecha no cumple con la propiedad ya que el nodo (8) es mayor que el (7) que se encuentra en la raíz del árbol y por lo tanto no se cumple que los todos los nodos del subárbol izquierdo son menores que la raíz.
El subárbol de la izquierda cuya raíz es (2) si es ABB y el de la derecha cuya raiz es (9) también es ABB, sin embargo el árbol completo no es un ABB.
El recorrido inorden de un árbol binario de búsqueda produce una secuencia ordenada de los valores almacenados en el árbol. Esto se debe a que al visitar el subárbol izquierdo, el nodo raíz y luego el subárbol derecho, se garantiza que los nodos se procesen en orden ascendente.
Por ejemplo en la siguiente figura se muestran dos árboles binarios de búsqueda que tienen el mismo recorrido inorden: 1, 2, 3, 5, 7, 9. Los árboles son diferentes porque los elementos se insertaron en diferente orden, sin embargo al ser un ABB el recorrido inorden es el mismo.
Figura 22.1 Dos árboles binarios de búsqueda con el mismo recorrido inorden#
22.1. Operaciones en un árbol binario de búsqueda#
Las operaciones más comunes en un árbol binario de búsqueda son:
Inserción: Agregar un nuevo nodo al árbol manteniendo la propiedad de ABB.
Búsqueda: Encontrar un nodo en el árbol.
Eliminación: Quitar un nodo del árbol manteniendo la propiedad de ABB.
22.1.1. Inserción#
La inserción en un árbol binario de búsqueda se realiza de manera recursiva. Se compara el valor a insertar con el valor del nodo actual y se decide si ir al subárbol izquierdo o derecho. Si el subárbol correspondiente está vacío, se inserta el nuevo nodo.
Para insertar un nuevo nodo en un árbol binario de búsqueda, se sigue el siguiente algoritmo:
1FUNCION InsertarABB(raiz, valor)
2 SI raiz ES nula ENTONCES
3 raiz ← CrearNodo(valor)
4 SINO SI valor < raiz.valor ENTONCES
5 raiz.izquierdo ← InsertarABB(raiz.izquierdo, valor)
6 SINO SI valor > raiz.valor ENTONCES
7 raiz.derecho ← InsertarABB(raiz.derecho, valor)
8 FIN SI
9 RETORNAR raiz
10FIN FUNCION
En la siguiente animación se observa la inserción del valor (6) en un árbol binario de búsqueda.
Se compara el valor (6) con la raíz (7) y como (6) es menor se desciende al subárbol izquierdo.
Se compara el valor (6) con la raíz (2) del subárbol izquierdo y como (6) es mayor se desciende al subárbol derecho.
Se compara el valor (6) con la raíz (5) del subárbol derecho y como (6) es mayor se desciende al subárbol derecho.
Como el subárbol derecho de (5) es nulo se inserta el nodo (6) como hijo derecho de (5).
Importante
La inserción no permite valores duplicados. Si se requiere contar los elementos repetidos en el árbol, se puede modificar el algoritmo para que en lugar de insertar un nuevo nodo, se incremente un contador en el nodo existente.
La inserción de un nuevo nodo siempre se realiza en una hoja del árbol, es decir, un nodo que no tiene hijos. Esto asegura que la estructura del árbol se mantenga y que la propiedad de ABB se respete.
22.1.2. Búsqueda#
La búsqueda en un árbol binario de búsqueda también se realiza de manera recursiva. Se compara el valor buscado con el valor del nodo actual y se decide si ir al subárbol izquierdo o derecho. Si el valor es igual al del nodo actual, se ha encontrado el nodo, si en cambio se llega a un nodo nulo, el valor no está en el árbol.
1FUNCION BuscarABB(raiz, valor)
2 SI raiz ES nula ENTONCES
3 RETORNAR nula
4 SINO SI raiz.valor = valor ENTONCES
5 RETORNAR raiz
6 SINO SI valor < raiz.valor ENTONCES
7 RETORNAR BuscarABB(raiz.izquierdo, valor)
8 SINO
9 RETORNAR BuscarABB(raiz.derecho, valor)
10 FIN SI
11FIN FUNCION
En la siguiente animación se observa la búsqueda del valor (4) que no se encuentra.
22.1.3. Eliminación#
La eliminación de un nodo en un árbol binario de búsqueda es un poco más compleja que la inserción y la búsqueda. Existen tres casos a considerar:
- El nodo a eliminar es una hoja (no tiene hijos)
En este caso, simplemente se elimina el nodo. En el ejemplo se elimina la hoja (6).
Figura 22.2 Eliminación de un nodo hoja#
- El nodo a eliminar tiene un solo hijo
En este caso, se reemplaza reemplaza el nodo a eliminar por su hijo. Esto se hace actualizando el puntero del padre del nodo a eliminar para que apunte al hijo del nodo a eliminar. En el ejemplo se elimina el nodo (5) que tiene sólo un hijo izquierdo (3) y se reemplaza por su hijo.
Figura 22.3 Eliminación de un nodo con un solo hijo#
- El nodo a eliminar tiene dos hijos
En este caso, se busca el nodo más pequeño en el subárbol derecho del nodo a eliminar (sucesor) o el nodo más grande en el subárbol izquierdo (predecesor). Luego, se reemplaza el valor del nodo a eliminar por el valor del sucesor o predecesor y se elimina el sucesor o predecesor (que siempre va a ser una hoja o a lo sumo va tener un sólo hijo).
En la siguiente figura se observa la eliminación de la raíz del árbol, el nodo (7).
Figura 22.4 Eliminación de un nodo con dos hijos#
Para ubicar al predecesor (es decir el mayor elemento del subárbol izquierdo), se debe bajar al subárbol izquierdo y luego seguir bajando por las ramas derechas hasta llegar a un nodo que no tenga hijo derecho. En este caso el predecesor es (6).
En cambio para ubicar al sucesor (es decir el menor elemento del subárbol derecho), se debe bajar al subárbol derecho y luego seguir bajando por las ramas izquierdas hasta llegar a un nodo que no tenga hijo izquierdo. En este caso el sucesor es (9).
En el ejemplo se eligió reemplazar la raíz con el predecesor y eliminar el nodo (6).
Importante
Cuando se elimina un nodo con dos hijos, el nodo no se elimina directamente, sino que se reemplaza por su predecesor o sucesor. Esto asegura mantener la estructura del ABB
A continuación se presenta el algoritmo de eliminación de un nodo en un árbol binario de búsqueda:
1FUNCION EliminarABB(raiz, valor)
2 SI raiz ES nula ENTONCES
3 RETORNAR nula
4 // Buscar el nodo a eliminar
5 SINO SI valor < raiz.valor ENTONCES
6 raiz.izquierdo ← EliminarABB(raiz.izquierdo, valor)
7 SINO SI valor > raiz.valor ENTONCES
8 raiz.derecho ← EliminarABB(raiz.derecho, valor)
9 SINO // Nodo encontrado
10 // Caso 1: Nodo a eliminar es una hoja
11 SI raiz.izquierdo ES nula Y raiz.derecho ES nula ENTONCES
12 RETORNAR nula
13 // Caso 2: Nodo a eliminar tiene un solo hijo
14 SINO SI raiz.izquierdo ES nula ENTONCES
15 RETORNAR raiz.derecho
16 SINO SI raiz.derecho ES nula ENTONCES
17 RETORNAR raiz.izquierdo
18 // Caso 3: Nodo a eliminar tiene dos hijos
19 SINO
20 predecesor ← BuscarMaximo(raiz.izquierdo) // busca el mayor del subárbol izquierdo
21 raiz.valor ← predecesor.valor
22 raiz.izquierdo ← EliminarABB(raiz.izquierdo, predecesor.valor) // elimina el predecesor
23 FIN SI
24 FIN SI
25 RETORNAR raiz
26FIN FUNCION
1FUNCION BuscarMaximo(raiz)
2 SI raiz.derecho ES nula ENTONCES
3 RETORNAR raiz
4 SINO
5 RETORNAR BuscarMaximo(raiz.derecho)
6 FIN SI
7FIN FUNCION
22.1.4. Orden de las operaciones#
En un árbol binario de búsqueda, las operaciones de inserción, búsqueda y eliminación tienen un tiempo de ejecución que depende de la altura del árbol. Por lo tanto es importante tratar de mantener el árbol equilibrado para que la altura no crezca demasiado.
Un árbol binario de búsqueda equilibrado tiene una altura aproximada de \(O(log (n))\), donde \(n\) es el número de nodos en el árbol. En este caso, las operaciones de inserción, búsqueda y eliminación tienen un tiempo de ejecución promedio de \(O(log (n))\).
Formalmente la altura \(h\) de un árbol binario de búsqueda se define como:
En la siguiente figura se observa un árbol binario de búsqueda completo (con todos los nodos en todos los niveles) y perfectamente balanceado, donde cada nodo tiene dos hijos y la altura del árbol es mínima. En este caso, el árbol tiene una altura de 3 y contiene 15 nodos.
Figura 22.5 Árbol binario de búsqueda equilibrado#
La altura \(h\) de un árbol binario completo y balanceado se puede calcular como:
Por otro lado, en el peor de los casos, un árbol binario de búsqueda puede degenerar en una lista enlazada, lo que resulta en una altura de \(O(n)\) y un tiempo de ejecución de \(O(n)\) para las operaciones. Esto ocurre cuando los nodos se insertan en orden ascendente o descendente, lo que provoca que el árbol se convierta en una estructura lineal. En la siguiente figura se observa un árbol binario que degeneró en una lista
Figura 22.6 Árbol binario de búsqueda degenerado#
La altura \(h\) de un árbol binario degenerado en una lista se puede calcular como:
22.2. Implementación de un árbol binario de búsqueda#
A continuación se presenta una implementación de un árbol binario de búsqueda en Go donde se utiliza un tipo genérico T que permite almacenar cualquier tipo de dato que implemente la interfaz constraints.Ordered, es decir cualquier tipo de dato que soporte orden total y se puedan comparar los elementos con <, >, ==, <=, >=.
En esta implementación las funcionalidades para manipular el árbol están en el árbol propiamiente dicho.
Como en el caso de las listas se puede delegar la implementación de las operaciones a los nodos del árbol, lo que permite que el árbol esté menos acoplado a la implementación de los nodos.
Nota
En la implementación se utiliza el paquete golang.org/x/exp/constraints que permite definir restricciones en los tipos genéricos. Este paquete es parte de la biblioteca de Go y se utiliza para trabajar con tipos genéricos y restricciones de tipo.
22.2.1. Nodo binario#
1package binarysearchtree
2
3import "golang.org/x/exp/constraints"
4
5// BinaryNode representa un nodo en un árbol binario.
6type BinaryNode[T constraints.Ordered] struct {
7 Value T
8 Left *BinaryNode[T]
9 Right *BinaryNode[T]
10}
22.2.2. Árbol binario de búsqueda#
1package binarysearchtree
2
3import "golang.org/x/exp/constraints"
4
5// BinarySearchTree representa un árbol de búsqueda binario.
6type BinarySearchTree[T constraints.Ordered] struct {
7 Root *BinaryNode[T]
8}
9
10// NewBinarySearchTree crea un nuevo árbol de búsqueda binario vacío.
11func NewBinarySearchTree[T constraints.Ordered]() *BinarySearchTree[T] {
12 return &BinarySearchTree[T]{}
13}
14
15// Insert inserta un valor en el árbol de búsqueda binario.
16func (bst *BinarySearchTree[T]) Insert(value T) {
17 bst.Root = bst.insertRecursive(bst.Root, value)
18}
19
20func (bst *BinarySearchTree[T]) insertRecursive(node *BinaryNode[T], value T) *BinaryNode[T] {
21 if node == nil {
22 return &BinaryNode[T]{Value: value}
23 }
24
25 if value < node.Value {
26 node.Left = bst.insertRecursive(node.Left, value)
27 } else if value > node.Value {
28 node.Right = bst.insertRecursive(node.Right, value)
29 }
30 return node
31}
32
33// Search busca un valor en el árbol de búsqueda binario.
34func (bst *BinarySearchTree[T]) Search(value T) bool {
35 return bst.searchRecursive(bst.Root, value)
36}
37
38func (bst *BinarySearchTree[T]) searchRecursive(node *BinaryNode[T], value T) bool {
39 if node == nil {
40 return false
41 }
42
43 if value == node.Value {
44 return true
45 } else if value < node.Value {
46 return bst.searchRecursive(node.Left, value)
47 } else {
48 return bst.searchRecursive(node.Right, value)
49 }
50}
51
52// Delete borra un valor del árbol de búsqueda binario.
53func (bst *BinarySearchTree[T]) Delete(value T) {
54 bst.Root = bst.deleteRecursive(bst.Root, value)
55}
56
57func (bst *BinarySearchTree[T]) deleteRecursive(node *BinaryNode[T], value T) *BinaryNode[T] {
58 if node == nil {
59 return nil
60 }
61
62 if value < node.Value {
63 node.Left = bst.deleteRecursive(node.Left, value)
64 } else if value > node.Value {
65 node.Right = bst.deleteRecursive(node.Right, value)
66 } else {
67 // Nodo encontrado
68 if node.Left == nil {
69 return node.Right
70 } else if node.Right == nil {
71 return node.Left
72 }
73
74 // Nodo con dos hijos: encontrar el sucesor inorder (el menor en el subárbol derecho)
75 minRight := bst.findMin(node.Right)
76 node.Value = minRight
77 node.Right = bst.deleteRecursive(node.Right, minRight)
78 }
79 return node
80}
81
82// findMin encuentra el nodo con el valor mínimo en un subárbol.
83func (bst *BinarySearchTree[T]) findMin(node *BinaryNode[T]) T {
84 current := node
85 for current.Left != nil {
86 current = current.Left
87 }
88 return current.Value
89}
90
91// Height calcula la altura del árbol de búsqueda binario.
92func (bst *BinarySearchTree[T]) Height() int {
93 return bst.heightRecursive(bst.Root)
94}
95
96func (bst *BinarySearchTree[T]) heightRecursive(node *BinaryNode[T]) int {
97 if node == nil {
98 return 0
99 }
100 leftHeight := bst.heightRecursive(node.Left)
101 rightHeight := bst.heightRecursive(node.Right)
102 if leftHeight > rightHeight {
103 return leftHeight + 1
104 }
105 return rightHeight + 1
106}
107
108// InorderTraversal realiza un recorrido inorder y devuelve un arreglo con los valores.
109func (bst *BinarySearchTree[T]) InorderTraversal() []T {
110 result := []T{}
111 bst.inorderRecursive(bst.Root, &result)
112 return result
113}
114
115func (bst *BinarySearchTree[T]) inorderRecursive(node *BinaryNode[T], result *[]T) {
116 if node != nil {
117 bst.inorderRecursive(node.Left, result)
118 *result = append(*result, node.Value)
119 bst.inorderRecursive(node.Right, result)
120 }
121}
122
123// PreorderTraversal realiza un recorrido preorder y devuelve un arreglo con los valores.
124func (bst *BinarySearchTree[T]) PreorderTraversal() []T {
125 result := []T{}
126 bst.preorderRecursive(bst.Root, &result)
127 return result
128}
129
130func (bst *BinarySearchTree[T]) preorderRecursive(node *BinaryNode[T], result *[]T) {
131 if node != nil {
132 *result = append(*result, node.Value)
133 bst.preorderRecursive(node.Left, result)
134 bst.preorderRecursive(node.Right, result)
135 }
136}
137
138// PostorderTraversal realiza un recorrido postorder y devuelve un arreglo con los valores.
139func (bst *BinarySearchTree[T]) PostorderTraversal() []T {
140 result := []T{}
141 bst.postorderRecursive(bst.Root, &result)
142 return result
143}
144
145func (bst *BinarySearchTree[T]) postorderRecursive(node *BinaryNode[T], result *[]T) {
146 if node != nil {
147 bst.postorderRecursive(node.Left, result)
148 bst.postorderRecursive(node.Right, result)
149 *result = append(*result, node.Value)
150 }
151}
22.2.3. Ejemplo de uso#
1package main
2
3import (
4
5 "bst/binarysearchtree"
6 "fmt"
7)
8
9func main() {
10 bstInt := binarysearchtree.NewBinarySearchTree[int]()
11 bstInt.Insert(5)
12 bstInt.Insert(3)
13 bstInt.Insert(7)
14 bstInt.Insert(2)
15 bstInt.Insert(4)
16 bstInt.Insert(6)
17 bstInt.Insert(8)
18
19 fmt.Println("Árbol de enteros:")
20 fmt.Println("Buscar 4:", bstInt.Search(4))
21 fmt.Println("Buscar 9:", bstInt.Search(9))
22 fmt.Println("Altura del árbol:", bstInt.Height())
23 fmt.Println("Recorrido Inorder:", bstInt.InorderTraversal())
24 fmt.Println("Recorrido Preorder:", bstInt.PreorderTraversal())
25 fmt.Println("Recorrido Postorder:", bstInt.PostorderTraversal())
26
27 bstInt.Delete(3)
28 fmt.Println("Árbol después de borrar 3:")
29 fmt.Println("Recorrido Inorder:", bstInt.InorderTraversal())
30
31 bstInt.Delete(7)
32 fmt.Println("Árbol después de borrar 7:")
33 fmt.Println("Recorrido Inorder:", bstInt.InorderTraversal())
34
35 bstInt.Insert(3)
36 bstInt.Insert(7)
37
38 bstString := binarysearchtree.NewBinarySearchTree[string]()
39 bstString.Insert("banana")
40 bstString.Insert("manzana")
41 bstString.Insert("naranja")
42
43 fmt.Println("\nÁrbol de strings:")
44 fmt.Println("Recorrido Inorder:", bstString.InorderTraversal())
45}
22.2.4. Iteradores#
Para poder implementar iteradores con los distintos recorridos de un árbol, las implementaciones recursivas no son la mejor opción ya que no permiten mantener el estado entre las llamadas. Por lo tanto se debe implementar un iterador que mantenga el estado del recorrido y permita avanzar a través de los nodos del árbol, lo que se logra utilizando una pila para almacenar los nodos que se deben visitar.
22.3. Ejercicios#
Implementar un método de árbol binario de búsqueda que devuelva la cantidad de nodos en el árbol.
Implementar un método de árbol binario de búsqueda que devuelva la cantidad de hojas en el árbol.
Implementar un iterador Inorden para un árbol binario de búsqueda.
Implementar un iterador Preorden para un árbol binario de búsqueda.
Implementar un iterador Postorden para un árbol binario de búsqueda.
Implementar un iterador por niveles para un árbol binario de búsqueda. Tal que primero devuelve la raíz, luego los hijos de la raíz que se encuentran en el nivel 1, luego los hijos de los nodos del nivel 1 que se encuentran en el nivel 2 y así sucesivamente.