Билеты

	16. 2–3–дерево поиска. Алгоритм вставки и удаления элементов в 2–3–дереве. Эффективность операций в 2–3–дереве. low2 low3   Предложены Хопкрофтом в 1973 г. Соответствует полному идеально сбалансированному BST-дереву (все пути от корня до листьев одинаковы), если все его узлы являются 2-узлами. В этом случае его высота равна log2n. С другой стороны, если все узлы в 2-3-дереве – 3-узлы, то высота равна log3n. Таким образом, длина прохода от корня дерева к листьям с элементами и, следовательно, трудоемкость операций лежит в пределах от О(log3n) до О(log2n). Точка роста дерева – корень. Состоит из листьев (для данных, имеют сыновей) и внутренних узлов. Для организации поиска элементов внутренние узлы дерева содержат дубликаты наименьшего ключа элемента во 2-ом поддереве и наим. ключа в 3-ем (если у узла есть 3-ий сын). Эти ключи служат границами поиска нужного листа с заданным ключом. Поиск начинается с корня. Если ключ меньше, чем минимальный элемент у второго сына (low2), то выбирается первый сын. Если узел имеет двух сыновей и ключ > low2, то выбирается второй сын. Если ключ > low2, но нет третьего сына, тот выбирается второй сын. Если есть третий сын и ключ < low3, то выбирается второй сын. Если есть третий сын и ключ ³ low3, то выбирается третий сын. Таким образом, если заданный ключ = ключу в листе, то данные найдены.	Вставка. T23_Insert(root, k,data)+Insert1(root, lt,&tdown,&ldown). T23_Insert(t,x,tup,lup). Включение нового элемента начинается так же, как и процесс поиска. Пусть мы находимся в некотором внутреннем узле x, чьи сыновья – листья и не содержат элемента с заданным ключом k. Если узел содержит двух сыновей, то новый элемент подключается к этому узлу в качестве третьего сына. Новый элемент помещается так, чтобы не нарушить упорядоченность сыновей. После этого корректируются значения минимальных ключей в узле x. Если после вставки лист с новым элементом становится четвертым сыном, то родительский узел расщепляется на два 2-узла. В свою очередь, новый внутренний узел, получившийся в результат расщепления, может вызвать следующего верхнего родительского узла, также имеющего трех сыновей. Процесс расщепления может достигнуть корня и привести к созданию нового корня.
Удаление. T23_Delete (root, k). Операция удаления может привести к тому, что у родительского узла останется один сын. Это может вызвать слияние родительского узла с соседним внутренним узлом. Процесс слияния также может достичь корня и вызвать его замену на узел, образованный в результате слияния двух его сыновей. 1) Если при удалении узла k у родителя (узла t) останется один сын и родитель является корнем, то новым корнем становится его единственный сын старого корня. 2) Если t не является корнем, то проверяются его братья. 3) Если у какого-либо брата есть 3 сына, то узлу t передается один из сыновей брата. Брат и узел t становятся 2-узлами. 4) Если у братьев нет трех сыновей, то единственный сын узла t передается брату. Брат становится 3-узлом, узел t уничтожается. В этом случае у родителя узла t удаляется сын t и ситуация повторяется для родителя узла t. При создании или удалении нового корня одновременно изменяется длина всех путей от корня к листьям и 2-3 дерево остается идеально сбалансированным.