• Деревья двоичного поиска. Алгоритмы включения и удаления без балансировки. Оценка числа операций.

Деревом двоичного поиска называется бинарное дерево, для которого выполнены следующие условия:

• множество вершин - подмножество линейно упорядоченного множества
• каждая вершина больше всех вершин из своего левого поддерева
• каждая вершина меньше всех своих вершин из правого поддерева

Оба поддерева также являются двоичными деревьями поиска.

Поиск в дереве двоичного поиска: д – дерево двоичного поиска а – искомое значение пусть х, л, п – корень, левое и правое поддеревья д

если (д -- пустое дерево) то { не нашли } иначе { если (а == х) то нашли иначе если (a < x) то найти а в л иначе найти а в п }

Вставка в дерево двоичного поиска: д – дерево двоичного поиска а – вставляемое значение пусть х, л, п – корень, левое и правое поддеревья д

если (д -- пустое дерево) то { дерево(а, пустое дерево, пустое дерево) } иначе { если (а == х) то ошибка иначе если (a < x) то вставить а в л иначе вставить а в п }

Сложность:

• в среднем $O(log n)$
• в худшем случае $О(n)$

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

Сложность:

• в среднем $O(log n)$
• в худшем случае $О(n)$