Деревья поиска. Организация: свойство упорядоченности и поиск за O(log N)

Модуль "Деревья поиска" • урок 1 из 8 • ~6 минут

Деревья поиска. Организация: правило размещения ключей

Двоичные деревья часто употребляются для представления множеств данных, в которых необходимо осуществлять быстрый поиск элементов по ключу. Если дерево организовано таким образом, что для любой его вершины выполняется следующее жесткое правило: все ключи в ее левом поддереве строго меньше ее ключа, а все ключи в правом поддереве строго больше ее ключа, то такое дерево называется деревом поиска (Binary Search Tree, BST).

Главным преимуществом такой организации является существенное сокращение времени поиска по сравнению с линейными структурами (списками). На каждом шаге поиска, сравнивая искомый ключ с ключом текущего узла, алгоритм переходит либо в левое, либо в правое поддерево, автоматически отбрасывая половину оставшихся вариантов. В идеально сбалансированном дереве максимальное количество сравнений не превышает его высоты, которая пропорциональна log2(N), где N - количество элементов. Таким образом, время поиска значительно сокращается: O(log N) вместо O(N).

Поиск в дереве (алгоритм)

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

struct node {
    int key;
    struct node* l;
    struct node* r;
};

/* Итеративный поиск в дереве */
struct node* locate(int x, struct node* t) {
    while (t != NULL && t->key != x) {
        if (x < t->key) {
            t = t->l; /* Идем в левое поддерево */
        } else {
            t = t->r; /* Идем в правое поддерево */
        }
    }
    return t; /* Вернет NULL, если элемент не найден */
}

Визуализация организации дерева поиска

Рассмотрим пример правильно организованного двоичного дерева поиска. Обратите внимание, что для каждого узла выполняется главное правило: левые потомки меньше, правые - больше.