三元搜索树

2025年3月17日 | 阅读19分钟

引言

三元搜索树（Ternary Search Tree）是一种字典树（trie）数据结构，它作为 trie 的一种低内存替代方案，常用于拼写检查和查找附近邻居等各种应用。

三元搜索树（TST）是一种复杂而高效的数据结构，它结合了二叉搜索树和 trie 结构的优点。它由 Jon Bentley 和 Robert Sedgewick 在他们 1998 年的开创性论文《Ternary Search Trees》中提出。

要理解三元搜索树，我们必须先掌握 trie 的概念。Trie，也称为数字树（digital tree）、基数树（radix tree）或前缀树（prefix tree），是一种搜索树，一种有序树数据结构，用于使用字符串作为键来存储动态集合或关联数组。

三元搜索树的结构

三元搜索树本质上是一种 trie，其中每个节点有三个子节点，而不是二叉树中传统的两个。节点设计用于按排序顺序存储键中的单个字符。这种独特的结构使得搜索、插入和删除操作非常高效。

1. 节点结构

键：表示与节点关联的字符。
数据：存储与字符关联的值。
左、中、右指针：指向三个子节点。

2. 平衡结构

TST 本质上保持平衡结构，确保高效的搜索和空间优化。
中间子节点有助于平衡树，防止二叉树中常见的倾斜结构。

让我们举一个例子来说明三元搜索树的结构。

在此示例中，TST 表示字符串“CAT”、“ME”、“MET”、“MEX”、“METAL”和“METEOR”。树中的每个节点对应于这些字符串中的一个字符。

三元搜索树的表示

在 trie（标准）数据结构中，每个节点包含 26 个子节点指针，但在三元搜索树中，每个节点仅包含 3 个指针。

左指针指向值小于当前节点的值的节点。
相等指针指向值与当前节点的值相同的节点。
右指针指向值大于当前节点的值的节点。

除了上述三个指针外，每个节点还有一个字段用于指示数据（字典情况下的字符）和一个字段用于指示字符串的结尾。

因此，它类似于 BST，BST 将数据按特定顺序保存。另一方面，三元搜索树中的数据分散在节点之间。例如，您需要四个节点来存储术语“Bird”。

三元搜索树相对于 trie 的一个优点是，三元搜索树占用的空间更少（每个节点只有三个指针，而标准 trie 有 26 个）。此外，三元搜索树可用于任何可以用哈希表存储字符串的场合。

当单词在字母表中分布均匀时，Trie 非常适合，可以最有效地利用空间。当要存储的字符串都具有相同的相同前缀时，三元搜索树更受欢迎；三元搜索树在空间方面最经济。

三元搜索树上的操作

1. 插入

插入操作涉及遍历树，根据需要创建新节点以容纳键的字符。

该过程确保每个节点都按排序顺序插入，从而保持 TST 的固有结构。

2. 搜索

搜索操作涉及基于键的字符遍历树。

在每一步，算法都会将当前字符与当前节点中存储的字符进行比较。

当整个键被遍历并且找到相应的数据时，搜索成功。

3. 删除

TST 中的删除是一项复杂的操作，涉及递归遍历和重构以保持树的平衡。

必须小心处理各种情况，例如具有一个、两个或三个子节点的节点。

性质

类似 Trie 的结构： TST 与 trie 类似，其中每个节点代表字符串的一个字符。但是，与 trie 不同，TST 没有为每个字符设置节点。相反，TST 节点只包含一个字符，并具有指向字符串中下一个字符的节点的指针。
二叉搜索树特性： TST 中的每个节点都遵循二叉搜索树属性，其中左子树中的节点值小于当前节点，右子树中的节点值大于当前节点。
高效搜索： TST 高效地支持前缀搜索、子串搜索和精确匹配搜索。树结构允许在搜索操作期间快速修剪不相关的子树。

实施

#include <iostream>
#include <string>
class TSTNode {
public:
    char data;
    bool isEnd;
    TSTNode* left;
    TSTNode* middle;
    TSTNode* right;
    TSTNode(char val) : data(val), isEnd(false), left(nullptr), middle(nullptr), right(nullptr) {}
};
class TernarySearchTree {
private:
    TSTNode* root;
    // Helper function for insertion
    TSTNode* insert(TSTNode* node, const std::string& key, size_t index);
    // Helper function for search
    bool search(TSTNode* node, const std::string& key, size_t index);
public:
    TernarySearchTree() : root(nullptr) {}
    // Public interface for insertion
    void insert(const std::string& key);
    // Public interface for search
    bool search(const std::string& key);
};
// Implementation of insertion
TSTNode* TernarySearchTree::insert(TSTNode* node, const std::string& key, size_t index) {
    char currentChar = key[index];
    if (!node) {
        node = new TSTNode(currentChar);
    }
    if (currentChar < node->data) {
        node->left = insert(node->left, key, index);
    } else if (currentChar == node->data) {
        if (index < key.length() - 1) {
            node->middle = insert(node->middle, key, index + 1);
        } else {
            node->isEnd = true;
        }
    } else {
        node->right = insert(node->right, key, index);
    }
    return node;
}
// Public interface for insertion
void TernarySearchTree::insert(const std::string& key) {
    root = insert(root, key, 0);
}
// Implementation of search
bool TernarySearchTree::search(TSTNode* node, const std::string& key, size_t index) {
    if (!node) {
        return false;
    }
    char currentChar = key[index];
    if (currentChar < node->data) {
        return search(node->left, key, index);
    } else if (currentChar == node->data) {
        if (index == key.length() - 1) {
            return node->isEnd;
        } else {
            return search(node->middle, key, index + 1);
        }
    } else {
        return search(node->right, key, index);
    }
}
// Public interface for search
bool TernarySearchTree::search(const std::string& key) {
    return search(root, key, 0);
}
// Example usage
int main() {
    TernarySearchTree tst;
    tst.insert("apple");
    tst.insert("banana");
    tst.insert("orange");
    std::cout << "Search for 'apple': " << (tst.search("apple") ? "Found" : "Not found") << std::endl;
    std::cout << "Search for 'grape': " << (tst.search("grape") ? "Found" : "Not found") << std::endl;
    return 0;
}

说明

该程序定义了一个名为 TSTNode 的类，表示三元搜索树中的一个节点。
每个节点包含一个字符（data）、一个布尔标志（isEnd），指示节点是否表示单词的结尾，以及三个指针（left, middle, and right），分别指向左、中、右子节点。
构造函数使用给定的字符初始化节点。
该程序还定义了一个名为 TernarySearchTree 的类，该类封装了 TST。它包括一个私有成员 root，表示 TST 的根。
三元搜索树通过递归辅助函数 insert 支持插入。该函数接受一个节点、一个键（要插入的字符串）以及键中的当前索引。
它根据键的字符递归地遍历树，在需要时创建新节点，直到到达键的末尾。insert 函数在内部使用，并且不对外公开。
TST 通过递归辅助函数 search 提供搜索操作。此函数检查键的字符是否与树节点匹配，并继续搜索直到到达键的末尾，验证最后一个节点是否标记为单词的结尾。
公共 search 方法 search(const std::string& key) 作为用户界面，通过调用带有 root 和初始索引的私有 search 函数来启动搜索过程。
公共插入方法 insert(const std::string& key) 作为界面，通过调用带有 root 和初始索引的私有 insert 函数来启动插入过程。
在 main 函数中，创建了 TernarySearchTree 的一个实例，并使用 insert 方法将三个单词（“apple”、“banana”和“orange”）插入到 TST 中。
然后，程序使用 search 方法搜索单词“apple”和“grape”，并打印每个单词是否找到。

程序输出

Java 代码

现在我们来编写一个 Java 程序来实现三元搜索树。

/** 
 ** A sample Java program to implement Ternary Search Tree 
 **/  
import java.util.Scanner;  
import java.util.ArrayList;  
/** class TSTNode **/  
class TSTNode  
{  
    char data;  
    boolean isEnd;  
    TSTNode left, middle, right;  
    /** Constructor **/  
    public TSTNode(char data)  
    {  
        this.data = data;  
        this.isEnd = false;  
        this.left = null;  
        this.middle = null;  
        this.right = null;  
    }          
}   
/** class TernarySearchTree **/  
class TernarySearchTree  
{  
    private TSTNode root;  
    private ArrayList<String> al;  
   
    /** Constructor **/  
    public TernarySearchTree()  
    {  
        root = null;  
    }  
    /** function to check if empty **/  
    public boolean isEmpty()  
    {  
        return root == null;  
    }  
    /** function to clear **/  
    public void makeEmpty()  
    {  
        root = null;  
    }  
    /** function to insert for a word **/  
    public void insert(String word)  
    {  
        root = insert(root, word.toCharArray(), 0);  
    }  
    /** function to insert for a word **/  
    public TSTNode insert(TSTNode r, char[] word, int ptr)  
    {  
        if (r == null)  
            r = new TSTNode(word[ptr]);  
        if (word[ptr] < r.data)  
            r.left = insert(r.left, word, ptr);  
        else if (word[ptr] > r.data)  
            r.right = insert(r.right, word, ptr);  
        else  
        {  
            if (ptr + 1 < word.length)  
                r.middle = insert(r.middle, word, ptr + 1);  
            else  
                r.isEnd = true;  
        }  
        return r;  
    }   
    /** function to delete a word **/  
    public void delete(String word)  
    {  
        delete(root, word.toCharArray(), 0);  
    }  
    /** function to delete a word **/  
    private void delete(TSTNode r, char[] word, int ptr)  
    {  
        if (r == null)  
            return;   
        if (word[ptr] < r.data)  
            delete(r.left, word, ptr);  
        else if (word[ptr] > r.data)  
            delete(r.right, word, ptr);  
        else  
        {  
            /** to delete a word just make isEnd false **/  
            if (r.isEnd && ptr == word.length - 1)  
                r.isEnd = false;  
            else if (ptr + 1 < word.length)  
                delete(r.middle, word, ptr + 1);  
        }          
    }   
    /** function to search for a word **/  
    public boolean search(String word)  
    {  
        return search(root, word.toCharArray(), 0);  
    }  
    /** function to search for a word **/  
    private boolean search(TSTNode r, char[] word, int ptr)  
    {  
        if (r == null)  
            return false;  
        if (word[ptr] < r.data)  
            return search(r.left, word, ptr);  
        else if (word[ptr] > r.data)  
            return search(r.right, word, ptr);  
        else  
        {  
            if (r.isEnd && ptr == word.length - 1)  
                return true;  
            else if (ptr == word.length - 1)  
                return false;  
            else  
                return search(r.middle, word, ptr + 1);  
        }          
    }  
    /** function to print tree **/  
    public String toString()  
    {  
        al = new ArrayList<String>();  
        traverse(root, "");  
        return "\nTernary Search Tree : "+ al;  
    }  
    /** function to traverse tree **/  
    private void traverse(TSTNode r, String str)  
    {  
        if (r != null)  
        {  
            traverse(r.left, str);  
            str = str + r.data;  
            if (r.isEnd)  
                al.add(str);   
            traverse(r.middle, str);  
            str = str.substring(0, str.length() - 1);   
            traverse(r.right, str);  
        }  
    }  
}  
/** class TernarySearchTree **/  
public class TernarySearchTreeTest  
{  
    public static void main(String[] args)  
    {  
        Scanner scan = new Scanner(System.in);   
        /* Creating object of TernarySearchTree */  
        TernarySearchTree tst = new TernarySearchTree();   
        System.out.println("Ternary Search Tree Test\n");   
        char ch;  
        /*  Perform tree operations  */  
        do      
        {  
            System.out.println("\nSelect one of the operation for Ternary Search Tree::");  
            System.out.println("1. To insert a new word in the Ternary Search Tree.");  
            System.out.println("2. To search an already existing word in the Ternary Search Tree.");  
            System.out.println("3. To delete a word from the Ternary Search Tree");  
            System.out.println("4. To check if the Ternary Tree is empty.");  
            System.out.println("5. To make the Ternary Search Tree empty.");  
            int choice = scan.nextInt();              
            switch (choice)  
            {  
            case 1 :   
                System.out.println("Enter word to insert");  
                tst.insert( scan.next() );                       
                break;                            
            case 2 :   
                System.out.println("Enter word to search");  
                System.out.println("Search result : "+ tst.search( scan.next() ));  
                break;   
            case 3 :   
                System.out.println("Enter word to delete");  
                tst.delete( scan.next() );                       
                break;   
            case 4 :   
                System.out.println("Empty Status : "+ tst.isEmpty() );                  
                break;      
            case 5 :   
                System.out.println("Ternary Search Tree cleared");   
                tst.makeEmpty();                 
                break;                                          
            default :   
                System.out.println("Wrong Entry \n ");  
                break;     
            }  
            System.out.println(tst);   
            System.out.println("\nDo you want to continue (Type y or n) \n");  
            ch = scan.next().charAt(0);                          
        } while (ch == 'Y'|| ch == 'y');          
    }  
}  

输出

上面的 Java 代码产生以下输出。

Ternary Search Tree Test
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
red
Ternary Search Tree : [red]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
blur e
Ternary Search Tree : [blue, red]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
green
Ternary Search Tree : [blue, green, red]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
yellow
Ternary Search Tree : [blue, green, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
pink
Ternary Search Tree : [blue, green, pink, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
black
Ternary Search Tree : [black, blue, green, pink, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
grey
Ternary Search Tree : [black, blue, green, grey, pink, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
mustard
Ternary Search Tree : [black, blue, green, grey, mustard, pink, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
White
Ternary Search Tree : [White, black, blue, green, grey, mustard, pink, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
1
Enter the word to insert
purple
Ternary Search Tree : [White, black, blue, green, grey, mustard, pink, purple, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
2
Enter the word to search
black
Search result: true
Ternary Search Tree : [White, black, blue, green, grey, mustard, pink, purple, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
3
Enter the word to delete
blue mustard
Ternary Search Tree : [White, black, blue, green, grey, pink, purple, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
4
Empty Status: false
Ternary Search Tree : [White, black, blue, green, grey, pink, purple, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
3
Enter the word to delete
black
Ternary Search Tree : [White, blue, green, grey, pink, purple, red, yellow]
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Tree is empty.
5. To make the Ternary Search Tree empty.
5
Ternary Search Tree cleared
Ternary Search Tree : []
Do you want to continue (Type y or n)
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To delete a word from the Ternary Search Tree
4. To check if the Ternary Search Tree is empty.
5. To make the Ternary Search Tree empty.
4
Empty Status: true
Ternary Search Tree : []
Do you want to continue (Type y or n)
n

在上面的 Java 代码中，我们实现了三元搜索树数据结构和各种函数，例如在三元搜索树中添加新数据、从三元搜索树中删除现有数据、检查三元搜索树是否为空，还有一个清空树的操作，该操作将删除三元搜索树中的所有内容，以及对三元搜索树的遍历。

为了对三元搜索树数据结构执行所有这些操作，编写了不同的函数，然后根据对三元搜索树数据结构的操作需求调用这些函数。

C++ 代码

让我们编写三元搜索树的 C++ 代码。

/* 
 * C++ Program to implement Ternary Seach Tree
 */
#include <iostream>
#include <cstdlib>
#define MAX 50
using namespace std; 
/* 
 * Node Declaration
 */
struct Node
{
    char data;
    unsigned isEndOfString: 1;
    Node *left, *eq, *right;
};
/* 
 * create a new ternary search tree node
 */ 
Node* newNode(char data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->isEndOfString = 0;
    temp->left = temp->eq = temp->right = NULL;
    return temp;
}
/* 
 * insert a new word in a Ternary Search Tree
 */ 
void insert(Node** root, char *word)
{
    if (!(*root))
        *root = newNode(*word);
    if ((*word) < (*root)->data)
        insert(&((*root)->left), word);
    else if ((*word) > (*root)->data)
        insert(&((*root)->right), word);
    else
    {
        if (*(word + 1))
            insert(&( (*root)->eq ), word + 1);
        else
            (*root)->isEndOfString = 1;
    }
}
/* 
 * traverse Utility function
 */  
void traverseTSTUtil(Node* root, char* buffer, int depth)
{
    if (root)
    {
        traverseTSTUtil(root->left, buffer, depth);
        buffer[depth] = root->data;
        if (root->isEndOfString)
        {
            buffer[depth + 1] = '\0';
            cout<<buffer<<endl;
        }
        traverseTSTUtil(root->eq, buffer, depth + 1);
        traverseTSTUtil(root->right, buffer, depth);
    }
}
/* 
 * traverse Ternary Search Tree
 */  
void traverseTST(Node* root)
{
    char buffer[MAX];
    traverseTSTUtil(root, buffer, 0);
}
/* 
 * search a given word in Ternary Search Tree
 */  
int searchTST(Node *root, char *word)
{
    if (!root)
        return 0;
    if (*word < (root)->data)
        return searchTST(root->left, word);
    else if (*word > (root)->data)
        return searchTST(root->right, word);
    else
    {
        if (*(word + 1) == '\0')
            return root->isEndOfString;
        return searchTST(root->eq, word+1);
    }
}
/* 
 * beginning of the Main function to call all the functions of the ternary search tree.
 */  
int main()
{
    Node *root = NULL;
    char s[100];
        char ch;
        /*  Perform tree operations  */
        do    
        {
            cout<<"\nSelect one of the operation for Ternary Search Tree::"<<endl;
            cout<<"1. To insert a new word in the Ternary Search Tree."<<endl;
            cout<<"2. To search an already exisitng word in the Ternary Search Tree."<<endl;
            cout<<"3. To Traverse the Ternary Search Tree."<<endl;             
            int choice;
            cin>>choice;            
            switch (choice)
            {
            case 1 : 
                cout<<"Enter word to insert"<<endl;
                cin>>s;
                insert(&root,s);                     
                break;                          
            case 2 : 
                cout<<"Enter word to search"<<endl;
                cin>>s;
                if (searchTST(root, s))
                    cout<<s<<" found in Ternary Search Tree"<<endl;
                else
                    cout<<s<<" not found in Ternary Search Tree"<<endl;
                break; 
            case 3 : 
                cout<<"Contents of the Ternary Search Tree are::"<<endl;
                traverseTST(root);
                break; 
            default : 
                cout<<"Wrong Entry \n ";
                break;   
            }
            cout<<"\nDo you want to continue (Type y or n) \n";
            cin>>ch;                        
        } while (ch == 'Y'|| ch == 'y');
return 0;
}

输出

上面的 C++ 代码产生以下输出。

Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
1
Enter the word to insert
orange 
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
1
Enter the word to insert
banana
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
1
Enter the word to insert
grapes 
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
1
Enter the word to insert
apple
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
1
Enter the word to insert
watermelon
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
1
Enter the word to insert
guava
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
1
Enter the word to insert
Kiwi
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
3
Contents of the Ternary Search Tree are::
Kiwi
apple
Banana
Watermelon
guava
grapes
orange
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
2
Enter the word to search
Kiwi
Kiwi found in Ternary Search Tree
Do you want to continue (Type y or n) 
y
Select one of the operations for Ternary Search Tree::
1. To insert a new word in the Ternary Search Tree.
2. To search an already existing word in the Ternary Search Tree.
3. To Traverse the Ternary Search Tree.
2
Enter the word to search
mango
mango not found in Ternary Search Tree
Do you want to continue (Type y or n) 
n

在上面的 C++ 代码中，我们实现了三元搜索树数据结构和各种函数，例如添加新数据、删除现有数据以及对三元搜索树的遍历。为了对三元搜索树数据结构执行所有这些操作，编写了不同的函数，然后根据对三元搜索树数据结构的操作需求调用这些函数。

实际应用

1. 拼写检查

TST 被广泛用于拼写检查算法，以高效地搜索和建议正确的拼写。

2. IP 路由

三元搜索树用于 IP 路由表中，以快速定位给定 IP 地址的最长匹配前缀。

3. 自动完成

TST 为搜索引擎和文本编辑器中的自动完成功能提供支持，提供快速准确的建议。

4. 符号表

TST 作为高效符号表的基础，有助于符号的快速检索和修改。

下一个主题股票跨度问题

三元搜索树

引言

三元搜索树的结构

三元搜索树的表示

三元搜索树上的操作

性质

实施

Java 代码

C++ 代码

实际应用

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

三元搜索树

引言

三元搜索树的结构

三元搜索树的表示

三元搜索树上的操作

性质

实施

Java 代码

C++ 代码

实际应用

相关帖子

检测并移除链表中的循环

将中缀表达式转换为前缀表达式

B 树可视化

数据结构中的多项式加法

通用树 (每个节点可以有任意数量的子节点) 层序遍历

双指针技术

合并 K 个排序链表

Morris 后序遍历

检查表达式中的括号是否平衡 (格式正确性)

查找二叉树中两个节点的直接父节点

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器