А какие нужны переменные для взаимодействия с бинарным деревом поиска?

Чтобы ответить на этот вопрос, давайте посмотрим на среднестатистическое бинарное дерево поиска.

Используя связи, есть возможность добраться до любой вершины дерева, начав движения от корня. Рассмотрим траекторию движения от корня до узла с ключом $41$.

💡 Траектория имеет такую форму: влево — вправо — вправо — влево.

Поэтому для всех операций необходимо иметь указатель на корень дерева, то есть на самый верхний элемент ( на рисунках выше ключом корня является число $55$ ). Данный элемент является предком (прямым или косвенным) для всех узлов двоичного дерева поиска.

Поэтому в программном коде придется добавить переменную-указатель на вершину двоичного дерева поиска:

Напомню, что из себя представляет структура Node:

То есть переменная-указатель root — это необходимая переменная для любой обработки поискового дерева, но для ряда вспомогательных операций одной переменной root будет явно недостаточно.

Например, если будет запущен поиск/удаление узла бинарного дерева по ключу, то помимо указателя на вершину дерева необходимо еще передать переменную, которая выражает ключевое значение искомого/удаляемого узла .