Inicio

Temas

Listas Simplemente (LSE) y Doblemente enlazadas (LDE)

Estructuras de Datos en Grafos

Árboles Binarios: operaciones de inserción, eliminación y busqueda

Los árboles binarios son una estructura de datos utilizada en la programación para almacenar y acceder a una colección de elementos de manera organizada. Cada elemento del árbol se conoce como un nodo y puede tener hasta dos hijos, lo que lo convierte en una estructura jerárquica.

A continuación se presentan algunas de las principales operaciones que se pueden realizar con árboles binarios:

Inserción:

Para insertar un elemento en un árbol binario, debes seguir los siguientes pasos:

Crea un nuevo nodo con el elemento que deseas insertar.

Si el árbol está vacío, el nuevo nodo se convierte en la raíz del árbol.

Si el árbol no está vacío, comienza a recorrer el árbol desde la raíz hasta encontrar un lugar donde insertar el nuevo nodo.

Compara el valor del nuevo nodo con el valor de cada nodo que encuentras mientras recorres el árbol. Si el valor del nuevo nodo es menor que el valor del nodo actual, continúa recorriendo el árbol hacia la izquierda. Si el valor del nuevo nodo es mayor, continúa recorriendo el árbol hacia la derecha.

Cuando encuentres un nodo cuyo hijo izquierdo o derecho esté vacío, inserta el nuevo nodo en esa posición.

                    
                        class BinaryTree {
                            
                            private:
                                struct TreeNode {
                                    int data;
                                    TreeNode* left;
                                    TreeNode* right;
                                };
                                TreeNode* root;
                            
                                void insert(TreeNode*&, int);
                            
                            public:
                                BinaryTree() { root = NULL; }
                                void insert(int data) { insert(root, data); }
                            };
                            
                            void BinaryTree::insert(TreeNode*& node, int data) {
                                if (node == NULL) {
                                    node = new TreeNode;
                                    node->data = data;
                                    node->left = node->right = NULL;
                                }
                                else if (data < node->data) {
                                    insert(node->left, data);
                                }
                                else {
                                    insert(node->right, data);
                                }
                            }

Eliminación:

Para eliminar un elemento de un árbol binario, debes seguir los siguientes pasos:

Comienza a recorrer el árbol desde la raíz hasta encontrar el nodo que deseas eliminar.

Una vez que encuentres el nodo a eliminar, verifica cuántos hijos tiene. Si el nodo no tiene hijos, simplemente lo eliminas y enlazas el padre del nodo con null.

Si el nodo tiene un hijo, enlaza el padre del nodo con el hijo del nodo y elimina el nodo.

Si el nodo tiene dos hijos, reemplázalo con el nodo más a la derecha del subárbol izquierdo o con el nodo más a la izquierda del subárbol derecho, dependiendo de la implementación del árbol. Luego elimina el nodo original.

                    
                        class BinaryTree {
                            
                            private:
                                struct TreeNode {
                                    int data;
                                    TreeNode* left;
                                    TreeNode* right;
                                };
                                TreeNode* root;
                            
                                void remove(TreeNode*&, int);
                            
                            public:
                                BinaryTree() { root = NULL; }
                                void remove(int data) { remove(root, data); }
                            };
                            
                            void BinaryTree::remove(TreeNode*& node, int data) {
                                if (node == NULL) {
                                    return;
                                }
                                if (data < node->data) {
                                    remove(node->left, data);
                                }
                                else if (data > node->data) {
                                    remove(node->right, data);
                                }
                                else {
                                    if (node->left == NULL && node->right == NULL) {
                                        delete node;
                                        node = NULL;
                                    }
                                    else if (node->left == NULL) {
                                        TreeNode* temp = node;
                                        node = node->right;
                                        delete temp;
                                    }
                                    else if (node->right == NULL) {
                                        TreeNode* temp = node;
                                        node = node->left;
                                        delete temp;
                                    }
                                    else {
                                        TreeNode* temp = node->right;
                                        while (temp->left != NULL) {
                                            temp = temp->left;
                                        }
                                        node->data = temp->data;
                                        remove(node->right, temp->data);
                                    }
                                }
                            }

Buscar:

Para buscar un elemento en un árbol binario, debes seguir los siguientes pasos:

Comienza a recorrer el árbol desde la raíz.

Compara el valor del elemento que estás buscando con el valor del nodo actual. Si son iguales, has encontrado el elemento y puedes detener la búsqueda.

Si el valor del elemento que estás buscando es menor que el valor del nodo actual, continúa recorriendo el árbol hacia la izquierda. Si el valor del elemento que estás buscando es mayor, continúa recorriendo el árbol hacia la derecha.

Repite el proceso hasta encontrar el elemento o hasta llegar a un nodo que sea null, lo que significa que el elemento no se encuentra en el árbol.

                    
                        class BinaryTree {
                            
                            private:
                                struct TreeNode {
                                    int data;
                                    TreeNode* left;
                                    TreeNode* right;
                                };
                                TreeNode* root;
                            
                                bool search(TreeNode*, int);
                            
                            public:
                                BinaryTree() { root = NULL; }
                                bool search(int data) { return search(root, data); }
                            };
                            
                            bool BinaryTree::search(TreeNode* node, int data) {
                                if (node == NULL) {
                                    return false;
                                }
                                if (node->data == data) {
                                    return true;
                                }
                                if (data < node->data) {
                                    return search(node->left, data);
                                }
                                else {
                                    return search(node->right, data);
                                }
                            }