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

{

Node * x = y->left;

y->left = rr_rotate(x);

return ll_rotate(y);

}

（4）右左失衡

所谓的右左，即 "失衡结点" 的右子树比左子树高 2，右孩子下的左子树比右子树高 1。

观察发现，若先对 "以 x 为根的子树" 进行 "左左旋转 (ll_rotate)"，此时 "以 y 为根的子树" 恰好符合 "右右失衡"，所以再进行一次 "右右旋转 (rr_rotate)"。参照物两次旋转后，恢复平衡。参照物

Node * AVL::rl_rotate(Node * y)

{

Node * x = y->right;

y->right = ll_rotate(x);

return rr_rotate(y);

}

插入操作

插入成功后，在递归回溯时依次对经过的结点判断是否失衡，若失衡就需要对其进行对应的旋转操作使其恢复平衡，在这期间，原先作为一棵子树的根结点就会因为旋转被替换，因此设置insert_real( )返回的是新根结点，这样就可以实时更新根结点。

插入操作实现代码如下：

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;