Составители:
74
1. Поиск вершины Node, которая содержит элемент Item. Если та-
кой вершины нет, то удаление невозможно.
2. Если Node – лист, то удалить из Node элемент Item, иначе заме-
нить элемент Item узла Node на самый левый элемент правого подде-
рева элемента Item (тем самым сохраняется упорядоченность дерева:
аналогично можно заменять элемент Item на самый правый элемент
левого поддерева), Node := вершина, из которой был взят элемент для
замены.
3. Если в Node меньше NumberOfItems/2 элементов (получи-
лась порожняя вершина), то:
– выбрать две соседние вершины Neighbor1 и Neighbor2: одна из
них – Node, вторая – ее левая или правая ближайшие;
– если в Neighbor1 и Neighbor2 в сумме меньше чем
NumberOfItems элементов, то слить вершины Neighbor1 и
Neighbor2 иначе перераспределить элементы между Neighbor1 и
Neighbor2 так, чтобы количество элементов в них не отличалось боль-
ше чем на единицу, Node := родительская вершина Neighbor1 и
Neighbor2.
4. Если Node не корень дерева, то перейти к пункту 3.
5. Если корень дерева пуст, то удалить его. Новым корнем дерева
будет та единственная вершина, на которую осталась ссылка в старом
корне.
Рассмотрим работу алгоритма на примере. Возьмем дерево, получив-
шееся в предыдущем примере после добавления элемента (рис. 22, а).
Будем удалять из этого дерева элемент 10. Сначала надо, двигаясь от
корня, найти вершину дерева, содержащую этот элемент. Он находится
в корне. Теперь поскольку элемент находится не в листовом узле, надо
заменить его, например, на самый левый элемент правого поддерева.
Делаем один шаг вправо и попадаем в корень правого поддерева. Те-
перь пока не достигнем листа, переходим на самого левого потомка.
Таким образом, найдем вершину, из которой позаимствуем элемент
для замены удаленного элемента 10. В найденной вершине возьмем са-
мый левый элемент. Таковым оказывается 11. Произведем замену эле-
мента 10 на 11 и удалим элемент 11 (рис. 22, б).
Теперь проверим вершину, из которой был удален элемент, не стала
ли она порожней. Число элементов в вершине равно нулю. Это меньше
половины размера вершины. Следовательно, вершина порожняя. Вы-
берем две соседние вершины: одна – та, из которой было удалено 11,
