Преобразование отсортированного двусвязного списка в BST - PullRequest
Новая
       13

Преобразование отсортированного двусвязного списка в BST

0 голосов
/ 24 октября 2011

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

Я думал сделать это так же, как преобразовать массив в сбалансированный BST.Найдите центр и затем рекурсивно преобразуйте левую часть и правую часть DLL.Например,

1 2 3 4 5 => 1 2 (3) 4 5 => 

     3
   /   \
  2     4
 /       \
1         5

Это приводит к рецидиву T (n) = 2T (n / 2) + O (n),O (n) для нахождения центра.Следовательно, временная сложность равна O (nlogn).Мне было интересно, если есть алгоритм, который делает это в O (N).

Ответы [ 3 ]

3 голосов
/ 24 октября 2011

Да, есть решение O (n). Обратите внимание, что в порядке обхода в BST итерирует элементы в нужном порядке, поэтому просто выполните обход по порядку в первоначально пустом дереве размера n и заполните его с элементами в списке. [I-й элемент, который вы вставляете в дерево при обходе, это i-й элемент в списке].
В конце ответа я добавил, как создать пустое сбалансированное дерево в O(n).

псевдокод : [предполагается | список | == | дерево |] 

global current <- null
fillTree(tree,list):
  current <- list.head
  fillTree(tree)
fillTree(tree):
  if tree == null:
     return
  fillTree(tree.left)
  //in-order traversal: we set the value after setting left, and before calling right
  tree.val <- current.val
  current <- current.next
  fillTree(tree.right)

Сложность тривиальна O(n), поскольку для каждой вершины дерева существует ровно одна итерация, и каждая итерация равна O (1).

EDIT:
Вы можете создать пустое сбалансированное дерево , просто создав пустое полное дерево (*), оно сбалансировано и построено как O (n).

(*) Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен.

1 голос
/ 27 июля 2015

почти на 4 года позже.но здесь приходит мое функциональное решение.Ниже приведен мой код на Haskell, сложность также O(n): 

import Data.List hiding (insert)

data Color = R | B deriving Show
data RBTree a = RBEmpty | RBTree { color :: Color
                                 , ltree :: RBTree a
                                 , nod   :: a
                                 , rtree :: RBTree a } deriving Show

fromOrdList ::  Ord e => [e] -> RBTree e
fromOrdList [] = empty
fromOrdList lst = 
    let (res, _) = _fol lst $ length lst
    in res
    where _fol :: (Ord e, Integral a) => [e] -> a -> (RBTree e, Maybe (e, [e]))
          _fol l 0            = (empty, uncons l)
          _fol (h:l) 1        = (RBTree B empty h empty, uncons l)
          _fol (h1:h2:l) 2    = (RBTree B (RBTree R empty h1 empty) h2 empty, uncons l)
          _fol (h1:h2:h3:l) 3 = (RBTree B (RBTree R empty h1 empty) h2 (RBTree R empty h3 empty), uncons l)
          _fol l n            =
            let mid                  = n `div` 2
                (ltr, Just (rt, tl)) = _fol l mid
                (rtr, mayremain)     = _fol tl (n - 1 - mid)
in (RBTree B ltr rt rtr, mayremain)

, что на самом деле является частью моей личной практики: https://github.com/HuStmpHrrr/PFDSPractise/blob/master/src/Tree/RBTree.hs#L97

0 голосов
/ 24 октября 2011

Посмотрите на мою реализацию рекурсивной вставки (c #).Есть T (n) = 2 * T (n / 2) + O (1).O (1) для нахождения центра: (l + r) / 2.Таким образом, сложность O (n) 

public class Tree<T>
  {
    public class TreeNode<T>
    {
      public TreeNode<T> Right { get; set; }
      public TreeNode<T> Left { get; set; }
      public T Data { get; set; }
    }

    public Tree()
    {
      Root = new TreeNode<T>();
    }  

    public TreeNode<T> Root { get; set; }

    private void InsertSortedListRec(IList<T> items, TreeNode<T> curNode, int l, int r)
    {
      var mid = (l + r)/2;
      curNode.Data = items[mid];

      if (mid - 1 >= l)
      {
        curNode.Left = new TreeNode<T>();
        InsertSortedListRec(items, curNode.Left, l, mid - 1);
      }

      if (mid + 1 <= r)
      {
        curNode.Right = new TreeNode<T>();
        InsertSortedListRec(items, curNode.Right, mid + 1, r);
      }
  }

    public void InsertSortedList(IList<T> items)
    {
      InsertSortedListRec(items, Root, 0, items.Count - 1);
    }
  }

Я предполагаю, что у нас есть индексированный массив (мы можем преобразовать связанный список в массив O (n))

...