La siguiente es la definición de árbol de búsqueda binaria (BST) según Wikipedia
Binary Search Tree es una estructura de datos de árbol binario basada en Nodes que tiene las siguientes propiedades:
- El subárbol izquierdo de un Node contiene solo Nodes con claves menores que la clave del Node.
- El subárbol derecho de un Node contiene solo Nodes con claves mayores que la clave del Node.
- El subárbol izquierdo y derecho también debe ser un árbol de búsqueda binaria.
No debe haber Nodes duplicados.
Las propiedades anteriores del árbol de búsqueda binaria proporcionan un orden entre las claves para que las operaciones como búsqueda, mínimo y máximo se puedan realizar rápidamente. Si no hay orden, es posible que tengamos que comparar cada clave para buscar una clave determinada.
Buscando una clave :
Para buscar un valor, si tuviéramos una array ordenada, podríamos haber realizado una búsqueda binaria. Digamos que queremos buscar un número en la array, en la búsqueda binaria, primero definimos la lista completa como nuestro espacio de búsqueda, el número solo puede existir dentro del espacio de búsqueda. Ahora comparamos el número a buscar o el elemento a buscar con el elemento del medio (mediana) del espacio de búsqueda y si el registro que se busca es menor que el elemento del medio, vamos a buscar en la mitad izquierda, sino vamos a buscar en la mitad derecha, en caso de igualdad hemos encontrado el elemento. En la búsqueda binaria comenzamos con ‘n’ elementos en el espacio de búsqueda y si el elemento medio no es el elemento que estamos buscando, reducimos el espacio de búsqueda a ‘n/2’seguimos reduciendo el espacio de búsqueda hasta que encontremos el registro que estamos buscando o lleguemos a un solo elemento en el espacio de búsqueda y terminemos con toda esta reducción.
Las operaciones de búsqueda en el árbol de búsqueda binaria serán muy similares. Digamos que queremos buscar el número, comenzamos en la raíz, y luego comparamos el valor a buscar con el valor de la raíz, si es igual, terminamos con la búsqueda, si es más pequeño, sabemos que necesitamos vaya al subárbol izquierdo porque en un árbol de búsqueda binaria todos los elementos del subárbol izquierdo son más pequeños y todos los elementos del subárbol derecho son más grandes. Buscar un elemento en el árbol de búsqueda binaria es básicamente este recorrido, en cada paso vamos hacia la izquierda o hacia la derecha y en cada paso descartamos uno de los subárboles. Si el árbol está balanceado (llamamos a un árbol balanceado si para todos los Nodes la diferencia entre las alturas de los subárboles izquierdo y derecho no es mayor que uno) comenzamos con un espacio de búsqueda de ‘n’Nodes y, a medida que descartamos uno de los subárboles, descartamos ‘n/2’ Nodes, por lo que nuestro espacio de búsqueda se reduce a ‘n/2’. En el siguiente paso reducimos el espacio de búsqueda a ‘n/4’ y repetimos hasta que encontremos el elemento o nuestro espacio de búsqueda se reduzca a un solo Node. La búsqueda aquí también es una búsqueda binaria, de ahí el nombre; Árbol de búsqueda binaria.
Implementación:
C++
// C function to search a given key in a given BST
struct node* search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}
Java
// A utility function to search a given key in BST
public Node search(Node root, int key)
{
// Base Cases: root is null or key is present at root
if (root==null || root.key==key)
return root;
// Key is greater than root's key
if (root.key < key)
return search(root.right, key);
// Key is smaller than root's key
return search(root.left, key);
}
Python
# A utility function to search a given key in BST def search(root,key): # Base Cases: root is null or key is present at root if root is None or root.val == key: return root # Key is greater than root's key if root.val < key: return search(root.right,key) # Key is smaller than root's key return search(root.left,key) # This code is contributed by Bhavya Jain
C#
// A utility function to search
// a given key in BST
public Node search(Node root,
int key)
{
// Base Cases: root is null
// or key is present at root
if (root == null ||
root.key == key)
return root;
// Key is greater than root's key
if (root.key < key)
return search(root.right, key);
// Key is smaller than root's key
return search(root.left, key);
}
// This code is contributed by gauravrajput1
Javascript
<script>
// A utility function to search
// a given key in BST
function search(root, key)
{
// Base Cases: root is null
// or key is present at root
if (root == null ||
root.key == key)
return root;
// Key is greater than root's key
if (root.key < key)
return search(root.right, key);
// Key is smaller than root's key
return search(root.left, key);
}
// This code is contributed by rrrtnx.
</script>
Ilustración para buscar 6 en el siguiente árbol:
- Empezar desde la raíz.
- Compare el elemento de búsqueda con la raíz, si es menor que la raíz, luego llame recursivamente al subárbol izquierdo, de lo contrario, llame recursivamente al subárbol derecho.
- Si el elemento a buscar se encuentra en cualquier lugar, devuelve verdadero, de lo contrario, devuelve falso.
Inserción de una llave :
Siempre se inserta una llave nueva en la hoja. Comenzamos a buscar una clave desde la raíz hasta que llegamos a un Node hoja. Una vez que se encuentra un Node hoja, el nuevo Node se agrega como elemento secundario del Node hoja.
100 100
/ \ Insert 40 / \
20 500 ---------> 20 500
/ \ / \
10 30 10 30
\
40
Implementación:
C++
// C++ program to demonstrate insertion
// in a BST recursively.
#include <iostream>
using namespace std;
class BST {
int data;
BST *left, *right;
public:
// Default constructor.
BST();
// Parameterized constructor.
BST(int);
// Insert function.
BST* Insert(BST*, int);
// Inorder traversal.
void Inorder(BST*);
};
// Default Constructor definition.
BST ::BST()
: data(0)
, left(NULL)
, right(NULL)
{
}
// Parameterized Constructor definition.
BST ::BST(int value)
{
data = value;
left = right = NULL;
}
// Insert function definition.
BST* BST ::Insert(BST* root, int value)
{
if (!root) {
// Insert the first node, if root is NULL.
return new BST(value);
}
// Insert data.
if (value > root->data) {
// Insert right node data, if the 'value'
// to be inserted is greater than 'root' node data.
// Process right nodes.
root->right = Insert(root->right, value);
}
else {
// Insert left node data, if the 'value'
// to be inserted is smaller than 'root' node data.
// Process left nodes.
root->left = Insert(root->left, value);
}
// Return 'root' node, after insertion.
return root;
}
// Inorder traversal function.
// This gives data in sorted order.
void BST ::Inorder(BST* root)
{
if (!root) {
return;
}
Inorder(root->left);
cout << root->data << endl;
Inorder(root->right);
}
// Driver code
int main()
{
BST b, *root = NULL;
root = b.Insert(root, 50);
b.Insert(root, 30);
b.Insert(root, 20);
b.Insert(root, 40);
b.Insert(root, 70);
b.Insert(root, 60);
b.Insert(root, 80);
b.Inorder(root);
return 0;
}
// This code is contributed by pkthapa
C
// C program to demonstrate insert
// operation in binary
// search tree.
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(struct node* root)
{
if (root != NULL) {
inorder(root->left);
printf("%d \n", root->key);
inorder(root->right);
}
}
/* A utility function to insert
a new node with given key in
* BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Code
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// print inoder traversal of the BST
inorder(root);
return 0;
}
Java
// Java program to demonstrate
// insert operation in binary
// search tree
class BinarySearchTree {
/* Class containing left
and right child of current node
* and key value*/
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() { root = null; }
BinarySearchTree(int value) { root = new Node(value); }
// This method mainly calls insertRec()
void insert(int key) { root = insertRec(root, key); }
/* A recursive function to
insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty,
return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() { inorderRec(root); }
// A utility function to
// do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
// Driver Code
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// print inorder traversal of the BST
tree.inorder();
}
}
// This code is contributed by Ankur Narain Verma
Python
# Python program to demonstrate # insert operation in binary search tree # A utility class that represents # an individual node in a BST class Node: def __init__(self, key): self.left = None self.right = None self.val = key # A utility function to insert # a new node with the given key def insert(root, key): if root is None: return Node(key) else: if root.val == key: return root elif root.val < key: root.right = insert(root.right, key) else: root.left = insert(root.left, key) return root # A utility function to do inorder tree traversal def inorder(root): if root: inorder(root.left) print(root.val) inorder(root.right) # Driver program to test the above functions # Let us create the following BST # 50 # / \ # 30 70 # / \ / \ # 20 40 60 80 r = Node(50) r = insert(r, 30) r = insert(r, 20) r = insert(r, 40) r = insert(r, 70) r = insert(r, 60) r = insert(r, 80) # Print inoder traversal of the BST inorder(r)
C#
// C# program to demonstrate
// insert operation in binary
// search tree
using System;
class BinarySearchTree {
// Class containing left and
// right child of current node
// and key value
public class Node {
public int key;
public Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() { root = null; }
BinarySearchTree(int value) { root = new Node(value); }
// This method mainly calls insertRec()
void insert(int key) { root = insertRec(root, key); }
// A recursive function to insert
// a new key in BST
Node insertRec(Node root, int key)
{
// If the tree is empty,
// return a new node
if (root == null) {
root = new Node(key);
return root;
}
// Otherwise, recur down the tree
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
// Return the (unchanged) node pointer
return root;
}
// This method mainly calls InorderRec()
void inorder() { inorderRec(root); }
// A utility function to
// do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null) {
inorderRec(root.left);
Console.WriteLine(root.key);
inorderRec(root.right);
}
}
// Driver Code
public static void Main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// Print inorder traversal of the BST
tree.inorder();
}
}
// This code is contributed by aashish1995
Javascript
<script>
// javascript program to demonstrate
// insert operation in binary
// search tree
/*
* Class containing left and right child of current node and key value
*/
class Node {
constructor(item) {
this.key = item;
this.left = this.right = null;
}
}
// Root of BST
var root = null;
// This method mainly calls insertRec()
function insert(key) {
root = insertRec(root, key);
}
/*
* A recursive function to insert a new key in BST
*/
function insertRec(root , key) {
/*
* If the tree is empty, return a new node
*/
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
function inorder() {
inorderRec(root);
}
// A utility function to
// do inorder traversal of BST
function inorderRec(root)
{
if (root != null) {
inorderRec(root.left);
document.write(root.key+"<br/>");
inorderRec(root.right);
}
}
// Driver Code
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
insert(50);
insert(30);
insert(20);
insert(40);
insert(70);
insert(60);
insert(80);
// print inorder traversal of the BST
inorder();
// This code is contributed by Rajput-Ji
</script>
20 30 40 50 60 70 80
Ilustración para insertar 2 en el siguiente árbol:
- Empezar desde la raíz.
- Compare el elemento de inserción con la raíz, si es menor que la raíz, luego llame recursivamente al subárbol izquierdo, de lo contrario, llame recursivamente al subárbol derecho.
- Después de llegar al final, simplemente inserte ese Node a la izquierda (si es menor que el actual) a la derecha.
Complejidad de tiempo: la complejidad de tiempo en el peor de los casos de las operaciones de búsqueda e inserción es O(h), donde h es la altura del árbol de búsqueda binaria. En el peor de los casos, es posible que tengamos que viajar desde la raíz hasta el Node hoja más profundo. La altura de un árbol sesgado puede convertirse en n y la complejidad temporal de la operación de búsqueda e inserción puede convertirse en O(n).
Implementación: Inserción mediante bucle.
Java
import java.util.*;
import java.io.*;
class GFG {
public static void main (String[] args) {
BST tree=new BST();
tree.insert(30);
tree.insert(50);
tree.insert(15);
tree.insert(20);
tree.insert(10);
tree.insert(40);
tree.insert(60);
tree.inorder();
}
}
class Node{
Node left;
int val;
Node right;
Node(int val){
this.val=val;
}
}
class BST{
Node root;
public void insert(int key){
Node node=new Node(key);
if(root==null) {
root = node;
return;
}
Node prev=null;
Node temp=root;
while (temp!=null){
if(temp.val>key){
prev=temp;
temp=temp.left;
}
else if (temp.val<key){
prev=temp;
temp=temp.right;
}
}
if(prev.val>key)
prev.left=node;
else prev.right=node;
}
public void inorder(){
Node temp=root;
Stack<Node> stack=new Stack<>();
while (temp!=null||!stack.isEmpty()){
if(temp!=null){
stack.add(temp);
temp=temp.left;
}
else {
temp=stack.pop();
System.out.print(temp.val+" ");
temp=temp.right;
}
}
}
}
Python3
class GFG : @staticmethod def main( args) : tree = BST() tree.insert(30) tree.insert(50) tree.insert(15) tree.insert(20) tree.insert(10) tree.insert(40) tree.insert(60) tree.inorder() class Node : left = None val = 0 right = None def __init__(self, val) : self.val = val class BST : root = None def insert(self, key) : node = Node(key) if (self.root == None) : self.root = node return prev = None temp = self.root while (temp != None) : if (temp.val > key) : prev = temp temp = temp.left elif(temp.val < key) : prev = temp temp = temp.right if (prev.val > key) : prev.left = node else : prev.right = node def inorder(self) : temp = self.root stack = [] while (temp != None or not (len(stack) == 0)) : if (temp != None) : stack.append(temp) temp = temp.left else : temp = stack.pop() print(str(temp.val) + " ", end ="") temp = temp.right if __name__=="__main__": GFG.main([]) # This code is contributed by rastogik346.
C#
using System;
using System.Collections.Generic;
public class GFG {
public static void Main(String[] args) {
BST tree = new BST();
tree.insert(30);
tree.insert(50);
tree.insert(15);
tree.insert(20);
tree.insert(10);
tree.insert(40);
tree.insert(60);
tree.inorder();
}
}
public class Node {
public Node left;
public int val;
public Node right;
public Node(int val) {
this.val = val;
}
}
public class BST {
public Node root;
public void insert(int key) {
Node node = new Node(key);
if (root == null) {
root = node;
return;
}
Node prev = null;
Node temp = root;
while (temp != null) {
if (temp.val > key) {
prev = temp;
temp = temp.left;
} else if (temp.val < key) {
prev = temp;
temp = temp.right;
}
}
if (prev.val > key)
prev.left = node;
else
prev.right = node;
}
public void inorder() {
Node temp = root;
Stack<Node> stack = new Stack<Node>();
while (temp != null || stack.Count!=0) {
if (temp != null) {
stack.Push(temp);
temp = temp.left;
} else {
temp = stack.Pop();
Console.Write(temp.val + " ");
temp = temp.right;
}
}
}
}
// This code is contributed by Rajput-Ji
10 15 20 30 40 50 60
Algunos datos interesantes:
- El recorrido en orden de BST siempre produce una salida ordenada.
- Podemos construir un BST con solo un recorrido de Preorden o Postorden o Orden de nivel. Tenga en cuenta que siempre podemos obtener un recorrido en orden ordenando el único recorrido dado.
- El número de BST únicos con n claves distintas es el número catalán
Enlaces relacionados:
- Operación de eliminación de árbol de búsqueda binaria
- Cuestionario sobre el árbol de búsqueda binaria
- Práctica de codificación en BST
- Todos los artículos sobre BST
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA