2-3-деревья от того, меньше ли К, чем старый ключ, или больше. Если же искомый лист – 3-узел, то мы разделяем его на два: наименьший из трех ключей (двух старых и нового) помещаем в первый лист, наибольший – во второй лист, а средний ключ переносится в узел, родительский по отношению к старому листу (если лист – корень дерева, то для вставки ключа создается новый корень). Заметим, что перемещение среднего ключа в родительский узел может привести к переполнению родительского узла (если он был 3-узлом) и, следовательно, вызвать ряд разделений узлов вдоль цепочки предков листа.
2-3-деревья
8
9
5,9
5,8,9
5
9
8
8
3,8
3,5
9
2,3,5
9
2
5
9
3,8
3,8
9
2
4,5
2
4,5,7
9
2-3-деревья
3,5,8
3,8
9
2
4
7
2
4,5,7
9
5
3
8
2
4
7
9
2-3-деревья
Как и в любом дереве поиска эффективность словарных операций зависит от его высоты. 2-3-дерево высотой h с минимальным количеством ключей представляет собой полное дерево с 2-узлами. Следовательно, для любого 2-3-дерева высотой h с n узлами мы получаем неравенство n ≥ 1 + 2 + … + 2↑h = 2↑(h+1) – 1, следовательно h ≤ log2(n+1) - 1. С другой стороны, 2-3-дерево высотой h с максимальным количеством узлов представляет собой полное дерево, все узла которого – 3-узлы, с двумя ключами и тремя потомками.
2-3-деревья
Следовательно, для любого 2-3-дерева с n узлами n ≤ 2*1+2*3+ …+2*3↑h = 2*(1+3+…+3↑h) = 3↑(h+1)-1, следовательно h ≥ log3(n+1) – 1. Из полученных таким образом верхней и нижней границ высоты h вытекает, что временная эффективность поиска, вставки и удаления как в наихудшем, так и в среднем случае – Θ(log2n).
Пирамиды
Пирамида это бинарное дерево с ключами, назначенные ее узлам (по одному ключу на узел), для которого выполняются два следующих условия. 1. Требование к форме дерева. Бинарное дерево практически полное или просто полное, т.е. все его уровни заполнены, за исключением, возможно, последнего уровня, в котором могут отсутствовать некоторые крайние справа листья. 2. Требование доминирования родительских узлов. Ключ в каждом узле не меньше ключей в его дочерних узлах (условие считается автоматически выполняющимся для всех листьев).
Пирамиды
Пирамиды
Имеется два основных способа построить пирамиду для заданного множества ключей. Первый называется восходящим построением пирамиды (bottom-up heap construction). При этом практически полное бинарное дерево инициализируется путем размещения n ключей в заданном порядке сверху вниз слева направо, а затем дерево «пирамидизируется» следующим образом. Начиная с последнего родительского узла и заканчивая корнем алгоритм проверяет, выполняется ли для рассматриваемого узла требование доминирования родительского узла.
Пирамиды
Если нет, то алгоритм обменивает ключ узла К с наибольшим ключом среди его дочерних узлов и проверяет выполнение требования доминирования родительского ключа К в новой позиции. Этот процесс продолжается до тех пор, пока для ключа К не будет выполнено требование доминирования родительского узла (в конечном итоге это требование будет выполнено, т.к. оно всегда выполняется для ключей в листьях). После завершения «пирамидизации» поддерева, корнем которого является данный родительский узел, алгоритм выполняет те же действия с непосредственным предком этого узла. Алгоритм завершает свою работу после обработки корня дерева.
Пирамиды
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.