Un árbol de búsqueda binaria (BST) es árbol en el que todos los nodos siguen las propiedades mencionadas a continuación-
-
el valor de la clave del sub −árbol izquierdo es menor que el valor de la clave de su nodo padre (raíz).
-
el valor de la clave del sub-árbol derecho es mayor o igual al valor de la clave de su nodo padre (raíz).,
por lo tanto, BST divide todos sus sub-árboles en dos segmentos; el sub-árbol izquierdo y el sub-árbol derecho y se puede definir como −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
representación
BST es una colección de nodos dispuestos de manera que mantienen las propiedades BST. Cada nodo tiene una clave y un valor asociado. Durante la búsqueda, la clave deseada se compara con las claves en BST y, si se encuentra, se recupera el valor asociado.,
a continuación se muestra una representación pictórica DE BST −
observamos que la clave del nodo raíz (27) tiene todas las claves de menor valor en el sub-árbol izquierdo y las claves de mayor valor en el sub-árbol derecho.
Operaciones Básicas
las Siguientes son las operaciones básicas de un árbol −
-
Buscar − Búsqueda de un elemento en un árbol.
-
Insertar: Inserta un elemento en un árbol.
-
pre-order Traversal-atraviesa un árbol de una manera de pre-orden.
-
recorrido en orden-atraviesa un árbol en orden.,
-
Post-order Traversal-atraviesa un árbol de una manera posterior al pedido.
Node
defina un nodo que tenga algunos datos, referencias a sus nodos secundarios izquierdo y derecho.
struct node { int data; struct node *leftChild; struct node *rightChild;};
operación de búsqueda
siempre que se busque un elemento, comience a buscar desde el nodo raíz. Luego, si los datos son menores que el valor de la clave, busque el elemento en el subárbol izquierdo. De lo contrario, busque el elemento en el subárbol correcto. Siga el mismo algoritmo para cada nodo.,
algoritmo
insertar operación
siempre que un elemento se va a insertar, primero busque su ubicación adecuada. Comience a buscar desde el nodo raíz, luego si los datos son menores que el valor de la clave, busque la ubicación vacía en el subárbol izquierdo e inserte los datos. De lo contrario, busque la ubicación vacía en el subárbol derecho e inserte los datos.