在Haskell中，如何生成一個完美平衡的二叉搜索樹？

該函數應該接受一個列表xs並構造一個平衡二叉搜索樹，其中包含與xs完全相同的一組元素。在Haskell中，如何生成一個完美平衡的二叉搜索樹？

結果應該是這樣的：（如果列表是[1,2,3,4,5,6,7,8]）

節點（節點（節點（節點1空空） 2空）4（節點空4空））5（節點（節點空6空）7（節點空8空））

也就是說樹應該是這樣的：

而不是這個：

有人能告訴我該怎麼做？我發現我可以做第二棵不完全平衡的樹，但不知道如何做第一棵樹。

我很感激任何幫助！提前謝謝！

來源

2013-09-30 Zip

使用Data.Tree.AVL（或其他一些）http://hackage.haskell.org/package/AvlTree-4.2/docs/Data-Tree-AVL.html – josejuan

@josejuan：我認爲OP想找到最理想的，完美的ba藍色的樹。自我平衡只能保證他們的身高至多是一個恆定的倍數。 – hugomg

如果你已經有一個長度排序的列表（x^2 - 1），你可以使用這個不錯的[遞歸算法]（http://brandon.si/code/building-a-tree-from-an-ordered-list /） – jberryman

對輸入列表進行排序。現在創建一棵樹，其根節點是列表的中間元素，其左右子樹是通過將該過程分別應用於中心左側和右側的子列表而生成的子樹。

在Haskell：

buildBalanced [] = Empty 
buildBalanced elts = Node (buildBalanced $ take half elts) 
          (elts !! half) 
          (buildBalanced $ drop (half+1) elts) 
    where half = length elts `quot` 2 

main = putStrLn $ show $ buildBalanced [1,2,3,4,5,6,7,8] 
-- prints Node (Node (Node (Node Empty 1 Empty) 2 Empty) 3 (Node Empty 4 Empty)) 5 (Node (Node Empty 6 Empty) 7 (Node Empty 8 Empty))

來源

2013-09-30 09:06:52 jacobm

它完美的工作！謝謝你的幫助！ – Zip

如果樹的頂部一定是中間元素：

mkBalanced [] = Empty 
mkBalanced xs = Node mid (mkBalanced half0) (mkBalanced half1) 
    where (half0, half') = splitAt ((length xs `div` 2) - 1) xs 
      half1 = tail half' 
      mid = head half'

如果不是：

mkBalanced [] = Empty 
mkBalanced (x:xs) = Node x (mkBalanced half0) (mkBalanced half1) 
    where (half0, half1) = splitAt (length xs `div` 2) xs

來源

2013-10-01 22:56:47 user2407038

在Haskell中，如何生成一個完美平衡的二叉搜索樹？

回答

相關問題