39 Динамич типы данных (1006387), страница 2
Текст из файла (страница 2)
В этом двухуровневом дереве мы можем добраться до любого ключа за три доступа к диску. Если бы мы сгруппировали по 100 ключей на узел, то за три доступа к диску мы могли бы найти любой ключ из 1000000. Чтобы сохранить это свойство, нам нужно сохранять сбалансированность дерево во время вставок и удалений. Во время вставки мы исследуем потомка, чтобы определить, можно ли добавить в него узел. Если нет, в дерево добавляется еще один брат, а ключи потомка перераспределяются так, чтобы появилось место для нового узла. Когда мы спускаемся, чтобы вставить ключ, и узел оказывается заполненным, мы рассыпаем корень, у которого появляются новые потомки, так что глубина дерева увеличивается.
Аналогичные действия предпринимаются при удалении - здесь может потребоваться объединить потомков. Этот метод изменения глубины дерева позволяет сохранить сбалансированность дерева.
Необязательно.
Критерий сбалансированности, сформулированный Адельсоном-Вельским и Ландисом:
Дерево называется сбалансированным тогда и только тогда, когда высоты двух поддеревьев каждой из его вершин отличаются не более чем на 1.
В сбалансированном дереве за время, пропорциональное O(log n) даже в худшем случае, можно выполнить следующие операции:
-
Найти вершину с заданным ключом
-
Включить новую вершину с заданным ключом
-
Исключить вершину с заданным ключом
6
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
