На этом шаге мы определим сбалансированное (BST) дерево.
Рассмотренные алгоритмы вставки и удаления в бинарном дереве поиска гарантированно порождают бинарное дерево поиска. Однако при этом весьма вероятно, что дерево будет "скошенным" и несбалансированным. Для небольших деревьев это не имеет особого значения, а для больших деревьев такое различие огромно.
H.Вирт [1, с.245] пишет: "Довольно естественно испытывать некоторое недоверие к алгоритму поиска по дереву с включениями... Прежде всего многих программистов беспокоит то, что обычно мы не знаем, каким образом будет расти дерево, и не имеем никакого представления о форме, которую оно примет".
- Определение.
- Сбалансированным деревом назовём дерево, в котором:
- длина пути от любого листа до корня "примерно одинакова";
- дерево имеет минимальное количество уровней, необходимых для данного количества узлов.
- Соглашение.
- В дальнейшем иногда будем называть BST-деревьями (или просто BST) бинарные деревья поиска.
(1) Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с.
На следующем шаге мы рассмотрим ротацию в бинарном дереве поиска.
