前言
在上篇博客中我们主要讲了AVL树的四种旋转方法以及如何构建AVL树,这篇博客我们主要来看一下AVL树的删除与销毁操作.
平衡二叉树(AVLTree–c++)(一)
正文
构建AVL树的过程是一个边插入边调整的过程,而删除某个节点的操作那么也是这样的(完成节点的删除后我们需要对AVL树进行判断,如果不再平衡我们需要进行调整).这里将其分为三种情况:删除叶子节点,删除有一颗子树的节点,删除左右子树都有的节点.
一个思路:
左子树上节点的删除相当于我们在右子树上插入了一个新节点，右子树上节点的删除相当于在左子树上插入了一个新节点.
但如何调整取决于该失衡节点的左右孩子的左右子树的高度差(要看具体情况).
删除叶子节点
第一种情况自然是删除叶子节点后,整棵树还是平衡的,这里就不再赘述了,我们来看以下删除叶子节点后,树不再平衡需要调整的情况.
我们这里要删除节点3,删除后是:
删除节点3后,我们通过平衡因子发现节点5失衡,通过上文说到的思路:在左子树上删除节点其实就相当于在右子树上插入节点,。我们找到节点5的右子树上的子节点8，发现节点8的左子树高度比右子树高，这就相当于在节点5的右子树节点8的左子树下插入了一个新的节点。那么此时我们需要的便是RL调整(具体的调整方法请见上篇博客).调整后的AVL树是这样的:
删除有一颗子树的节点
第一种情况是删除节点后直接用左子树或右子树替换该节点的位置后,整棵树还是平衡的,这里也不再赘述了.我们来看删除有一颗子树的节点后,树不再平衡需要调整的情况.
我们这里要删除节点8,删除后是:
删除节点8后,我们通过平衡因子发现节点7失衡,通过上文说到的思路:删除右子树的节点相当于在左子树上插入新的节点。我们找到值为9的节点，找到其父节点，其值为7.然后找到其左孩子，节点值为4。发现该节点的右子树比左子树高度高，也就是相当于在左子树的右子树上插入节点。因此我们这里要进行LR型调整调整后的AVL树是这样的:
删除左右子树都有的节点
这种删除方法有三种情况:
- 左子树高,将其树上值最大的节点赋值给删除节点,然后删除此节点.
- 右子树高,将其树上值最小的节点赋值给删除节点,然后删除此节点.
- 一样高,任用以上两种方法其一即可.
根据AVL树的性质，我们可以得到我们要删除的节点只有两种情况，叶子节点或者是只有一棵子树的节点。
删除后的调整操作按照我们前面已经讲的两种方法来调整。
这里我们要删除节点6:
具体代码
template <typename T>
AVLNode<T> *AVLTree<T>::FindMin(AVLNode<T> *root) const
{
if(root == nullptr)
return nullptr;
if(root->left == nullptr)
return root;
return FindMin(root->left);
}
template <typename T>
AVLNode<T> *AVLTree<T>::FindMax(AVLNode<T> *root) const
{
if(root == nullptr)
return nullptr;
if(root->right == nullptr)
return root;
return FindMax(root->right);
}
template <typename T>
AVLNode<T> *AVLTree<T>::Delete(AVLNode<T> *&root, T key)
{
if(root == nullptr)
return nullptr;
if(key < root->key) //删除的节点在左子树上
{
root->left = Delete(root->left, key);
//判断是否还满足平衡条件
//删除左子树的节点相当于在右子树插入一个节点
if(GetHeight(root->right) - GetHeight(root->left) == 2)
{
if(GetHeight(root->right->left) > GetHeight(root->right->right))
root = RL(root);
else
root = RR(root);
}
}
else if(key > root->key) //删除的节点在右子树上
{
root->right = Delete(root->right, key);
//判断是否还满足平衡条件
//删除右子树的节点相当于在左子树插入一个节点
if(GetHeight(root->left) - GetHeight(root->right) == 2)
{
if(GetHeight(root->left->left) > GetHeight(root->left->right))
root = LL(root);
else
root = LR(root);
}
}
else //找到了要删除的节点
{
//左右子树都非空
//在左右子树中较高的子树中进行删除
if(root->left != nullptr && root->right != nullptr)
{
//左子树高,将其值最大的节点赋值给删除节点,然后删除
if(GetHeight(root->left) >= GetHeight(root->right))
{
AVLNode<T> *MaxNode = FindMax(root->left);
root->key = MaxNode->key;
root->left = Delete(root->left, key);
}
//右子树高,将其值最小的节点赋值给删除节点,然后删除
else
{
AVLNode<T> *MinNode = FindMin(root->right);
root->key = MinNode->key;
root->right = Delete(root->right, key);
}
}
else
{
AVLNode<T> *temp = root;
root = (root->left != NULL) ? root->left : root->right;
delete temp;
}
}
return root;
}
销毁操作就是正常的销毁二叉树操作
template <typename T>
void AVLTree<T>::destory(AVLNode<T> *&root)
{
if(root == nullptr)
return;
destory(root->left);
destory(root->right);
delete root;
}