Пример удаления различных узлов из сбалансированного дерева

Узел, который необходимо удалить, обозначен двойной рамкой. Если задано сбалансированное дерево (рис.6.35. a), то последовательное удаление узлов с ключами 4,8,6,5,2,1 и 7 дает деревья (рис.6.35 b...h).

Удаление ключа 4 само по себе просто, т.к. он представляет собой терминальный узел. Однако при этом появляется несбалансированность в узле 3. Его балансировка требует однократного левого поворота налево. Балансировка вновь становится необходимой после удаления узла 6. На этот раз правое поддерево корня балансируется однократным поворотом направо.

Удаление узла 2, хотя само по себе просто, так как он имеет только одного потомка, вызывает сложный двукратный поворот направо и налево.

И четвертый случай: двукратный поворот налево и направо вызывается удалением узла 7, который прежде заменяется самым правым элементом левого поддерева, т.е. узлом с ключом 3.

Рис.6.36 а..h Удаление узлов из сбалансированого дерева.

Удаление элемента из сбалансированного дерева удобнее разбить на 4 отдельных процедуры:

· 1. Delete - осуществляет рекурсивный поиск по дереву удаляемого элемента, вызывает процедуры удаления и балансировки.

· 2. Del - осуществляет собственно удаление элемента и вызов при необходимости процедуры балансировки.

· 3. Balance_L и Balance_R - производят балансировку и коррекцию показателей сбалансированности после удаления элемента из левого (правого) поддерева.