Можем ли мы построить BST из обхода предзаказа, просто вставив элементы в обходе предзаказа последовательно в пустое дерево?

Question

Учитывая прохождение предварительного заказа BST. Я должен построить BST.Могу ли я построить BST из прохождения предварительного заказа, просто создав пустой BST и вставив элементы в обход предварительного заказа один за другим, начиная с первого элемента и заканчивая последним элементом, в пустой BST?

Например,рассмотрим следующий BST: -

    10
   /   \
  5     40
 /  \      \
1    7      50

Его обход по предварительному заказу:

10 5 1 7 40 50

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

(empty tree)

вставьте первый элемент обхода предварительного заказа: 10

   10

вставьте второй элемент обхода предварительного заказа: 5

   10
   /
  5

аналогично,

     10       
   / 
  5  
 /  
1   

     10
   /   
  5    
 /  \  
1    7 

     10
   /   \
  5     40
 /  \ 
1    7

     10
   /   \
  5     40
 /  \      \
1    7      50

Здесь я построил точный BST, просто вставив элементы вПредзаказ обход по одному в пустое дерево.Будет ли этот алгоритм работать во всех случаях? Есть ли случаи, когда этот алгоритм не будет работать?

void insertIntoTree(struct* Node,int val)
{
   if(Node == NULL)
   {
       Node = createNewNode(val);
       return;
   }
   if(val < Node->val)
      insertIntoTree(Node->left,val);
   else
      insertIntoTree(Node->right,val);

}
int main()
{
  int preorderlist[] = { 10,5,1,7,40,50};

  for(int i=0;i <= preorderlist.size();i++)
  {
     insertIntoTree(TreeRoot,preorderlist[i]);
  }

}

Answer 1

Ваш код будет работать, но он неэффективен. Вы не используете свойство предварительного заказа массива. Фактически, ваш код строит BST из общего массива. Чтобы улучшить свой алгоритм, вы можете построить дерево рекурсивно, сохранив minRange и maxRange в каждом узле. Если следующий элемент находится за пределами диапазона текущего узла, вернитесь обратно к родительскому узлу.

EDIT: Вы получите то же самое дерево, но сложность будет O (N * logN), если исходное дерево было сбалансированным, и O (N ^ 2), если это не так.

Я не хочу писать код для вас, но я попытаюсь объяснить мой алгоритм лучше: Держите указатель на последний узел, который вы вставили. Также для каждого узла сохраняют диапазон поддерева. При вставке элемента начните с указателя, который вы сохранили. если новый узел находится в диапазоне, вставьте его как дочерний и обновите указатель. если он не находится в диапазоне, переместите указатель к его родителю и попытайтесь вставить туда. Чтобы обновить диапазон: если вы вставляете новый узел в качестве левого потомка, установите для его maxRange его родительское значение. и соответственно установить minRange для правильного ребенка. Сложность будет O (N) для всех случаев.