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

y->left = rr_rotate(x);

return ll_rotate(y);

}

Node * AVL::rl_rotate(Node * y)

{

Node * x = y->right;

y->right = ll_rotate(x);

return rr_rotate(y);

}

void AVL::destroy(Node * node)

{

if (node == nullptr)

return;

destroy(node->left);

destroy(node->right);

delete node;

}

int AVL::get_height(Node * node)

{

if (node == nullptr)

return 0;

return node->height;

}

int AVL::get_balance(Node * node)

{

if (node == nullptr)

return 0;

return get_height(node->left) - get_height(node->right);

}

Node * AVL::insert_real(int key, Node * node)

{

if (node == nullptr)

return new Node(key);

if (key < node->key)

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

else if (key > node->key)

node->right = insert_real(key, node->right);

else

return node;

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;

}

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);