樹木只有

Question

幾年前在葉子值，一個C＃的過程中，我學會了寫字，看上去或多或少像這樣的二叉樹：

data Tree a = Branch a (Tree a) (Tree a) | Leaf 

我看到它的好處，它有它在分支上的值，允許快速和容易地查找和插入值，因爲它會在每個分支的根部一直向下遇到一個值，直到它碰到一個葉子，這個值沒有任何價值。

自從我開始學習Haskell，但是，我已經看到了很多樹的例子：

data Tree a = Branch (Tree a) (Tree a) | Leaf a 

這個定義令我困惑。我看不出有上的元素數據不分支，因爲它最終會導致樹看起來像這樣的用處：

這對我來說，好像一個設計不佳的替代品。這也讓我懷疑它的查找時間，因爲它無法評估哪個分支去尋找它正在尋找的值;而是需要通過每個節點來找到它正在尋找的內容。

那麼，誰能介紹一下爲什麼第二個版本（葉子上的值）在Haskell中比第一個版本更普遍？

Answer 1

我認爲這取決於您想要建模的內容以及如何對它進行建模。

一棵樹的內部節點存儲值和葉子只是葉子本質上是一個標準的二叉樹（每棵樹的樹爲NULL，你基本上有一個命令式的二叉樹）。如果值按排序順序存儲，則您現在有一個二叉搜索樹。以這種方式存儲數據有許多具體的優點，其中大部分優勢都是從命令式設置直接轉移過來的。

葉子存儲數據和內部節點僅用於結構的樹木有其優點。例如，紅色/黑色樹支持稱爲split和join的兩項強大操作，這些操作在某些情況下具有優勢。 split將輸入密鑰作爲輸入，然後破壞性地修改該樹以生成兩棵樹，其中一棵樹包含小於指定輸入鍵的所有鍵以及一個包含其餘鍵的鍵。從某種意義上說，join是相反的：它需要兩棵樹，一棵樹的值都小於另一棵樹的值，然後將它們融合成一棵樹。這些操作在大多數紅/黑樹上特別難以實現，但是如果所有數據僅存儲在樹葉中而不是存儲在內部節點中，則這些操作要簡單得多。 This paper detailing an imperative implementation of red/black trees提到紅色/黑色樹的一些較舊的實現使用這種方法就是出於這個原因。

作爲將密鑰存儲在樹葉中的另一個潛在優勢，假設您要實現將兩個列表連接在一起的連接操作。如果葉片中沒有數據，這很簡單

concat first second = Branch first second 

這是可行的，因爲沒有數據存儲在這些節點中。如果數據存儲在樹葉中，則需要以某種方式將密鑰從其中一個樹葉移動到新的並置節點，這需要更多時間並且更難處理。

最後，在某些情況下，您可能希望將數據存儲在樹葉中，因爲葉子與內部節點根本不同。例如，考慮一個分析樹，其中葉子存儲來自解析的特定終端，內部節點存儲生產中的所有非終端。在這種情況下，實際上有兩種不同類型的節點，因此將任意數據存儲在內部節點中是沒有意義的。

希望這會有所幫助！

Answer 2

更多的是更好更差更多。我會解釋幾個基本的考慮事項，以說明爲什麼你的直覺失敗。然而，總的想法是，不同的數據結構需要不同的東西。

空葉節點在某些情況下實際上可能是一個空間（因此也是時間）問題。如果一個節點由一些信息和兩個指向它的子節點的指針表示，那麼每個節點的子節點都是葉節點，最終會有兩個空指針。這是每個葉節點的兩個機器字，它可以增加相當多的空間。有些結構通過確保每片葉片至少保存一條信息來證明其存在，從而避免了這種情況。在某些情況下（例如ropes），每個葉子可能具有相當大且密集的有效負載。

使內部節點變大（通過在其中存儲信息）使修改樹變得更加昂貴。在平衡樹中更改葉通常會強制您爲O(log n)內部節點分配替換。如果其中每一個都較大，那麼您只是分配了更多空間並花費額外時間來複制更多單詞。內部節點的額外大小還意味着您可以將較少的樹結構裝入CPU高速緩存中。

Answer 3

您描述了一棵樹上的葉子數據爲「設計不佳的替代方案」。

我同意這可以作爲一個列表的替代，但它不一定設計得很差！考慮數據類型

data Tree t = Leaf t | Branch (Tree t) (Tree t) 

您可以定義cons和snoc（追加到結束列表）操作 - 爲O

cons :: t -> Tree t -> Tree t 
cons t (Leaf s)  = Branch (Leaf t) (Leaf s) 
cons t (Branch l r) = Branch (cons t l) r 

snoc :: Tree t -> t -> Tree t 
snoc (Leaf s)  t = Branch (Leaf s) (Leaf t) 
snoc (Branch l r) t = Branch l (snoc r t) 

這些運行（大致平衡名單）（log n）的時間，其中n是列表的長度。這與標準鏈接列表形成對比，標準鏈接列表具有O（1）cons和O（n）snoc操作。您還可以定義一個固定時間append（如templatetypedef的答案）

append :: Tree t -> Tree t -> Tree t 
append l r = Branch l r 

是O（1）任何大小的兩個列表，而標準表是O（n），其中n是的長度左邊的論點。

在實踐中，你會想定義這些函數稍微更智能的版本，這些函數試圖保持樹的平衡。要做到這一點，在分支上有一些額外的信息通常是有用的，這可以通過具有多種分支來完成（如具有「紅色」和「黑色」節點的紅黑樹）或明確地包括附加數據在分支，如在

data Tree b a = Leaf a | Branch b (Tree b a) (Tree b a) 

例如，可以通過存儲在節點子樹都元素的總數支持O（1）size操作。由於需要正確保存關於子樹大小的信息，因此樹上的所有操作都變得稍微複雜一些 - 實際上，計算樹大小的工作將分攤到構造樹的所有操作上（並巧妙地持久化，因此，只要稍後需要重新構建尺寸，就可以完成最少的工作）。