AVL樹的刪除和重構

Question

我已經看到，當一個節點從AVL樹中刪除時，它可能需要重建多次，而插入只需要一次。任何人都可以給我一個這種刪除案例的例子。 另外我已經實現了AVL樹，我想檢查delete（）函數是否正常工作。所以你可以給一系列的插入，然後刪除，這可以幫助我確定我的delete（）是否正確，並處理所有這些？

假設你有一個AVL樹，每個節點存儲一個名稱（字符串），並且你有函數insertAVL（element）和deleteAVL（element）。

Answer 1

好吧，插入和刪除都可以有多個旋轉，因爲你必須在樹上工作。

例如，添加{5,2,4,3,7,8,10,9}的數據集，然後刪除{5}，添加{9}，最後刪除{2}。你得到以下。

addValue. id=5 
└── (1) 5 

addValue. id=2 
└── (2) 5 
    └── (1) 2 

addValue. id=4 
└── (3) 5 *unbalanced left 2 - right 0* 
    └── (2) 2 
     └── (1) 4 
After left rotation: 
└── (3) 5 *unbalanced left 2 - right 0* 
    └── (2) 4 
     └── (1) 2 
After right rotation: 
└── (2) 4 
    ├── (1) 2 
    └── (1) 5 

addValue. id=3 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (1) 5 

addValue. id=7 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (2) 5 
     └── (1) 7 

addValue. id=8 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 5 *unbalanced right 2 - left 0* 
     └── (2) 7 
      └── (1) 8 
After left rotation: 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (2) 7 
     ├── (1) 5 
     └── (1) 8 

addValue. id=10 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 
     ├── (1) 5 
     └── (2) 8 
      └── (1) 10 

addValue. id=9 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 
     ├── (1) 5 
     └── (3) 8 *unbalanced left 0 - right 2* 
      └── (2) 10 
       └── (1) 9 
After right rotation: 
└── (5) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (4) 7 
     ├── (1) 5 
     └── (3) 8 *unbalanced right 2 - left 0* 
      └── (2) 9 
       └── (1) 10 
After left rotation: 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 
     ├── (1) 5 
     └── (2) 9 
      ├── (1) 8 
      └── (1) 10 

removeValue. value=5 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 *unbalanced right 2 - left 0* 
     └── (2) 9 
      ├── (1) 8 
      └── (1) 10 
After left rotation: 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 9 
     ├── (2) 7 
     │ └── (1) 8 
     └── (1) 10 

addValue. id=9 
└── (5) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (4) 9 
     ├── (3) 7 *unbalanced right 2 - left 0* 
     │ └── (2) 8 
     │  └── (1) 9 
     └── (1) 10 
After left: 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 9 
     ├── (2) 8 
     │ ├── (1) 7 
     │ └── (1) 9 
     └── (1) 10 

removeValue. value=2 
└── (4) 4 *unbalanced right 3 - left 1* 
    ├── (1) 3 
    └── (3) 9 
     ├── (2) 8 
     │ ├── (1) 7 
     │ └── (1) 9 
     └── (1) 10 
After right rotation: 
└── (4) 4 *unbalanced right 3 - left 1* 
    ├── (1) 3 
    └── (3) 8 
     ├── (1) 7 
     └── (2) 9 
      ├── (1) 9 
      └── (1) 10 
After left rotation: 
└── (3) 8 
    ├── (2) 4 
    │ ├── (1) 3 
    │ └── (1) 7 
    └── (2) 9 
     ├── (1) 9 
     └── (1) 10 

我有一棵AVL樹​​，如果你想仔細看看。