我发现,当从 AVL 树中删除一个节点时,它可能需要多次重组,而插入只需要一次。谁能给我一个这样的删除案例的例子吗? 另外,我已经实现了一个AVL树,我想检查delete()函数是否正常工作。那么你能给出一系列插入和删除序列来帮助我确定我的delete()是否正确并处理所有这些问题吗?
假设您有一个 AVL 树,每个节点都存储一个名称(字符串),并且您有函数 insertAVL(element) 和 deleteAVL(element)。
嗯,插入和删除都可以有多次轮换,因为你必须沿着树向上移动。
例如添加数据集{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 树这里,如果你想仔细看看。
插入时最多只需要一次重组,删除时可能需要多次重组,因为重组的效果是将该部分的高度减少 1。
如果您需要在插入中进行重组,则意味着您已插入到平衡因子为1或-1的子树下,使其变为2或-2。通过这次插入,该子树的高度增加了 1,重组基本上使树恢复到原来的高度。因此,该子树的父母仍然具有相同的高度。
另一方面,如果您删除并且需要重组,您基本上删除了子树较短子节点的左节点,导致平衡因子为 2 或 -2。在这种情况下,删除后不会影响该子树的原始高度。然而,重组树会产生
newheight = oldheight - 1
,这可能会影响其父母的高度和平衡。因此,您需要检查重组子树的每个父树,以确保每个子树都是平衡的。