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

Свести бинарное дерево к связанному списку

Первая проблема, которую я хочу рассмотреть, заключается в следующем:

Есть решения этой проблемы, которые мы считаем «правильными», и решения, которые мы считаем «неправильными». Под неправильным я подразумеваю игнорирование парадигм древовидных структур данных и выбор более интуитивного, но менее эффективного решения. Я продемонстрирую один ниже, который выглядит следующим образом:

  1. завершить предварительный обход дерева (это порядок, в котором заканчиваются узлы) и сохранить значения каждого узла
  2. перебрать сохраненные значения для обхода дерева в предварительном порядке, используя их для создания плоского связанного списка.
void flatten(TreeNode* root){
     if(root){
          vector<int> node_values;
          preorder(root, node_values);
          root->left = null;
          curr = root;
          for(int i = 1; i < values.size(); i++){
               curr->right = new TreeNode(values[i]);
               curr = curr->right;
          }
     }
}
void preorder(TreeNode* curr, vector<int>& values){
     if(curr){
          values.push_back(curr->val);
          preorder(curr->left, values);
          preorder(curr->right, values);
     }
}

Хотя это решение никоим образом не является вопиющим (в зависимости от ваших стандартов), оно, безусловно, является неоптимальным решением по множеству причин:

  1. он не может определить объединяющее условие для узлов в дереве, что обычно имеет первостепенное значение для решения проблем дерева.
  2. Требуется дополнительное хранилище для отслеживания значений узлов в предварительном порядке, а также ненужного обхода всего дерева только для того, чтобы получить этот порядок.
  3. требует создания новых узлов для всего дерева, кроме корня

Все проблемы с этим решением связаны с невозможностью идентифицировать какой-либо рекурсивный шаблон для каждого узла, что имеет решающее значение для решения большинства проблем с деревьями, давайте попробуем исправить это, углубившись в эту проблему.

Первое, на что я смотрю, — это то, как узлы изменяются по отношению друг к другу, от бинарного дерева до связного списка. Прежде всего, мы замечаем, что для каждого отдельного узла в двоичном дереве его следующим указателем в связанном списке (или его правым дочерним элементом) является узел, который ранее был его левым дочерним элементом. Это тип универсального сходства между узлами, который обычно является критически важным для решения проблемы. Кроме того, для каждого узла его правый дочерний элемент в двоичном дереве становится правым дочерним элементом всего его левого поддерева в двоичном дереве при сведении к связанному списку. Этого должно быть достаточно для понимания сходства между узлами для реализации рекурсивного решения, которое будет выглядеть следующим образом:

  1. сохранить указатель на левое и правое поддеревья текущего узла и рекурсивно вызывать функцию как для левого, так и для правого поддеревьев
  2. установить правый дочерний элемент текущего узла в качестве указателя на левое поддерево
  3. теперь, когда исходное левое поддерево текущего узла теперь является правым поддеревом, перейдите к самому правому листовому узлу этого поддерева и установите его правый дочерний элемент как старое правое поддерево текущего узла.
void flatten(TreeNode* root){
   if(root){
        flatten(root->left);
        flatten(root->right);
        TreeNode* right = root->right;
        root->right = root->left;
        root->left = NULL;
        TreeNode* curr = root;
        while(curr->right){
                curr = curr->right;
        }
        curr->right = right;
    }
}

Вуаля! Вот и все! Это решение не только ввергает общество любителей бинарных деревьев в состояние эйфории, но и устраняет проблемы необходимости вспомогательного хранилища и создания новых узлов вместо реорганизации существующего дерева. Хотя производительность рекурсивной реализации была всего на ~1 миллисекунду выше, улучшение использования памяти было значительным.

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

определить, сбалансировано ли бинарное дерево

Определение сбалансированности бинарного дерева — это проблема, которую на самом деле не следует решать никаким другим способом, кроме рекурсивного.

Мы можем быстро понять, почему решение лучше всего решать рекурсивно, поскольку среди всех узлов в дереве есть объединяющий принцип. Чтобы все бинарное дерево было сбалансированным, поддерево с корнем в каждом узле дерева также должно быть сбалансировано, поэтому любые проверки, применяемые к корню дерева, должны применяться повсеместно.

когда для узлов через дерево наблюдается объединяющее условие, подобное описанному выше, мы обычно можем вывести из этого методологию решения проблемы. В этом случае сбалансированное двоичное дерево — это дерево, в котором поддерево с корнем в каждом узле дерева имеет левых и правых дочерних элементов с разницей в высоте не более 1, см. примеры сбалансированного и несбалансированного дерева ниже.

Мы можем определить высоту от определенного узла n как количество ребер между n и самым глубоким листовым узлом в дереве с корнем n. Исходя из этого, мы можем вывести следующую стратегию для этой проблемы:

  1. для данного узла n проверьте, является ли он нулевым или его дочерние элементы равны нулю, в любом случае дерево с корнем в n сбалансировано.
  2. если n не равно нулю и имеет хотя бы 1 дочерний элемент, следующим шагом будет вычисление высоты поддеревьев с корнями в дочерних элементах n.
  3. как только высота поддеревьев была вычислена, мы проверяем, является ли разница в высоте ≤ 1, если это не так, мы возвращаем false. Если высоты находятся в пределах 1 друг от друга, мы рекурсивно вызываем нашу функцию баланса для двух поддеревьев, возвращая истину, если оба этих поддерева сбалансированы, и ложь в противном случае.

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

int height(TreeNode* root){
   if(root){
        return 1 + max(height(root->left), height(root->right));
   }
   return 0;
}
bool isBalanced(TreeNode* root) {
   if(!root){
        return true;
   }
   if(!root->left && !root->right){
        return true;
   }
        
   int lHeight = height(root->left);
   int rHeight = height(root->right);
   if(abs(lHeight - rHeight) <= 1){
        return isBalanced(root->right) && isBalanced(root->left);
   }
   return false;
}

Это так просто!

Я буду делать этот пост довольно коротким по сравнению с другими, мне нечего было сказать, и в основном я хотел написать быстрый пост, восхищающийся элегантностью и простотой алгоритмов бинарного дерева. Спасибо за чтение!