Разбить 2-3 дерева на меньшее и большее заданное значение X

Question

Мне нужно написать функцию, которая получает ключ x и разделяет 2-3 дерева на 2 2-3 дерева. В первом дереве есть все узлы, которые больше х, а во втором меньше. Мне нужно сделать это со сложностью O (logn) . заранее спасибо за любую идею.

изм Я думал о поиске ключа х в дереве. И после того, как разделить его два поддеревья (больше или меньше, если они существуют) на 2 дерева, и после начать подниматься и каждый раз проверять поддеревья, которые я еще не проверял, и присоединяться к одному из деревьев. Моя проблема в том, что все листья должны быть на одном уровне.

Answer 1

Если вы переместитесь от корня к своему ключу и разделите каждый узел так, чтобы один указывал на узлы, большие, чем ключ, а другой на остальные, а затем делал более крупный узел частью вашего более крупного дерева, скажем, имеяКрайний левый узел на один уровень выше его (не чините дерево, сделайте это в конце), пока не дойдете до ключа, вы получите свои деревья.Затем вам просто нужно исправить оба дерева на пути, который вы использовали (обратите внимание, что один и тот же путь существует на обоих деревьях).

Answer 2

Если вы уже охватили 2-3-4 дерева в лекции, вот подсказка: посмотрите, можете ли вы применить тот же алгоритм вставки для 2-3 деревьев.В частности, сделать вставки всегда начинаются с листа, а затем соответствующим образом реструктурировать дерево.Когда закончите, определите сложность алгоритма, который вы получили.