Как работает вставка бинарного дерева поиска с помощью рекурсии?

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

bstnode* insert(bstnode* root,int data)
{
    if(root==NULL){
        bstnode* tmp= new bstnode();
        tmp->data=data;
        tmp->left=tmp->right=NULL;
        return tmp;
    }

    if(data<root->data)     
        root->left = insert(root->left, data); 
    else 
        root->right = insert(root->right, data); //can't understand the logic here
    return root; 
}

/* consider following BST with their addresses[]:
              15 [100]
             /  
           10    20 [200]
                   
                   tmp [300]  
*/

По моему мнению root->right = insert(root->right, data); должен хранить адрес вновь созданного узла в root->right, поэтому этот код не должен работать для дерева с высотой>2. Однако он отлично работает для любого числа узлов.
Должно быть, я упустил некоторые важные детали.

предположим, я хочу вставить 25 в BST, то есть вставить (root, 25);
как 25>15:-

я ломаю рекурсивную систему. часть здесь:
root->right = insert(root->right, 25);
или 15->right = insert(15->right,25); Здесь, рекурсивно вызывая его снова, потому что 25>20
insert(root->right, 25) => root->right->right = insert(root->right->right, 25);
или insert(15->right, 25) => 20->right = insert(20->right, 25);

insert(20->right,25) является NULL, поэтому создается новый узел tmp.
insert(20->right,25); возвращает tmp.

теперь разматываем рекурсию.

//20->right = insert(20->right, 25);

Итак,

20->right= 300 (адрес tmp);

//insert(15->right, 25) => 20->right
//and 15->right = insert(15->right,25);

15->right = 20->next;
поэтому 15->right = [300] адрес.
или root->right = [300] адрес.
что не так с моей подходить?

Снова обзор рекурсивных вызовов: 

15->right = insert(15->right,25);
15->right = [20->right = insert(20->right,25)]; //20->right is NULL so creating new node
15->right = [20->right=   300 address of tmp];
15->right = [20->right or 300]
15->right = [300] // but in reality 15->right = [200]
4 3
algorithm data-structures recursion

4 ответа:

Вы забываете, что root - > right - это root - > right адреса, который вы передаете в функцию как root. каждый вызов insert проходит в root - > right или root - >left в зависимости от того, в какую сторону вы проходите.

Это утверждение неверно: 

root->right = root->right->right = tmp;

Как только итерация функции возвращается, она удаляется из стека, поэтому в этом случае у нас есть 3 вызова, я поставлю ваши числа вместо значения указателя.

insert(15->right,25)
insert(20->right,25)

Последний равен нулю, поэтому он создает узел с 25 и возвращает его в вызов insert (20 - >right, 25) и устанавливает 25 как 20 - >right, так что у вас есть дерево, которое выглядит следующим образом

/* consider following BST with their addresses[]:

              20 [200]
               \
                25 [300]  
*/

Затем он возвращает это дерево в вызов insert (15 - >right, 25) и устанавливает эти деревья прямо на дерево, которое мы только что вернули, поэтому мы получаем ваше конечное дерево 

/* consider following BST with their addresses[]:
          15 [100]
         /  \
       30    20 [200]
               \
                25 [300]  
*/

EDIT: давайте посмотрим, смогу ли я прояснить. Давайте еще раз посмотрим на ваше дерево 

/* consider following BST with their addresses[]:
          15 [100]
         /  \
       10    20 [200]
               \
               tmp [300]  
*/

Мы хотим вставить 25, поэтому мы вызываем (снова я буду использовать значение в этом узле дерева, чтобы представьте указатель, который мы проходим) вставить(15, 25)

Это затем вызывает insert on root - >right, который оказывается 20 

insert(20, 25)

Это вызывает insert снова на 20 правом узле Теперь, который оказывается null 

insert(null,25)

Итак, давайте теперь посмотрим на результаты

Insert (null,25) возвращает узел с 25 в нем, а затем удаляется из стека 

 return 25;

Insert (20,25) получает свой возврат узла с 25. он устанавливает право ребенка на 25, который выглядит как это 

 20->right = 25;
 return 20;
Теперь мы возвращаемся к исходному вызову insert (15,25). ему вернули 20. так оно и есть 
15->right = 20;
return 15;
2

Я думаю, что путаница может исходить из двух разных источников для вас. Во-первых, дерево, закомментированное в ваш код, будет невозможно. Во-вторых, новый узел создается только тогда, когда функция передается в нулевом указателе. Только значения меньше 15 могут идти влево. Это будет что-то вроде этого (в зависимости от порядка добавления): 

   15
  /  \
     20
    /  \
       30

Когда вы добавите к этому 25, это закончится следующим образом: 

   15
  /  \
     20
    /  \
        30
       /
      25

Я попытаюсь пройти через код, чтобы объяснить это. Когда добавление 25 к исходному дереву при первом вызове функции первый узел не является нулевым и 25 > 15, так что 

else
{ 
    root->right = insert(root->right, data);
}

Называется. Это вызывает ту же самую функцию вставки рекурсивно, но теперь использует узел 20 в качестве сравнения. Опять же не null, а 25 > 20, поэтому вызовите insert на правом узле, как указано выше. Это снова вызывает рекурсивную функцию, но теперь на 30. 25

1

Обратите внимание, что insert() всегда возвращает root, который был передан ему в качестве аргумента, если только root == NULL. Поэтому нет никакого способа для нового узла, который вы вставляете, чтобы "идти вверх по дереву". То, что происходит в рекурсивном вызове, не имеет значения-вы всегда возвращаете тот же root, который был передан в случае безNULL.

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

Если вы передаете не NULL узел и data < root->data, получите ли вы правильный результат, если вы сделаете root->left = insert(root->left, data) и предположите, что insert() волшебным образом "просто работает" (то есть, что он вставляет data в левое дерево и возвращает корень этого дерева)?

Если логика проверена как для левого, так и для правого случая, вы затем рассматриваете базовый случай: если вам передан узел NULL, Вы вернете правильное одноэлементное дерево?

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

0

В каком-то смысле вы правы. У вас никогда не может быть поддерева (не дерева) высотой >2.

В этом коде у вас никогда не будет root->right->right, потому что, насколько это касается кода, когда вы вызываете root->left = insert(root->left, data);

(локальный) корневой указатель теперь указывает на узел, который вы только что вставили. (локальный) корень указывает на root->left.

Таким образом, вы можете иметь дерево любой высоты (однако локальный корневой указатель указывает на поддерево высоты

0