Рубрики

Троичное дерево поиска

Тройное дерево поиска — это специальная структура данных дерева, в которой дочерние узлы стандартного дерева дерева упорядочены как двоичное дерево поиска.

Представление троичных поисковых деревьев:
В отличие от стандартной (стандартной) структуры данных, где каждый узел содержит 26 указателей для своих дочерних элементов, каждый узел в троичном дереве поиска содержит только 3 указателя:
1. Левый указатель указывает на узел, значение которого меньше значения в текущем узле.
2. Равный указатель указывает на узел, значение которого равно значению в текущем узле.
3. Правый указатель указывает на узел, значение которого больше, чем значение в текущем узле.

Помимо трех вышеупомянутых указателей, у каждого узла есть поле для указания данных (символ в случае словаря) и другое поле для обозначения конца строки.
Таким образом, более или менее это похоже на BST, который хранит данные в некотором порядке. Однако данные в троичном дереве поиска распределяются по узлам. Например, для хранения слова «Geek» нужны 4 узла.
На рисунке ниже показано, как именно хранятся слова в троичном дереве поиска.

Одним из преимуществ использования троичных деревьев поиска по сравнению с попытками является то, что троичные деревья поиска более экономичны (задействуют только три указателя на узел по сравнению с 26 указателями в стандартных попытках). Кроме того, троичные деревья поиска могут использоваться каждый раз, когда для хранения строк используется хеш-таблица.

Попытки подходят, когда есть правильное распределение слов по алфавиту, чтобы пробелы использовались наиболее эффективно. В противном случае троичные поисковые деревья лучше. Тернарные деревья поиска эффективны в использовании (с точки зрения пространства), когда строки, подлежащие сохранению, имеют общий префикс.

Приложения троичных поисковых деревьев:
1. Тернарные деревья поиска эффективны для запросов типа «По заданному слову найти следующее слово в словаре (поиск ближайших соседей)» или «Найти все телефонные номера, начинающиеся с 9342, или« при вводе нескольких начальных символов в веб-браузере отображаются все веб-сайты. имена с этим префиксом »(функция автозаполнения)».

2. Используется при проверке орфографии: деревья троичного поиска могут использоваться как словарь для хранения всех слов. Как только слово набрано в редакторе, его можно параллельно искать в дереве троичного поиска, чтобы проверить правильность написания.

Реализация:
Ниже приведена реализация троичного дерева поиска. Реализованные операции: поиск, вставка и обход.

// C программа для демонстрации вставки троичного поискового дерева (TST), путешествия
// и поисковые операции
#include <stdio.h>
#include <stdlib.h>
#define MAX 50

  
// Узел троичного дерева поиска

struct Node

{

    char data;

  

    // True, если этот символ является последним символом одного из слов

    unsigned isEndOfString: 1;

  

    struct Node *left, *eq, *right;

};

  
// Вспомогательная функция для создания нового узла троичного поискового дерева

struct Node* newNode(char data)

{

    struct Node* temp = (struct Node*) malloc(sizeof( struct Node ));

    temp->data = data;

    temp->isEndOfString = 0;

    temp->left = temp->eq = temp->right = NULL;

    return temp;

}

  
// Функция для вставки нового слова в троичное дерево поиска

void insert(struct 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);

  

    // Если текущий символ слова совпадает с символом root,

    else

    {

        if (*(word+1))

            insert(&( (*root)->eq ), word+1);

  

        // последний символ слова

        else

            (*root)->isEndOfString = 1;

    }

}

  
// Рекурсивная функция для обхода троичного дерева поиска

void traverseTSTUtil(struct Node* root, char* buffer, int depth)

{

    if (root)

    {

        // Первый переход по левому поддереву

        traverseTSTUtil(root->left, buffer, depth);

  

        // Сохраняем символ этого узла

        buffer[depth] = root->data;

        if (root->isEndOfString)

        {

            buffer[depth+1] = '\0';

            printf( "%s\n", buffer);

        }

  

        // Обход поддерева с использованием равного указателя (среднее поддерево)

        traverseTSTUtil(root->eq, buffer, depth + 1);

  

        // Наконец пройти через правое поддерево

        traverseTSTUtil(root->right, buffer, depth);

    }

}

  
// Основная функция для обхода троичного дерева поиска.
// Он в основном использует traverseTSTUtil ()

void traverseTST(struct Node* root)

{

    char buffer[MAX];

    traverseTSTUtil(root, buffer, 0);

}

  
// Функция для поиска заданного слова в TST

int searchTST(struct 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);

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Node *root = NULL;

  

    insert(&root, "cat");

    insert(&root, "cats");

    insert(&root, "up");

    insert(&root, "bug");

  

    printf("Following is traversal of ternary search tree\n");

    traverseTST(root);

  

    printf("\nFollowing are search results for cats, bu and cat respectively\n");

    searchTST(root, "cats")? printf("Found\n"): printf("Not Found\n");

    searchTST(root, "bu")?   printf("Found\n"): printf("Not Found\n");

    searchTST(root, "cat")?  printf("Found\n"): printf("Not Found\n");

  

    return 0;

}

Выход:

Following is traversal of ternary search tree
bug
cat
cats
up

Following are search results for cats, bu and cat respectively
Found
Not Found
Found

Сложность времени: временная сложность операций троичного дерева поиска аналогична сложности двоичного дерева поиска. т.е. операции вставки, удаления и поиска занимают время, пропорциональное высоте троичного дерева поиска. Пространство пропорционально длине строки, которая будет сохранена.

Ссылка:
http://en.wikipedia.org/wiki/Ternary_search_tree

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Троичное дерево поиска

0.00 (0%) 0 votes