Разделить двоичное дерево

Question

Я пытаюсь разбить бинарное дерево поиска в корне на Java. Я понятия не имею, как это сделать. Рекурсивный вызов - вот что меня больше всего смущает. Ниже псевдокод, который мне дали. Когда x больше, чем T (дерево, которое нужно разделить), я собираюсь назвать split (R.key, R.right, L, R)? Я на правильном пути? Это единственная функция в проекте, которая смущает меня. Заранее спасибо.

 void split( int x, bst T, bst L, bst R) /* assuming x is not in T */
 {
    if T is null, make L and R null
    else if x < T.key
      set R = T /* all keys at the root and in right subtree are greater than x */
      recursively split T's left subtree into L and R’s left subtree
         /* some keys in T's left subtree are greater than x, other may be less than x */

    else /* x is greater than T.key */
      set L = T
      recursively split T's right subtree into L's right subtree and R
 }

Answer 1

Важно, чтобы у вас было двоичное упорядоченное дерево, такое, чтобы Left Root, и нет узла в правом поддереве, такого как узел

Это похоже на двудомный поиск; если значение для деления больше, чем ваш текущий корень, вы уверены, что оно больше, чем все узлы в левом поддереве (из-за предыдущего ограничения). Таким образом, чтобы найти, какой из узлов дерева больше, вам нужно только проверить узлы справа. Аналогично, если значение для деления меньше значения root, оно также меньше значений всех узлов правого поддерева, и вы должны выполнить более точную проверку в левом дереве.

Чтобы увидеть это ясно, я предлагаю вам нарисовать это дерево (без пробелов здесь)

8

4 12

3 6 10 14

1 2 5 7 9 11 13 15

, установите несколько значений разделения выборки и отметьте, какие узлы останутся в новом дереве.