Случайные деревья

Случайные деревья поиска представляют собой упорядоченные бинарные деревья поиска, при создании которых элементы (их ключи) вставляются в случайном порядке.

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

При поступлении элементов в случайном порядке получаем дерево с минимальной высотой h (рис. 2 А), при этом минимизируется время поиска элемента в дереве, которое пропорционально . При поступлении элементов в упорядоченном виде (рис. 2 В) или в порядке с единичными сериями монотонности (рис. 2 С) происходит построение вырожденных деревьев поиска (оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет .

A

B

С

Рис. 2. Случайные деревья поиска

Дата добавления: 2014-01-04