Árbol binario enhebrado | Inserción

Ya hemos discutido el árbol binario de subprocesos binarios .
La inserción en el árbol de subprocesos binarios es similar a la inserción en el árbol binario, pero tendremos que ajustar los subprocesos después de la inserción de cada elemento.

Representación C del Node binario subproceso: 

struct Node
{
  struct Node *left, *right;
  int info;

  // false if left pointer points to predecessor 
  // in Inorder Traversal
  boolean lthread; 

  // false if right pointer points to successor 
  // in Inorder Traversal
  boolean rthread; 
};

En la siguiente explicación, hemos considerado el árbol de búsqueda binario (BST) para la inserción, ya que la inserción está definida por algunas reglas en los BST.
Sea tmp el Node recién insertado . Puede haber tres casos durante la inserción:

Caso 1: Inserción en árbol vacío 

Los punteros izquierdo y derecho de tmp se establecerán en NULL y el nuevo Node se convertirá en la raíz. 

root = tmp;
tmp -> left = NULL;
tmp -> right = NULL;

Caso 2: cuando se inserta un nuevo Node como hijo izquierdo 

Después de insertar el Node en su lugar adecuado, tenemos que hacer que sus hilos izquierdo y derecho apunten en orden antecesor y sucesor respectivamente. El Node que fue sucesor en orden . Entonces, los hilos izquierdo y derecho del nuevo Node serán: 

tmp -> left = par ->left;
tmp -> right = par;

Antes de la inserción, el puntero izquierdo del padre era un hilo, pero después de la inserción será un enlace que apunta al nuevo Node. 

par -> lthread = false;
par -> left = temp;

El siguiente ejemplo muestra un Node que se inserta como hijo izquierdo de su padre. 
 

Después de la inserción de 13, 
 

El predecesor de 14 se convierte en el predecesor de 13, por lo que el hilo izquierdo de 13 apunta a 10. El 
sucesor de 13 es 14, por lo que el hilo derecho de 13 apunta al hijo izquierdo, que es 13. 
El puntero izquierdo de 14 ahora no es un hilo, apunta a hijo izquierdo que tiene 13 años.

Caso 3: cuando se inserta un nuevo Node como hijo derecho 

El padre de tmp es su predecesor inorder. El Node que era el sucesor en orden del padre ahora es el sucesor en orden de este Node tmp. Entonces, los hilos izquierdo y derecho del nuevo Node serán: 

tmp -> left = par;
tmp -> right = par -> right;

Antes de la inserción, el puntero derecho del padre era un hilo, pero después de la inserción será un enlace que apunta al nuevo Node. 

par -> rthread = false;
par -> right = tmp;

El siguiente ejemplo muestra un Node que se inserta como hijo derecho de su padre. 
 

Después de 15 insertados, 
 

El sucesor de 14 se convierte en el sucesor de 15, por lo que el hilo derecho de 15 apunta a 16 
El predecesor de 15 es 14, por lo que el hilo izquierdo de 15 apunta a 14. 
El puntero derecho de 14 ahora no es un hilo, apunta al hijo derecho que es 15 .

Implementación de C++ para insertar un nuevo Node en el árbol de búsqueda binaria con subprocesos: al 
igual que la inserción BST estándar , buscamos el valor clave en el árbol. Si la clave ya está presente, regresamos; de lo contrario, la nueva clave se inserta en el punto donde termina la búsqueda. En BST, la búsqueda termina cuando encontramos la clave o cuando alcanzamos un puntero NULL izquierdo o derecho. Aquí, todos los punteros NULL izquierdos y derechos se reemplazan por subprocesos, excepto el puntero izquierdo del primer Node y el puntero derecho del último Node. Entonces, aquí la búsqueda no tendrá éxito cuando alcancemos un puntero NULL o un hilo.

Implementación:

// Insertion in Threaded Binary Search Tree.
#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    struct Node *left, *right;
    int info;
 
    // False if left pointer points to predecessor
    // in Inorder Traversal
    bool lthread;
 
    // False if right pointer points to successor
    // in Inorder Traversal
    bool rthread;
};
 
// Insert a Node in Binary Threaded Tree
struct Node *insert(struct Node *root, int ikey)
{
    // Searching for a Node with given value
    Node *ptr = root;
    Node *par = NULL; // Parent of key to be inserted
    while (ptr != NULL)
    {
        // If key already exists, return
        if (ikey == (ptr->info))
        {
            printf("Duplicate Key !\n");
            return root;
        }
 
        par = ptr; // Update parent pointer
 
        // Moving on left subtree.
        if (ikey < ptr->info)
        {
            if (ptr -> lthread == false)
                ptr = ptr -> left;
            else
                break;
        }
 
        // Moving on right subtree.
        else
        {
            if (ptr->rthread == false)
                ptr = ptr -> right;
            else
                break;
        }
    }
 
    // Create a new node
    Node *tmp = new Node;
    tmp -> info = ikey;
    tmp -> lthread = true;
    tmp -> rthread = true;
 
    if (par == NULL)
    {
        root = tmp;
        tmp -> left = NULL;
        tmp -> right = NULL;
    }
    else if (ikey < (par -> info))
    {
        tmp -> left = par -> left;
        tmp -> right = par;
        par -> lthread = false;
        par -> left = tmp;
    }
    else
    {
        tmp -> left = par;
        tmp -> right = par -> right;
        par -> rthread = false;
        par -> right = tmp;
    }
 
    return root;
}
 
// Returns inorder successor using rthread
struct Node *inorderSuccessor(struct Node *ptr)
{
    // If rthread is set, we can quickly find
    if (ptr -> rthread == true)
        return ptr->right;
 
    // Else return leftmost child of right subtree
    ptr = ptr -> right;
    while (ptr -> lthread == false)
        ptr = ptr -> left;
    return ptr;
}
 
// Printing the threaded tree
void inorder(struct Node *root)
{
    if (root == NULL)
        printf("Tree is empty");
 
    // Reach leftmost node
    struct Node *ptr = root;
    while (ptr -> lthread == false)
        ptr = ptr -> left;
 
    // One by one print successors
    while (ptr != NULL)
    {
        printf("%d ",ptr -> info);
        ptr = inorderSuccessor(ptr);
    }
}
 
// Driver Program
int main()
{
    struct Node *root = NULL;
 
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 5);
    root = insert(root, 16);
    root = insert(root, 14);
    root = insert(root, 17);
    root = insert(root, 13);
 
    inorder(root);
 
    return 0;
}

// Java program Insertion in Threaded Binary Search Tree.
import java.util.*;
class solution
{
static class Node
{
     Node left, right;
    int info;
   
    // False if left pointer points to predecessor
    // in Inorder Traversal
    boolean lthread;
   
    // False if right pointer points to successor
    // in Inorder Traversal
    boolean rthread;
};
   
// Insert a Node in Binary Threaded Tree
static Node insert( Node root, int ikey)
{
    // Searching for a Node with given value
    Node ptr = root;
    Node par = null; // Parent of key to be inserted
    while (ptr != null)
    {
        // If key already exists, return
        if (ikey == (ptr.info))
        {
            System.out.printf("Duplicate Key !\n");
            return root;
        }
   
        par = ptr; // Update parent pointer
   
        // Moving on left subtree.
        if (ikey < ptr.info)
        {
            if (ptr . lthread == false)
                ptr = ptr . left;
            else
                break;
        }
   
        // Moving on right subtree.
        else
        {
            if (ptr.rthread == false)
                ptr = ptr . right;
            else
                break;
        }
    }
   
    // Create a new node
    Node tmp = new Node();
    tmp . info = ikey;
    tmp . lthread = true;
    tmp . rthread = true;
     
    if (par == null)
    {
        root = tmp;
        tmp . left = null;
        tmp . right = null;
    }
    else if (ikey < (par . info))
    {
        tmp . left = par . left;
        tmp . right = par;
        par . lthread = false;
        par . left = tmp;
    }
    else
    {
        tmp . left = par;
        tmp . right = par . right;
        par . rthread = false;
        par . right = tmp;
    }
   
    return root;
}
   
// Returns inorder successor using rthread
static  Node inorderSuccessor( Node ptr)
{
    // If rthread is set, we can quickly find
    if (ptr . rthread == true)
        return ptr.right;
   
    // Else return leftmost child of right subtree
    ptr = ptr . right;
    while (ptr . lthread == false)
        ptr = ptr . left;
    return ptr;
}
   
// Printing the threaded tree
static void inorder( Node root)
{
    if (root == null)
        System.out.printf("Tree is empty");
   
    // Reach leftmost node
     Node ptr = root;
    while (ptr . lthread == false)
        ptr = ptr . left;
   
    // One by one print successors
    while (ptr != null)
    {
        System.out.printf("%d ",ptr . info);
        ptr = inorderSuccessor(ptr);
    }
}
   
// Driver Program
public static void main(String[] args)
{
     Node root = null;
   
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 5);
    root = insert(root, 16);
    root = insert(root, 14);
    root = insert(root, 17);
    root = insert(root, 13);
   
    inorder(root);
} 
}
//contributed by Arnab Kundu

# Insertion in Threaded Binary Search Tree.
class newNode:
    def __init__(self, key):
     
        # False if left pointer points to
        # predecessor in Inorder Traversal
        self.info = key
        self.left = None
        self.right =None
        self.lthread = True
     
        # False if right pointer points to
        # successor in Inorder Traversal
        self.rthread = True
 
# Insert a Node in Binary Threaded Tree
def insert(root, ikey):
     
    # Searching for a Node with given value
    ptr = root
    par = None # Parent of key to be inserted
    while ptr != None:
         
        # If key already exists, return
        if ikey == (ptr.info):
            print("Duplicate Key !")
            return root
 
        par = ptr # Update parent pointer
 
        # Moving on left subtree.
        if ikey < ptr.info:
            if ptr.lthread == False:
                ptr = ptr.left
            else:
                break
 
        # Moving on right subtree.
        else:
            if ptr.rthread == False:
                ptr = ptr.right
            else:
                break
 
    # Create a new node
    tmp = newNode(ikey)
 
    if par == None:
        root = tmp
        tmp.left = None
        tmp.right = None
    else if ikey < (par.info):
        tmp.left = par.left
        tmp.right = par
        par.lthread = False
        par.left = tmp
    else:
        tmp.left = par
        tmp.right = par.right
        par.rthread = False
        par.right = tmp
 
    return root
 
# Returns inorder successor using rthread
def inorderSuccessor(ptr):
     
    # If rthread is set, we can quickly find
    if ptr.rthread == True:
        return ptr.right
 
    # Else return leftmost child of
    # right subtree
    ptr = ptr.right
    while ptr.lthread == False:
        ptr = ptr.left
    return ptr
 
# Printing the threaded tree
def inorder(root):
    if root == None:
        print("Tree is empty")
 
    # Reach leftmost node
    ptr = root
    while ptr.lthread == False:
        ptr = ptr.left
 
    # One by one print successors
    while ptr != None:
        print(ptr.info,end=" ")
        ptr = inorderSuccessor(ptr)
 
# Driver Code
if __name__ == '__main__':
    root = None
 
    root = insert(root, 20)
    root = insert(root, 10)
    root = insert(root, 30)
    root = insert(root, 5)
    root = insert(root, 16)
    root = insert(root, 14)
    root = insert(root, 17)
    root = insert(root, 13)
 
    inorder(root)
     
# This code is contributed by PranchalK

using System;
 
// C# program Insertion in Threaded Binary Search Tree. 
public class solution
{
public class Node
{
     public Node left, right;
    public int info;
 
    // False if left pointer points to predecessor 
    // in Inorder Traversal 
    public bool lthread;
 
    // False if right pointer points to successor 
    // in Inorder Traversal 
    public bool rthread;
}
 
// Insert a Node in Binary Threaded Tree 
public static Node insert(Node root, int ikey)
{
    // Searching for a Node with given value 
    Node ptr = root;
    Node par = null; // Parent of key to be inserted
    while (ptr != null)
    {
        // If key already exists, return 
        if (ikey == (ptr.info))
        {
            Console.Write("Duplicate Key !\n");
            return root;
        }
 
        par = ptr; // Update parent pointer
 
        // Moving on left subtree. 
        if (ikey < ptr.info)
        {
            if (ptr.lthread == false)
            {
                ptr = ptr.left;
            }
            else
            {
                break;
            }
        }
 
        // Moving on right subtree. 
        else
        {
            if (ptr.rthread == false)
            {
                ptr = ptr.right;
            }
            else
            {
                break;
            }
        }
    }
 
    // Create a new node 
    Node tmp = new Node();
    tmp.info = ikey;
    tmp.lthread = true;
    tmp.rthread = true;
 
    if (par == null)
    {
        root = tmp;
        tmp.left = null;
        tmp.right = null;
    }
    else if (ikey < (par.info))
    {
        tmp.left = par.left;
        tmp.right = par;
        par.lthread = false;
        par.left = tmp;
    }
    else
    {
        tmp.left = par;
        tmp.right = par.right;
        par.rthread = false;
        par.right = tmp;
    }
 
    return root;
}
 
// Returns inorder successor using rthread 
public static Node inorderSuccessor(Node ptr)
{
    // If rthread is set, we can quickly find 
    if (ptr.rthread == true)
    {
        return ptr.right;
    }
 
    // Else return leftmost child of right subtree 
    ptr = ptr.right;
    while (ptr.lthread == false)
    {
        ptr = ptr.left;
    }
    return ptr;
}
 
// Printing the threaded tree 
public static void inorder(Node root)
{
    if (root == null)
    {
        Console.Write("Tree is empty");
    }
 
    // Reach leftmost node 
     Node ptr = root;
    while (ptr.lthread == false)
    {
        ptr = ptr.left;
    }
 
    // One by one print successors 
    while (ptr != null)
    {
        Console.Write("{0:D} ",ptr.info);
        ptr = inorderSuccessor(ptr);
    }
}
 
// Driver Program 
public static void Main(string[] args)
{
     Node root = null;
 
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 5);
    root = insert(root, 16);
    root = insert(root, 14);
    root = insert(root, 17);
    root = insert(root, 13);
 
    inorder(root);
}
}
 
  // This code is contributed by Shrikant13

<script>
// javascript program Insertion in Threaded Binary Search Tree.
     class Node {
     constructor(){
this.left = null, this.right = null;
        this.info = 0;
 
        // False if left pointer points to predecessor
        // in Inorder Traversal
        this.lthread = false;
 
        // False if right pointer points to successor
        // in Inorder Traversal
        this.rthread = false;
    }
    }
 
    // Insert a Node in Binary Threaded Tree
    function insert(root , ikey) {
        // Searching for a Node with given value
var ptr = root;
var par = null; // Parent of key to be inserted
        while (ptr != null) {
            // If key already exists, return
            if (ikey == (ptr.info)) {
                document.write("Duplicate Key !\n");
                return root;
            }
 
            par = ptr; // Update parent pointer
 
            // Moving on left subtree.
            if (ikey < ptr.info) {
                if (ptr.lthread == false)
                    ptr = ptr.left;
                else
                    break;
            }
 
            // Moving on right subtree.
            else {
                if (ptr.rthread == false)
                    ptr = ptr.right;
                else
                    break;
            }
        }
 
        // Create a new node
var tmp = new Node();
        tmp.info = ikey;
        tmp.lthread = true;
        tmp.rthread = true;
 
        if (par == null) {
            root = tmp;
            tmp.left = null;
            tmp.right = null;
        } else if (ikey < (par.info)) {
            tmp.left = par.left;
            tmp.right = par;
            par.lthread = false;
            par.left = tmp;
        } else {
            tmp.left = par;
            tmp.right = par.right;
            par.rthread = false;
            par.right = tmp;
        }
 
        return root;
    }
 
    // Returns inorder successor using rthread
    function inorderSuccessor(ptr) {
        // If rthread is set, we can quickly find
        if (ptr.rthread == true)
            return ptr.right;
 
        // Else return leftmost child of right subtree
        ptr = ptr.right;
        while (ptr.lthread == false)
            ptr = ptr.left;
        return ptr;
    }
 
    // Printing the threaded tree
    function inorder(root) {
        if (root == null)
            document.write("Tree is empty");
 
        // Reach leftmost node
var ptr = root;
        while (ptr.lthread == false)
            ptr = ptr.left;
 
        // One by one print successors
        while (ptr != null) {
            document.write(ptr.info+" ");
            ptr = inorderSuccessor(ptr);
        }
    }
 
    // Driver Program
     
var root = null;
 
        root = insert(root, 20);
        root = insert(root, 10);
        root = insert(root, 30);
        root = insert(root, 5);
        root = insert(root, 16);
        root = insert(root, 14);
        root = insert(root, 17);
        root = insert(root, 13);
 
        inorder(root);
 
// This code contributed by aashish1995
</script>

5 10 13 14 16 17 20 30 

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.