如何增加AVL樹？

我想增加一棵avl樹來爲每個節點添加額外的屬性，例如它包含的節點數（即在其子樹中）。如何增加AVL樹？

從這個avl java執行代碼在這裏 http://www.blackbam.at/blackbams-blog/2012/05/04/avl-tree-implementation-in-java/ 我想添加一些代碼給它，這樣每個節點將包含一個size元素。

在AvlNode類，我把它改爲：

/** Here is the AVL-Node class for Completenesse **/ 
public class AvlNode { 
    public AvlNode left; 
    public AvlNode right; 
    public AvlNode parent; 
    public int key; 
    public int balance; 
    public int size; 

    public AvlNode(int k) { 
      left = right = parent = null; 
      balance = 0; 
      key = k; 
      size = 1; 
    } 
    public String toString() { 
     return "" + key; 
    } 
}

但現在對於AvlTree類，我在哪裏其實插入過程中添加代碼來更新節點的大小值和刪除操作。我認爲這是rotateleft和rototeight方法。這是正確的嗎？

來源

2013-02-06 omega

你試過了嗎？ –

這完全取決於你想要做什麼與增強。通常情況下，增強平衡二叉搜索樹的時候，你就需要在邏輯中插入額外的代碼做

插入，其改變某些子樹的數量/內容，
缺失，從子樹刪除元素，和
樹輪旋轉，在不同的子樹上移動節點。

CLRS的「算法導論」教科書在增強二分搜索樹上有一章。雖然他們專注於紅/黑樹，但相同的一般策略應該適用於任何基於輪換的樹平衡方案。

希望這會有所幫助！

來源

2013-02-07 00:14:06 templatetypedef

可能值得注意的是，通常最重要的部分是向上/向下傳播樹，這當然必須在您提到的操作過程中/之後調用。 –

如何增加AVL樹？

回答

相關問題