Árbol de búsqueda ternario (eliminación)

En la publicación SET 1 sobre TST, hemos descrito cómo insertar y buscar un Node en TST. En este artículo, discutiremos el algoritmo sobre cómo eliminar un Node de TST.

Durante la operación de eliminación, eliminamos la clave de forma ascendente utilizando la recursividad. Los siguientes son casos posibles al eliminar una clave de trie.

1. Es posible que la clave no esté allí en TST. 
   Solución: la operación de eliminación no debe modificar el TST.
2. Clave presente como clave única (ninguna parte de la clave contiene otra clave (prefijo), ni la clave en sí es prefijo de otra clave en TST). 
   Solución: elimine todos los Nodes.
3. La clave es la clave de prefijo de otra clave larga en TST. 
   Solución: desmarque el Node hoja.
4. Clave presente en TST, teniendo al menos otra clave como prefijo. 
   Solución: elimine los Nodes desde el final de la clave hasta el primer Node de hoja de la clave de prefijo más larga.

Explicación de la función delete_node

1. Supongamos que queremos eliminar la string «BIG», ya que no está presente en TST, por lo que después de hacer coincidir con el primer carácter ‘B’, la función delete_node devolverá cero. Por lo tanto, no se elimina nada.
2. Ahora queremos eliminar la string «BUG», está presente de forma única en TST, es decir, no tiene una parte que sea el prefijo de otra string ni es el prefijo de ninguna otra string, por lo que se eliminará por completo.
3. Ahora queremos eliminar la string «CAT», ya que es el prefijo de la string «CATS», no podemos eliminar nada de la string «CAT» y solo podemos desmarcar el Node hoja que asegurará que «CAT» ya no sea miembro. string de TST.
4. Ahora queremos eliminar la string «CATS», ya que tiene una string de prefijo «CAT» que también es una string miembro de TST, por lo que solo podemos eliminar el último carácter de la string «CATS», lo que garantizará que la string «CAT» siga siendo la parte de TST.

Implementación:

// C program to demonstrate deletion in
// Ternary Search Tree (TST). For insert
// and other functions, refer
// https://www.geeksforgeeks.org/ternary-search-tree/
#include<stdio.h>
#include<stdlib.h>
 
// structure of a node in TST
struct Node
{
    char key;
    int isleaf;
    struct Node *left;
    struct Node *eq;
    struct Node *right;
};
 
// function to create a Node in TST
struct Node *createNode(char key)
{
    struct Node *temp =
        (struct Node*)malloc(sizeof(struct Node));
    temp->key = key;
    temp->isleaf = 0;
    temp->left = NULL;
    temp->eq = NULL;
    temp->right = NULL;
    return temp;
};
 
// function to insert a Node in TST
void insert_node(struct Node **root ,char *s)
{
    if (!(*root))
        (*root) = createNode(*s);
 
    if ((*s)<(*root)->key)
        insert_node( &(*root)->left ,s);
 
    else if ((*s)>(*root)->key)
        insert_node( &(*root)->right ,s);
 
    else if ((*s) == (*root)->key)
    {
        if (*(s+1) == '\0')
        {
            (*root)->isleaf = 1;
            return;
        }
        insert_node( &(*root)->eq ,s+1);
    }
}
 
// function to display the TST
void display(struct Node *root, char str[], int level)
{
    if (!root)
        return;
 
    display(root->left ,str ,level);
    str[level] = root->key;
 
    if (root->isleaf == 1)
    {
        str[level+1] = '\0';
        printf("%s\n",str);
    }
 
    display(root->eq ,str ,level+1);
    display(root->right ,str ,level);
}
 
// to check if current Node is leaf node or not
int isLeaf(struct Node *root)
{
    return root->isleaf == 1;
}
 
// to check if current node has any child node or not
int isFreeNode(struct Node *root)
{
    if (root->left ||root->eq ||root->right)
        return 0;
    return 1;
}
 
// function to delete a string in TST
int delete_node(struct Node *root, char str[],
                int level ,int n)
{
    if (root == NULL)
        return 0;
 
 
    // CASE 4 Key present in TST, having
    // atleast one other key as prefix key.
    if (str[level+1] == '\0')
    {
        // Unmark leaf node if present
        if (isLeaf(root))
        {
            root->isleaf=0;
            return isFreeNode(root);
        }
 
        // else string is not present in TST and
        // return 0
        else
            return 0;
    }
    else
    {
        // CASE 3 Key is prefix key of another
        // long key in TST.
        if (str[level] < root->key)
            delete_node(root->left ,str ,level ,n);
        else if (str[level] > root->key)
            delete_node(root->right ,str ,level ,n);
 
        // CASE 1 Key may not be there in TST.
        else if (str[level] == root->key)
        {
            // CASE 2 Key present as unique key
            if( delete_node(root->eq ,str ,level+1 ,n) )
            {
                // delete the last node, neither it
                // has any child
                // nor it is part of any other string
                free(root->eq);
                return !isLeaf(root) && isFreeNode(root);
            }
        }
    }
 
    return 0;
}
 
// Driver function
int main()
{
    struct Node *temp = NULL;
 
    insert_node(&temp ,"CAT");
    insert_node(&temp ,"BUGS");
    insert_node(&temp ,"CATS");
    insert_node(&temp ,"UP");
 
    int level = 0;
    char str[20];
    int p = 0;
 
    printf( "1.Content of the TST before "
            "deletion:\n" );
    display(temp ,str ,level);
 
    level = 0;
    delete_node(temp ,"CAT" ,level ,5);
 
    level = 0;
    printf("\n2.Content of the TST after "
           "deletion:\n");
    display(temp, str, level);
    return 0;
}

// C++ program to demonstrate deletion in
// Ternary Search Tree (TST)
// For insert and other functions, refer
// https://www.geeksforgeeks.org/ternary-search-tree
 
#include<bits/stdc++.h>
using namespace std;
 
// structure of a node in TST
struct Node
{
    char key;
    int isleaf;
    struct Node *left;
    struct Node *eq;
    struct Node *right;
};
 
// function to create a node in TST
struct Node *createNode(char key)
{
    struct Node *temp = new Node;
    temp->key = key;
    temp->isleaf = 0;
    temp->left = NULL;
    temp->eq = NULL;
    temp->right = NULL;
    return temp;
};
 
// function to insert a Node in TST
void insert_node(struct Node **root, string s)
{
    if((int)s.length()==0)
        return;
    if (!(*root))
    {
        (*root) = createNode(s[0]);
        // return;
    }
 
    if ((s[0])<(*root)->key)
        insert_node( &(*root)->left, s);
 
    else if ((s[0])>(*root)->key)
        insert_node( &(*root)->right, s);
 
    else if ((s[0]) == (*root)->key)
    {
        if ((int)s.length() == 1)
        {
            (*root)->isleaf = 1;
            return;
        }
        insert_node( &(*root)->eq, s.substr(1));
    }
}
 
// function to display the TST
void display(struct Node *root, char str[], int level)
{
    if (!root)
        return;
 
    display(root->left, str, level);
    str[level] = root->key;
 
    if (root->isleaf == 1)
    {
        str[level+1] = '\0';
        cout<< str <<endl;
    }
 
    display(root->eq, str, level+1);
    display(root->right, str, level);
}
 
//to check if current node is leaf node or not
int isLeaf(struct Node *root)
{
    return root->isleaf == 1;
}
 
// to check if current node has any child
// node or not
int isFreeNode(struct Node *root)
{
    if (root->left ||root->eq ||root->right)
        return 0;
    return 1;
}
 
// function to delete a string in TST
int delete_node(struct Node *root, string str,
                int level, int n)
{
    if (root == NULL)
        return 0;
 
 
    // CASE 4 Key present in TST, having atleast
    // one other key as prefix key.
    if (str[level+1] == '\0')
    {
        // Unmark leaf node if present
        if (isLeaf(root))
        {
            root->isleaf = 0;
            return isFreeNode(root);
        }
 
        // else string is not present in TST and
        // return 0
        else
            return 0;
    }
 
    // CASE 3 Key is prefix key of another long
    // key in TST.
    if (str[level] < root->key)
        return delete_node(root->left, str, level, n);
    if (str[level] > root->key)
        return delete_node(root->right, str, level, n);
 
    // CASE 1 Key may not be there in TST.
    if (str[level] == root->key)
    {
        // CASE 2 Key present as unique key
        if (delete_node(root->eq, str, level+1, n))
        {
            // delete the last node, neither it has
            // any child nor it is part of any other
            // string
            delete(root->eq);
            return !isLeaf(root) && isFreeNode(root);
        }
    }
 
    return 0;
}
 
// Driver function
int main()
{
    struct Node *temp = NULL;
 
    insert_node(&temp, "CAT");
    insert_node(&temp, "BUGS");
    insert_node(&temp, "CATS");
    insert_node(&temp, "UP");
 
    int level = 0;
    char str[20];
    int p = 0;
 
    cout << "1.Content of the TST before deletion:\n";
    display(temp, str, 0);
 
    level = 0;
    delete_node(temp,"CAT", level, 5);
 
    level = 0;
    cout << "\n2.Content of the TST after deletion:\n";
    display(temp, str, level);
    return 0;
}

# Python 3 program to demonstrate deletion in
# Ternary Search Tree (TST)
# For insert and other functions, refer
# https://www.geeksforgeeks.org/ternary-search-tree
 
 
# class of a node in TST
class Node:
    def __init__(self,key):
        self.key=key
        self.isleaf=False
        self.left=None
        self.eq=None
        self.right=None
 
# function to insert a Node in TST
def insert_node(root, s):
 
    if s=='':
        return root
    if not root:
        root = Node(s[0])
 
    if ((s[0])<root.key):
        root.left=insert_node(root.left, s)
 
    elif (s[0]>root.key):
        root.right=insert_node(root.right, s)
    else:
        if (len(s) == 1):
            root.isleaf = True
            return root
        root.eq=insert_node(root.eq, s[1:])
 
    return root
 
# function to display the TST
def display(root, s, level):
    if not root:
        return
 
    display(root.left, s, level)
    s[level] = root.key
 
    if (root.isleaf):
        s[level+1] = ''
        print(''.join(s[:level+1]))
 
    display(root.eq, s, level+1)
    display(root.right, s, level)
 
 
# to check if current node has any child
# node or not
def isFreeNode(root):
    return not (root.left or root.eq or root.right)
 
# function to delete a string in TST
def delete_node(root, s, level):
    if not root:
        return False
 
    # CASE 4 Key present in TST, having atleast
    # one other key as prefix key.
    if level+1 == len(s):
        # Unmark leaf node if present
        if root.isleaf:
            root.isleaf = False
            return isFreeNode(root)
 
        # else string is not present in TST and
        # return 0
        return False
 
    # CASE 3 Key is prefix key of another long
    # key in TST.
    if s[level] < root.key:
        return delete_node(root.left, s, level)
    if s[level] > root.key:
        return delete_node(root.right, s, level)
 
    # CASE 1 Key may not be there in TST.
    if s[level] == root.key and delete_node(root.eq, s, level+1):
        # delete the last node, neither it has
        # any child nor it is part of any other
        # string
        root.eq = None
        return not root.isleaf and isFreeNode(root)
 
    return False
 
 
# Driver function
if __name__ == '__main__':
    temp = None
 
    temp=insert_node(temp, "CAT")
    temp=insert_node(temp, "BUGS")
    temp=insert_node(temp, "CATS")
    temp=insert_node(temp, "UP")
 
    level = 0;s=['']*20
 
    print("1.Content of the TST before deletion:")
    display(temp, s, 0)
 
 
    print("2.Content of the TST after deletion:")
    delete_node(temp,"CAT", level)
    display(temp, s, level)

1.Content of the TST before deletion:
BUGS
CAT
CATS
UP

2.Content of the TST after deletion:
BUGS
CATS
UP

Este artículo es una contribución de Yash Singla . 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.