Бинарные деревья поиска (BST)

Термины   20 января 2013  Автор статьи:  

BST — это структурированное дерево, хранящее набор ключей и позволяющие эффективно осуществлять операции поиска ключа, вставку ключа, удаление ключа, а иногда и другие операции. Каждая вершина бинарного дерева поиска хранит в себе ключ, причем все ключи в левом поддереве произвольной вершины строго меньше ключа заданной вершины, аналогично все ключи в правом поддереве строго больше ключа в этой вершине. Двоичное дерево поиска требует O(N) памяти, где N — количество ключей.
Для реализации BST обычно создается класс Node, который содержит значение ключа, а также ссылки на левого и правого сына. Для поиска элемента в бинарных деревьях применяется одна и та же операция find, которая начинается из корня и просто спускается в левое или в правое поддерево, в зависимости от того, больше или меньше текущий ключ ключа, который мы ищем. Таким образом время поиска пропорционально глубине дерева, т.е может варьироваться от logN до N. (дерево равномерно построено или дерево вырождено в цепочку)
Для того, чтобы реализовать простую вставку необходимо просто написать рекурсивную функцию insert, которая будет возвращать корень поддерева, который содержит вставленный элемент. Пишется она не сложнее, чем функция вставки. Более конкретно посмотрите в интересующей вас реализации. Но такой способ вставки не гарантирует того, что наше дерево не выродится в линию, поэтому для этого придется придумать более хитрые условия, которые помогут поддерживать нужную высоту дерева. Очевидно, что эту условия будут реализованы только в методах вставки и удаления, а операция поиска останется неизменной.
Таким образом, двоичное дерево поиска — это такое дерево, которое содержит удовлетворяющие условию значение ключа строго большое значения любого ключа в левом поддереве и строго меньшее в правом. С помощью простой рекурсивной процедуры в дереве поиска можно найти элемент за время пропорциональное высоте дерева, очевидно, что высота дерева из m элементов не меньше чем O(logm). С другой стороны простой обход дерева позволяет выписать его ключи в порядке возрастания, следовательно, если взять массив из N элементов и последовательно добавить в пустое дерево поиска, а затем обойти дерево и выписать элементы, то получится алгоритм сортировки, который не может работать быстрее чем O(NlogN). Таким образом вставка работает не быстрее чем logN. Для того, чтобы поиск и вставка выполнялись за logN к дереву добавляют различные свойства, который гарантируют высоту дерева logN и позволяют реализовать операции удалении и вставки за O(logN).

Бинарным деревьям поиска на Java

Научиться программировать

  • на Delphi

  • на Java

  • на C++