Dado un hora estándar del este , la tarea es insertar un nuevo nodo en este hora estándar del este .
Ejemplo:
Inserción en el árbol de búsqueda binaria
Cómo insertar un valor en un árbol de búsqueda binaria:
Siempre se inserta una nueva clave en la hoja manteniendo la propiedad del árbol de búsqueda binario. Comenzamos a buscar una clave desde la raíz hasta llegar a un nodo hoja. Una vez que se encuentra un nodo hoja, el nuevo nodo se agrega como hijo del nodo hoja. Se siguen los siguientes pasos mientras intentamos insertar un nodo en un árbol de búsqueda binario:
- Verifique el valor que se insertará (digamos X ) con el valor del nodo actual (digamos vale ) estamos en:
- Si X es menos que vale pasar al subárbol izquierdo.
- De lo contrario, vaya al subárbol derecho.
- Una vez que se alcanza el nodo de la hoja, inserte X a su derecha o izquierda según la relación entre X y el valor del nodo hoja.
Siga la siguiente ilustración para una mejor comprensión:
Ilustración:
Inserción en BST
Inserción en BST
Inserción en BST
Inserción en BST
Inserción en BST
Inserción en el árbol de búsqueda binaria mediante recursividad:
A continuación se muestra la implementación de la operación de inserción mediante recursividad.
C++14
c# fecha y hora
// C++ program to demonstrate insertion> // in a BST recursively> #include> 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>raíz->datos) {> >// Insert right node data, if the 'value'> >// to be inserted is greater than 'root' node data.> >// Process right nodes.> >root->derecha = Insertar(raíz->derecha, valor);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->izquierda = Insertar(raíz->izquierda, valor);> >}> >// 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->izquierda);> >cout ' '; Inorder(root->bien); } // Código del controlador int main() { BST b, *root = NULL; raíz = b.Insertar(raíz, 50); b.Insertar(raíz, 30); b.Insertar(raíz, 20); b.Insertar(raíz, 40); b.Insertar(raíz, 70); b.Insertar(raíz, 60); b.Insertar(raíz, 80); b.Inorder(raíz); devolver 0; }> |
>
>
C
// C program to demonstrate insert> // operation in binary> // search tree.> #include> #include> 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->clave = elemento;> >temp->izquierda = temp->derecha = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->izquierda);> >printf>(>'%d '>, root->clave);> >inorder(root->derecha);> >}> }> // 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 key)> >node->izquierda = insertar(nodo->izquierda, clave);> >else> if> (key>nodo->clave)> >node->derecha = insertar(nodo->derecha, clave);> >// 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 inorder traversal of the BST> >inorder(root);> >return> 0;> }> |
>
>
Java
// Java program to demonstrate> // insert operation in binary> // search tree> import> java.io.*;> public> 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> >else> if> (key root.left = insertRec(root.left, key); else if (key>raíz.clave) raíz.derecha = insertRec(raíz.derecha, clave); // Devuelve el puntero del nodo (sin cambios) return root; } // Este método llama principalmente a InorderRec() void inorder() { inorderRec(root); } // Una función de utilidad para // hacer un recorrido en orden de BST void inorderRec(Node root) { if (root!= null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(raíz.derecha); } } // Código del controlador public static void main(String[] args) { árbol BinarySearchTree = new BinarySearchTree(); /* Creemos el siguiente BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); árbol.insertar(30); árbol.insertar(20); árbol.insertar(40); árbol.insert(70); árbol.insert(60); árbol.insert(80); // Imprime el recorrido en orden del BST tree.inorder(); } } // Este código es una contribución de Ankur Narain Verma> |
marco tkinter
>
>
Python3
# 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 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, end=' ') inorder(root.right) # Driver program to test the above functions if __name__ == '__main__': # 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 inorder 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.left = insertRec(root.left, key); else if (key>raíz.clave) raíz.derecha = insertRec(raíz.derecha, clave); // Devuelve el puntero del nodo (sin cambios) return root; } // Este método llama principalmente a InorderRec() void inorder() { inorderRec(root); } // Una función de utilidad para // hacer un recorrido en orden de BST void inorderRec(Node root) { if (root!= null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(raíz.derecha); } } // Código del controlador public static void Main(String[] args) { árbol BinarySearchTree = new BinarySearchTree(); /* Creemos el siguiente BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); árbol.insertar(30); árbol.insertar(20); árbol.insertar(40); árbol.insert(70); árbol.insert(60); árbol.insert(80); // Imprime el recorrido en orden del BST tree.inorder(); } } // Este código es una contribución de aashish1995> |
>
>
JavaScript
> // 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.left = insertRec(root.left, key); else if (key>raíz.clave) raíz.derecha = insertRec(raíz.derecha, clave); // Devuelve el puntero del nodo (sin cambios) return root; } // Este método llama principalmente a la función InorderRec() inorder() { inorderRec(root); } // Una función de utilidad para // hacer un recorrido en orden de la función BST inorderRec(root) { if (root!= null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(raíz.derecha); } } // Código del controlador /* Creemos el siguiente BST 50 / 30 70 / / 20 40 60 80 */ insert(50); insertar(30); insertar(20); insertar(40); insertar(70); insertar(60); insertar(80); // Imprime el recorrido en orden del BST inorder(); // Este código es una contribución de Rajput-Ji> |
>
>Producción
20 30 40 50 60 70 80>
Complejidad del tiempo:
- La complejidad temporal en el peor de los casos de las operaciones de inserción es Oh) dónde 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 nodo de la hoja más profundo. La altura de un árbol torcido puede llegar a ser norte y la complejidad temporal de la operación de inserción puede volverse En).
Espacio Auxiliar: El auxiliar La complejidad espacial de la inserción en un árbol de búsqueda binario es O(1)
Inserción en el árbol de búsqueda binaria mediante un enfoque iterativo:
En lugar de utilizar la recursividad, también podemos implementar la operación de inserción de forma iterativa utilizando un mientras bucle . A continuación se muestra la implementación utilizando un bucle while.
emitir un comando
C++
// C++ Code to insert node and to print inorder traversal> // using iteration> #include> using> namespace> std;> // BST Node> class> Node {> public>:> >int> val;> >Node* left;> >Node* right;> >Node(>int> val)> >: val(val)> >, left(NULL)> >, right(NULL)> >{> >}> };> // Utility function to insert node in BST> void> insert(Node*& root,>int> key)> {> >Node* node =>new> Node(key);> >if> (!root) {> >root = node;> >return>;> >}> >Node* prev = NULL;> >Node* temp = root;> >while> (temp) {> >if> (temp->val> clave) {> >prev = temp;> >temp = temp->izquierda;> >}> >else> if> (temp->val anterior = temperatura; temperatura = temperatura->derecha; } } if (prev->val> clave) prev->izquierda = nodo; else anterior->derecha = nodo; } // Función de utilidad para imprimir el recorrido en orden void inorder(Nodo* raíz) { Nodo* temp = raíz; apilar st; while (temp!= NULL ||!st.empty()) { if (temp!= NULL) { st.push(temp); temp = temp->izquierda; } más { temp = st.top(); st.pop(); cout''; temperatura = temperatura->derecha; } } } // Código del controlador int main() { Nodo* raíz = NULL; insertar(raíz, 30); insertar(raíz, 50); insertar(raíz, 15); insertar(raíz, 20); insertar(raíz, 10); insertar(raíz, 40); insertar(raíz, 60); // Llamada a función para imprimir el recorrido en orden inorder(root); devolver 0; }> |
>
>
Java
// Java code to implement the insertion> // in binary search tree> import> java.io.*;> import> java.util.*;> class> GFG {> >// Driver code> >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;> >// Function to insert a key> >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>clave) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>clave) prev.left = nodo; else prev.right = nodo; } // Función para imprimir el valor del orden public void inorder() { Node temp = root; Pila pila = nueva pila(); while (temp!= null || !stack.isEmpty()) { if (temp!= null) { stack.add(temp); temp = temp.izquierda; } más { temp = pila.pop(); System.out.print(temp.val + ' '); temp = temp.derecha; } } } }> |
>
>
Python3
# Python 3 code to implement the insertion> # operation iteratively> 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> ># Function to insert a key in the BST> >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>clave):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>key): prev.left = node else: prev.right = node # Función para imprimir el recorrido en orden de BST def inorder(self): temp = self.root stack = [] while (temp != Ninguno o no (len( pila) == 0)): if (temp! = Ninguno): stack.append(temp) temp = temp.left else: temp = stack.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Este código es una contribución de rastogik346.> |
>
>
C#
centos vs sombrero rojo
// Function to implement the insertion> // operation iteratively> using> System;> using> System.Collections.Generic;> public> class> GFG {> >// Driver code> >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);> >// Function call to print the inorder traversal> >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;> >// Function to insert a new key in the BST> >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>clave) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>clave) prev.left = nodo; else prev.right = nodo; } // Función para imprimir el recorrido en orden de BST public void inorder() { Node temp = root; Pila pila = nueva pila(); while (temp!= null || stack.Count!= 0) { if (temp!= null) { stack.Push(temp); temp = temp.izquierda; } más { temp = pila.Pop(); Console.Write(temp.val + ' '); temp = temp.derecha; } } } } // Este código es una contribución de Rajput-Ji> |
>
>
JavaScript
// JavaScript code to implement the insertion> // in binary search tree> class Node {> >constructor(val) {> >this>.left =>null>;> >this>.val = val;> >this>.right =>null>;> >}> }> class BST {> >constructor() {> >this>.root =>null>;> >}> >// Function to insert a key> >insert(key) {> >let node =>new> Node(key);> >if> (>this>.root ==>null>) {> >this>.root = node;> >return>;> >}> >let prev =>null>;> >let temp =>this>.root;> >while> (temp !=>null>) {> >if> (temp.val>clave) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>clave) prev.left = nodo; else prev.right = nodo; } // Función para imprimir el valor de orden inorder() { let temp = this.root; dejar pila = []; while (temp!= nulo || pila.longitud> 0) { if (temp!= nulo) { pila.push(temp); temp = temp.izquierda; } más { temp = pila.pop(); console.log(temp.val + ' '); temp = temp.derecha; } } } } let árbol = nuevo BST(); árbol.insertar(30); árbol.insertar(50); árbol.insertar(15); árbol.insertar(20); árbol.insert(10); árbol.insertar(40); árbol.insert(60); árbol.inorder(); // este código es aportado por devendrasolunke> |
>
>Producción
10 15 20 30 40 50 60>
El complejidad del tiempo de recorrido en orden es En) , ya que cada nodo se visita una vez.
El Espacio auxiliar es En) , ya que usamos una pila para almacenar nodos para recursividad.
Enlaces relacionados:
- Operación de búsqueda en árbol de búsqueda binaria
- Operación de eliminación del árbol de búsqueda binaria