内容简介:AVL树本质上还是二叉树,但是比二叉搜索树多了一个条件:每个节点的左右子树高度不超过1因为二叉搜索树在极端情况下无限趋近于链表,这种情况下不能体现二叉搜索树的高效率。如下图
AVL树本质上还是二叉树,但是比二叉搜索树多了一个条件:每个节点的左右子树高度不超过1
因为二叉搜索树在极端情况下无限趋近于链表,这种情况下不能体现二叉搜索树的高效率。如下图
{ Node<T> root; { T key; Node<T> left; Node<T> right; { .key = key; } } }
{ height(root); } { ; { ; } }
AVL树在添加或者删除后,可能导致AVL树失去平衡。
失去平衡包括四种:LL(左左),LR(左右),RR(右右),RL(右左),具体参考下图
旋转方式:将k1变成根节点,k2变成k1的右子树,"k1的右子树"变成"k2的左子树"
/** * 左左旋转 * @param tree * @return */ > tree){ ; tree.; lTree. = tree; lTree; }
旋转方式:旋转方式与LL旋转类似
/** * 右右旋转 * @param tree * @return */ > tree){ ; tree.; rTree. = tree; rTree; }
旋转方式:左右旋转需要经过两次调整,第一次旋转是围绕"k1"进行的"RR旋转",第二次是围绕"k3"进行的"LL旋转"
/** * 左右旋转 * tree * */ { rrRotation(tree.left); llRotation(tree); }
旋转方式:右左旋转同样需要经过两次调整,第一次旋转是围绕"k3"进行的"LL旋转",第二次是围绕"k1"进行的"RR旋转"
/** * 右右旋转 * tree * */ { llRotation(tree.right); rrRotation(tree); }
{ ){ root = Node<>(key); } { root = fixAfterOperation(root); } } { tmp; ){ tree = Node<>(key); } { tmp = key.compareTo(tree.key); ){ tree.left = (tree.left,key); }){ tree.right = (tree.right,key); } { tree; } } tree; }
当树添加或者删除某一节点后,如果导致AVL树失衡,旋转树
> tree) { (tree != null) { tree = llRotation(tree); } tree = lrRotation(tree); } } tree = rlRotation(tree); } { tree =rrRotation(tree); } } } tree; }
{ ){ (root,key); root = fixAfterOperation(root); } } { tree; tmp = key.compareTo(tree.key); ){ tree.left = (tree.left,key); }){ tree.right = (tree.right,key); } { Node<T> successor = successor(tree); Node<T> l = tree.left; tree = ; } tree.key = l.key; tree.left = (tree.left,l.key); } } tree.key = successor.key; tree.right = (tree.right,successor.key); } } tree; } { Node<T> result = tree.right; ){ result = result.left; } result; }
Linux公社的RSS地址 : https://www.linuxidc.com/rssFeed.aspx
本文永久更新链接地址: https://www.linuxidc.com/Linux/2019-03/157249.htm
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 机器学习之类别不平衡问题:从数据集角度处理不平衡问题(二)
- Kafka 重平衡机制
- 处理非平衡数据的七个技巧
- 企业如何实现云计算中的负载平衡?
- 如何在Kubernetes实现gRPC的负载平衡?
- 如何解决机器学习中的数据不平衡问题?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
The Web Designer's Idea Book
Patrick Mcneil / How / 2008-10-6 / USD 25.00
The Web Designer's Idea Book includes more than 700 websites arranged thematically, so you can find inspiration for layout, color, style and more. Author Patrick McNeil has cataloged more than 5,000 s......一起来看看 《The Web Designer's Idea Book》 这本书的介绍吧!