Создать сбалансированное бинарное дерево поиска из отсортированного связанного списка - PullRequest
Новая
       27

Создать сбалансированное бинарное дерево поиска из отсортированного связанного списка

20 голосов
/ 21 ноября 2010

Какой лучший способ создать сбалансированное двоичное дерево поиска из отсортированного односвязного списка?

Ответы [ 11 ]

0 голосов
/ 22 ноября 2010

Это псевдорекурсивный алгоритм, который я предложу. 


createTree(treenode *root, linknode *start, linknode *end)
{
   if(start == end or start = end->next)
   {
      return; 
   } 
   ptrsingle=start;
   ptrdouble=start;
   while(ptrdouble != end and ptrdouble->next !=end)
   {
    ptrsignle=ptrsingle->next;
    ptrdouble=ptrdouble->next->next;
   }
   //ptrsignle will now be at the middle element. 
   treenode cur_node=Allocatememory;
   cur_node->data = ptrsingle->data;
   if(root = null)
       {
           root = cur_node; 
       }
   else
      {
         if(cur_node->data (less than) root->data)
          root->left=cur_node
         else
           root->right=cur_node
      }
   createTree(cur_node, start, ptrSingle);
   createTree(cur_node, ptrSingle, End); 
}

Root = ноль; Начальным вызовом будет createtree (Root, list, null);

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

Время выполнения будет o (nlogn). Дополнительное пространство будет o (logn). Не эффективное решение для реальной ситуации, когда у вас может быть дерево R-B, которое гарантирует вставку nlogn. Но достаточно хорош для интервью.

Страница:
...