参照物 一文读懂 AVL 树(3)
}
void AVL::insert(int key)
{
header->left = insert_real(key, header->left);
}
查找操作
Node * AVL::find_real(int key, Node * node)
{
if (node == nullptr)
return nullptr;
if (key < node->key)
return find_real(key, node->left);
else if (key > node->key)
return find_real(key, node->right);
else
return node;
}
Node * AVL::find(int key)
{
return find_real(key, header->left);
}
删除操作
删除操作的四种失衡情况和插入操作一样,读者可以参考前文。下面是删除操作的实现代码:
Node * AVL::erase_real(int key, Node * node)
{
if (node == nullptr)
return node;
if (key < node->key)
node->left = erase_real(key, node->left);
else if (key > node->key)
node->right = erase_real(key, node->right);
else
{
if (node->left && node->right)
{
// 找到后继结点
Node * x = node->right;
while (x->left)
x = x->left;
// 后继直接复制
node->key = x->key;
// 转化为删除后继
node->right = erase_real(x->key, node->right);
}
else
{
Node * t = node;
node = node->left ? node->left : node->right;
delete t;
if (node == nullptr)
return nullptr;
}
}
node->height = max(get_height(node->left), get_height(node->right)) + 1;
int balance = get_balance(node);
// 左左失衡
if (balance > 1 && get_balance(node->left) >= 0) // 需要加等号
return ll_rotate(node);
// 右右失衡
if (balance < -1 && get_balance(node->right) <= 0) // 需要加等号
return rr_rotate(node);
// 左右失衡
if (balance > 1 && get_balance(node->left) < 0)
return lr_rotate(node);
// 右左失衡
if (balance < -1 && get_balance(node->right) > 0)
#吴亦凡#