如何将已排序的双向链表转换为平衡二叉搜索树。将已排序的双向链表转换为BST
我正在考虑以与将数组转换为平衡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)中做到这一点。
如何将已排序的双向链表转换为平衡二叉搜索树。将已排序的双向链表转换为BST
我正在考虑以与将数组转换为平衡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)中做到这一点。
是的,有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)。
(*)一个完整的二叉树是一个二叉树,其中除了最后一个以外的每个关卡都被完全填充。
看看我的递归插入(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))
近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
我不是BST转换为DLL。其他方式 – shreyasva
@shreyasva:请阅读答案,它正在将已排序的列表转换为BST。它在遍历树时正在做它。 – amit
@shreyasva:我编辑了答案并添加了'如何在'O(n)''中构建一个空的平衡树?如果这是我的答案的问题。 – amit