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树​​，如果你想仔细看看。