algorithm
Árboles binarios de búsqueda
Buscar..
Introducción
El árbol binario es un árbol en el que cada nodo tiene un máximo de dos hijos. El árbol de búsqueda binaria (BST) es un árbol binario en el que sus elementos se colocan en un orden especial. En cada BST, todos los valores (es decir, la clave) en el subárbol izquierdo son menores que los valores en el subárbol derecho.
Árbol de búsqueda binario - Inserción (Python)
Esta es una implementación simple de la inserción de árbol de búsqueda binaria utilizando Python.
A continuación se muestra un ejemplo:
Siguiendo el fragmento de código, cada imagen muestra la visualización de ejecución, lo que facilita la visualización de cómo funciona este código.
class Node:
def __init__(self, val):
self.l_child = None
self.r_child = None
self.data = val
def insert(root, node):
if root is None:
root = node
else:
if root.data > node.data:
if root.l_child is None:
root.l_child = node
else:
insert(root.l_child, node)
else:
if root.r_child is None:
root.r_child = node
else:
insert(root.r_child, node)
def in_order_print(root):
if not root:
return
in_order_print(root.l_child)
print root.data
in_order_print(root.r_child)
def pre_order_print(root):
if not root:
return
print root.data
pre_order_print(root.l_child)
pre_order_print(root.r_child)
Árbol de búsqueda binario - Eliminación (C ++)
Antes de comenzar con la eliminación, solo quiero poner algunas luces en lo que es un árbol de búsqueda binaria (BST). Cada nodo en una BST puede tener un máximo de dos nodos (hijo izquierdo y derecho). El subárbol izquierdo de un nodo tiene una clave menor o igual que la clave de su nodo principal. El subárbol derecho de un nodo tiene una clave mayor que la clave de su nodo principal.
Eliminar un nodo en un árbol mientras se mantiene su propiedad de árbol de búsqueda binaria.
Hay tres casos que deben considerarse al eliminar un nodo.
- Caso 1: el nodo que se eliminará es el nodo de hoja (nodo con valor 22).
- Caso 2: el nodo que se va a eliminar tiene un hijo (nodo con valor 26).
- Caso 3: El nodo a eliminar tiene ambos hijos (Nodo con valor 49).
Explicación de los casos:
- Cuando el nodo que se va a eliminar es un nodo de hoja, simplemente elimine el nodo y pase
nullptra su nodo principal. - Cuando un nodo que se va a eliminar tiene solo un hijo, copie el valor hijo en el valor del nodo y elimine el hijo (convertido al caso 1)
- Cuando un nodo que se va a eliminar tiene dos hijos, el mínimo de su subárbol derecho se puede copiar al nodo y el valor mínimo se puede eliminar del subárbol derecho del nodo (Convertido al Caso 2)
Nota: El mínimo en el subárbol derecho puede tener un máximo de un hijo y ese hijo también correcto si tiene el hijo izquierdo significa que no es el valor mínimo o que no está siguiendo la propiedad BST.
La estructura de un nodo en un árbol y el código para la eliminación:
struct node
{
int data;
node *left, *right;
};
node* delete_node(node *root, int data)
{
if(root == nullptr) return root;
else if(data < root->data) root->left = delete_node(root->left, data);
else if(data > root->data) root->right = delete_node(root->right, data);
else
{
if(root->left == nullptr && root->right == nullptr) // Case 1
{
free(root);
root = nullptr;
}
else if(root->left == nullptr) // Case 2
{
node* temp = root;
root= root->right;
free(temp);
}
else if(root->right == nullptr) // Case 2
{
node* temp = root;
root = root->left;
free(temp);
}
else // Case 3
{
node* temp = root->right;
while(temp->left != nullptr) temp = temp->left;
root->data = temp->data;
root->right = delete_node(root->right, temp->data);
}
}
return root;
}
La complejidad de tiempo del código anterior es O ( h ), donde h es la altura del árbol.
El antepasado común más bajo en un BST
Considere el BST:
El antepasado común más bajo de 22 y 26 es 24.
El antepasado común más bajo de 26 y 49 es 46.
El antepasado común más bajo de 22 y 24 es 24.
La propiedad del árbol de búsqueda binario se puede usar para encontrar los nodos del antepasado más bajo
Código Psuedo:
lowestCommonAncestor(root,node1, node2){
if(root == NULL)
return NULL;
else if(node1->data == root->data || node2->data== root->data)
return root;
else if((node1->data <= root->data && node2->data > root->data)
|| (node2->data <= root->data && node1->data > root->data)){
return root;
}
else if(root->data > max(node1->data,node2->data)){
return lowestCommonAncestor(root->left, node1, node2);
}
else {
return lowestCommonAncestor(root->right, node1, node2);
}
}
Árbol binario de búsqueda - Python
class Node(object):
def __init__(self, val):
self.l_child = None
self.r_child = None
self.val = val
class BinarySearchTree(object):
def insert(self, root, node):
if root is None:
return node
if root.val < node.val:
root.r_child = self.insert(root.r_child, node)
else:
root.l_child = self.insert(root.l_child, node)
return root
def in_order_place(self, root):
if not root:
return None
else:
self.in_order_place(root.l_child)
print root.val
self.in_order_place(root.r_child)
def pre_order_place(self, root):
if not root:
return None
else:
print root.val
self.pre_order_place(root.l_child)
self.pre_order_place(root.r_child)
def post_order_place(self, root):
if not root:
return None
else:
self.post_order_place(root.l_child)
self.post_order_place(root.r_child)
print root.val
"" "Crear un nodo diferente e insertar datos en él" ""
r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]
for nd in nodeList:
node.insert(r, Node(nd))
print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))