При вставке узла помните следующее правило: узлы будут добавляться только в виде листьев в дерево. Предположим, у нас есть следующее дерево.
Если мы посмотрим на это дерево, вы заметите, что в каждом узле значения в левом поддереве меньше, чем значение узла, а значения в правом поддереве больше, чем значение узла.
Допустим, мы хотели вставить значение 35. Можете ли вы предсказать, где оно будет в дереве? Давайте пройдемся по нему и посмотрим, чем он закончится.
Мы начинаем со сравнения 35 со значением корневого узла, 20. Поскольку 35 больше, чем значение в корневом узле, мы переходим в правое поддерево.
Затем мы сравниваем 35 с 40. Поскольку 35 меньше 40, мы переходим к его левому поддереву.
Затем мы сравниваем 35 с 33. Поскольку 35 больше 33, мы пытаемся перейти в правое поддерево узла 33.
Поскольку в узле 33 нет правого поддерева, мы вставляем туда узел 35.
Довольно простая логика. Вот и все, что касается вставки узла. Постарайтесь не усложнять его, и вы быстро поймете, что большинство алгоритмов просты.
Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает этот алгоритм и многое другое.
