数据结构笔记总结(11.6)LR 和 RL

LL和RR

将前两节的情况重新命名

新插入的节点z在y左孩子的右侧(LR)

首先对x进行左旋转,转为了LL的情况。

新插入的节点z在y右孩子的左侧(RL)

首先对x进行右旋转,转化成了RR的情况。

代码实现

// 平衡维护
//LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
    return rightRotate(node);
//RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
    return leftRotate(node);
//LR
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
    node.left = leftRotate(node.left);
    return rightRotate(node);
}
//RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
    node.right = rightRotate(node.right);
    return leftRotate(node);
}

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(11.6)LR 和 RL

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多