0

ソートされた二重連結リストをバランスの取れた二分探索木に変換するにはどうすればよいですか?

アレイをバランスの取れた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）でこれを行うアルゴリズムがあるかどうか疑問に思っていました。

4

3 に答える 3

3

はい、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)ツリーの頂点ごとに正確に1つの反復があり、各反復はO（1）であるため、複雑さは自明です。

編集：空の 完全なツリー（*）を構築するだけで、空のバランスの取れたツリーを作成
できます。それはバランスが取れており、構築するとO（n）になります。

（*）完全な二分木は、おそらく最後を除くすべてのレベルが完全に満たされている二分木です。

于 2011-10-24T11:02:28.550 に答える
2

約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

于 2015-07-27T12:33:18.443 に答える
0

私の再帰的挿入 (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）に変換できます）

于 2011-10-24T11:07:23.783 に答える