Я ищу эффективный способ слияния двух BST, зная, что элементы в первом дереве все ниже, чем элементы второго. Я видел некоторые методы слияния, но без этой функции, я думаю, это должно упростить алгоритм.Объединение дерева двоичного поиска
Любая идея?
Если деревья не сбалансированы, или результат не должен быть сбалансирован, что это довольно легко:
without loss of generality - let the first BST be smaller (in size) than the second.
1. Find the highest element in the first BST - this is done by following the right son while it is still available. Let the value be x, and the node be v
2. Remove this item (v) from the first tree
3. Create a new Root with value x, let this new root be r
4. set r.left = tree1.root, r.right = tree2.root
(*) Если первый BST больше по размеру, чем второй, просто повторите процесс находим v как наименьший узел во втором дереве.
(*) Сложность O(min{|T1|,|T2|}) наихудший случай (поиск наивысшего элемента, если дерево очень сбалансировано), и O(log(min{|T1|,|T2|})) средний случай - если дерево относительно сбалансировано.
Являются ли деревья сбалансированными * Предполагают ли они оставаться такими? – amit
Деревья не сбалансированы, но не должны быть нитевидными – Antt
Что такое «нитевидные»? Вы имеете в виду, что вы не хотите/допускаете простое размещение одного дерева в другое? Вам нужно сделать что-то вроде балансировки, чтобы полностью объединить их вместе, это то, что вы имеете в виду? –