参照物 一文读懂 AVL 树(6)

else

return node;

}

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)

return rl_rotate(node);

return node;

}

void AVL::in_order(Node * node)

{

if (node == nullptr)

return;

in_order(node->left);

cout << node->key << " ";

in_order(node->right);

}

AVL::AVL()

{

header = new Node(0);

}

AVL::~AVL()

{

destroy(header->left);

delete header;

header = nullptr;

}

void AVL::insert(int key)

{

header->left = insert_real(key, header->left);