將已排序的雙向鏈表轉換爲BST

如何將已排序的雙向鏈表轉換爲平衡二叉搜索樹。將已排序的雙向鏈表轉換爲BST

我正在考慮以與將數組轉換爲平衡BST相同的方式來執行此操作。找到中心，然後遞歸轉換DLL的左側部分和右側部分。例如，

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

這是導致復發T（N）= 2T（N/2）+ O（n）中。 O（n）用於查找中心。因此時間複雜度爲O（nlogn）。我想知道是否有一個算法在O（n）中做到這一點。

來源

2011-10-24 shreyasva

是的，有O（n）的解決方案。請注意，BST上的in-order traversal正在按照所需順序迭代元素，因此只需執行的索引遍歷初始空樹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)，由於存在excactly爲樹的每個頂點一次迭代，並且每次迭代是O（1）。

編輯：
可以創建一個空的平衡樹，只需建立一個空的complete tree（*），它是平衡和構建它爲O（n）。

（*）一個完整的二叉樹是一個二叉樹，其中除了最後一個以外的每個關卡都被完全填充。

來源

2011-10-24 11:02:28 amit

我不是BST轉換爲DLL。其他方式 – shreyasva

@shreyasva：請閱讀答案，它正在將已排序的列表轉換爲BST。它在遍歷樹時正在做它。 – amit

@shreyasva：我編輯了答案並添加了'如何在'O（n）''中構建一個空的平衡樹？如果這是我的答案的問題。 – amit

看看我的遞歸插入（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-24 11:07:23

近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-27 12:33:18 HuStmpHrrr

將已排序的雙向鏈表轉換爲BST

回答

相關問題