甘肃龙网

  1. 首页 > 生活 > >

含代码实现 SizeBalanceTree详解

生活百科节点

目录
1.SBT树的概念及其相关性质
2.SBT树的四种违规类型
3.BST树的插入
4.SBT的删除
5.代码汇总
1.SBT树的概念及其相关性质
SizeTree(SBT)是一种平衡二叉查找树 。它的论文由中国广东中山记念中学的陈启峰于2006年末完成 ， php
并在 Camp 2007中发表 。因为SBT的拼写很容易找到中文谐音 ，  它常被中国的Oler们戏称为 “傻X树”、html
“Super BT”等 。但它的性能并不SB ， 编写起来也并不BT 。偏偏相反 ， SBT易于实现 ， 且据陈启峰论文中所言  ， node
“这是目前为止速度最快的高级二叉搜索树” 。它能在O(logn)的时间内完成全部BST的相关操做 。并且因为SBT赖数组
以保持平衡的是Size域而不是其余“无用”的域 ， 它能够很方便地实现动态顺序统计中的和rank 。数据结构
1.2SBT树相关性质：
任何一个叔叔节点的个数不能少于侄子节点的个数 ， 举个例子如图所示：
大叔为T3和T4的叔叔节点 ， 二叔为T1和T2的叔叔节点在SBT树种大叔节点的个数必须大于等于T3和T4任何一个节点的个数 ， 二叔的节点个数必须大于T1和T2之中任何一个节点个数 。
SBT树不像AVL树一样有这么严格的平衡性 ， SBT树这样规定的目的是为了保证左边的高度最大不超过右树的两倍或者右树的高度不会超过左树高度的两倍 ， 具体证明请看大佬的文章
陈启峰SBT论文（译）
1.3SBT树节点的定义：

含代码实现 SizeBalanceTree详解

文章插图
struct SBTNode{SBTNode(const pairkv = pair()):_kv(kv),_left(nullptr),_right(nullptr),_size(1){}pair_kv;SBTNode* _left;SBTNode* _right;int _size;//节点的个数};
2.SBT树的四种违规类型
SBT树和AVL树一样一共有四种违规类型：
1.LL型违规
2.LR型违规
3.RR型违规
4.RL型违规
LL型违规
LL型违规是指大叔的左子树的节点个数大于了二叔的节点个数成为LL型违规和AVL树类似需要进行右旋但与AVL树也有点不一样 ， 具体请看下面的解释：
我们对根节点进行右旋之后 ， 我们会发现大叔的孩子节点发生了变化 ， 还有根节点的孩子也发生了变化 ， 此时需要递归检查大叔和根节点是否满足SBT树的定义 ， 这一点与AVL树有所不同 。为什么孩子节点发生变化之后需要对其进行检查呢？这是因为之前它比较的对象发生了改变 。
对应代码：
Node* rightRotate(Node* cur) {Node* leftNode = cur->_left;cur->_left = leftNode->_right;leftNode->_right = cur;leftNode->_size = cur->_size;//重新调整节点个数cur->_size = (cur->_left ? cur->_left->_size : 0) + (cur->_right ? cur->_right->_size : 0)+1;//重新计算节点个数return leftNode;//返回调整后的新头部}
注意：递归调整放到方法里面
RR型违规：
RR型违规是指T4节点的个数大于大叔的节点个数 ， 调整方案和AVL树一样对根节点进行一个左旋 。
同样的根节点和二叔这两个节点孩子节点发生改变 ， 递归对这个两个节点进行检查看是否满足SBT树的定义 。
对应代码：
Node* leftRotate(Node* cur) {Node* rightNode = cur->_right;cur->_right = rightNode->_left;rightNode->_left = cur;rightNode->_size = cur->_size;//重新调整节点个数cur->_size = (cur->_left ? cur->_left->_size : 0) + (cur->_right ? cur->_right->_size : 0) + 1;//重新计算节点的个数return rightNode;//返回新的头部}


上一篇：1 概率与统计进阶——概率统计的基础概念：条件概率、全概率、贝叶斯公式

下一篇：智能手表好处有多少？荣耀产品开箱“惊人”