tree-balancing

2熱度

2回答

我試圖解決以下問題：「給定一個具有唯一整數元素的排序（遞增順序）數組，寫一個算法來創建一個具有最小高度的BST。給定的答案將根節點作爲數組的中間。雖然這樣做對我來說很直觀，但我試圖嚴格證明，最好將根節點設置在數組中間。本書給出的理由是：「爲了創建最小高度的樹，我們需要儘可能地將左子樹中的節點數量與右子樹中的節點數量相匹配，這意味着我們希望根節點是數組的中間部分，因爲這意味着一半的元素會少於根，

0熱度

2回答

瞭解AVL旋轉的平衡因素/節點高度

因此，我很難理解如何平衡AVL樹。據我所知，旋轉的東西，但我無法弄清楚如何找到節點高度的平衡因素，例如： http://i.imgur.com/yh5zNIl.png 誰能向我解釋如何找到真正的平衡因素對於每個節點？我知道如果[（左子樹） - （右子樹）]的高度不在（-1 < = x < = 1），那麼它的不平衡......但我不知道如何找到「 X」。（編輯：我不需要代碼，我只是想了解如何找到B

1熱度

1回答

保持AVL樹平衡而不旋轉

B樹是像AVL樹一樣的自平衡樹。 HERE我們可以看到左右旋轉是如何保持AVL樹平衡的。和HERE是解釋B樹插入的鏈接。這種插入技術並不涉及任何旋轉，如果我沒有錯，保持樹木平衡。因此它看起來更簡單。問：是否有任何類似的（或沒有使用旋轉的其他技術）保持avl樹平衡？

0熱度

1回答

何時平衡BST的最佳時間？

我有一個BST和2個進入它的隊列。爲了在最短的時間內插入和刪除，我需要經常平衡我的樹。爲此，我使用DSW算法。我已經完成了所有這些工作，並且這一切都很好。我的問題是我不知道什麼時候平衡樹的最佳時間。我試過尋找這方面的文件和任何類型的信息，但我找不到任何。我基本上需要知道什麼時候對樹進行平衡是最理想的，這樣不會太頻繁地花費太多時間，但是我的插入刪除時間通常不會很長。所以最終總運行時間儘可能短。

3熱度

1回答

立即從平衡二叉樹中刪除多個項目

我在項目中使用帶有鏈接葉子的紅黑二叉樹（Java的TreeMap），以快速查找並遍歷項目。問題是我可以很容易地在樹上獲得35000個物品，並且我需要多次刪除「X以上的所有物品」，這幾乎可以是整個樹（比如30000個物品，因爲它們都更大比X）要花費太多時間去除它們並且每次重新平衡樹。是否有任何算法可以幫助我在這裏（所以我可以讓自己的樹實現）？

0熱度

1回答

什麼是AVL樹的平衡因子

我正在爲AVL樹做介紹，無法理解什麼是平衡因子。請給我鏈接或任何可以用圖形方式理解AVL樹高度效果的東西

0熱度

1回答

排序單鏈表到BST Java

我目前有一個排序的鏈接列表，並與一個void返回方法，我需要從列表中遞歸構造一個平衡二叉搜索樹（這被稱爲第二個參數）。作爲參數，我只能擁有LL Head，創建的根和列表的長度。該方法不能是破壞性的LL，和事後測試樹我有一個printTree和TREEDEPTH： public static void makeBalancedTree(ListNode head, TreeNode root, i

0熱度

1回答

AVL樹完美平衡問題

我想知道AVL樹重新平衡是否存在根本問題。根據幾個教程，對於AVL插入，最大2旋轉它可以是平衡的。但是，它可能取決於所謂的平衡。按照link查看樹。本來它有6個元素。假設我們插入最後一個值爲3或4.5或5.5或6.5。無論如何，它將被插入到底部的左側。作爲總共7個元素的樹，爲了完美的平衡，我會認爲它只有3行。這將迫使新的根是6或6.5（如果我們插入6.5）。我真的無法想出一種在兩輪內重新平衡它

0熱度

1回答

當它重新平衡自己時，紅黑樹會修改其葉子的從左到右的順序嗎？

換句話說，如果您在插入後立即從左到右閱讀紅黑樹中的樹葉值，那麼在樹上執行平衡操作後，該順序是否保持不變？

1熱度

1回答

Haskll，高度平衡檢查

有沒有辦法將其轉換，以便根據身高檢查平衡？（假設這就是問題所在。） size :: Tree a -> Int size (Leaf n) = 1 size (Node x z) = size x + size z + 1 isBalanced :: Tree a -> Bool isBalanced (Leaf _) = True isBalanced (Node l r) =