Поисковые деревья m-WAY | Комплект-1 (Поиск)

Опубликовано: 12 Января, 2022

M- сторонние деревья поиска - это многосторонние деревья, которые представляют собой обобщенные версии двоичных деревьев, в которых каждый узел содержит несколько элементов. В m-Way дереве порядка m каждый узел содержит не более m - 1 элемента и m дочерних элементов.

Цель m-Way поискового дерева высоты h требует O (h) no. доступов для операции вставки / удаления / извлечения. Следовательно, это гарантирует, что высота h близка к log_m (n + 1) .

Количество элементов в дереве поиска m-Way высоты h колеблется от минимума h до максимума .

Дерево поиска m-Way из n элементов находится в диапазоне от минимальной высоты log_m (n + 1) до максимума n.

Пример 5-стороннего дерева поиска показан на рисунке ниже. Обратите внимание на то, что каждый узел имеет не более 5 дочерних узлов и, следовательно, содержит не более 4 ключей.

The structure of a node of an m-Way tree is given below:

struct node {
    int count;
    int value[MAX + 1];
    struct node* child[MAX + 1];
};

Here, count represents the number of children that a particular node has
The values of a node stored in the array value
The addresses of child nodes are stored in the child array
The MAX macro signifies the maximum number of values that a particular node can contain

Поиск в дереве поиска m-Way:

Поиск ключа в дереве поиска m-Way аналогичен поиску в двоичном дереве поиска.
Чтобы найти 77 в 5-стороннем дереве поиска, показанном на рисунке, мы начинаем с корня и, поскольку 77> 76> 44> 18, переходим к четвертому поддереву.
В корневом узле четвертого поддерева 77 <80 & поэтому мы переходим к первому поддереву узла. Поскольку 77 доступно в единственном узле этого поддерева, мы утверждаем, что поиск 77 был успешно выполнен.

// Searches value in the node
struct node* search(int val,
                    struct node* root,
                    int* pos)
{
  
    // if root is Null then return
    if (root == NULL)
        return NULL;
    else {
  
        // if node is found
        if (searchnode(val, root, pos))
            return root;
  
        // if not then search in child nodes
        else
            return search(val,
                          root->child[*pos],
                          pos);
    }
}
  
// Searches the node
int searchnode(int val,
               struct node* n,
               int* pos)
{
    // if val is less than node->value[1]
    if (val < n->value[1]) {
        *pos = 0;
        return 0;
    }
  
    // if the val is greater
    else {
        *pos = n->count;
  
        // check in the child array
        // for correct position
        while ((val < n->value[*pos])
               && *pos > 1)
            (*pos)--;
        if (val == n->value[*pos])
            return 1;
        else
            return 0;
    }
}

поиск():

Функция search () получает три параметра
Первый параметр - это значение для поиска, второй - это адрес узла, с которого должен выполняться поиск, а третий - это адрес переменной, которая используется для хранения позиции найденного значения.
Первоначально проверяется условие, является ли адрес искомого узла NULL.
Если это так, то просто возвращается значение NULL.
В противном случае вызывается функция searchchnode (), которая фактически ищет заданное значение.
Если поиск успешен, возвращается адрес узла, в котором найдено значение.
Если поиск не увенчался успехом, выполняется рекурсивный вызов функции search () для дочернего элемента текущего узла.

searchchnode ():

Функция searchchnode () получает три параметра
Первый параметр - это значение, которое нужно найти.
Второй параметр - это адрес узла, в котором должен выполняться поиск, а третий - указатель pos, который содержит адрес переменной, в которой сохраняется позиция значения, которое однажды было найдено.
Эта функция возвращает значение 0, если поиск завершился неудачно, и 1, если он успешен.
В этой функции сначала проверяется, меньше ли искомое значение, чем самое первое значение узла.
Если это так, это означает, что значение отсутствует в текущем узле. Следовательно, значение 0 присваивается переменной, на которую указывает pos, и возвращается 0, поскольку поиск неуспешен.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Поисковые деревья m-WAY | Комплект-1 (Поиск)

РЕКОМЕНДУЕМЫЕ СТАТЬИ