内容简介: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的负载平衡?
- 如何解决机器学习中的数据不平衡问题?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。