SizeBalanceTree详解（含代码实现）

转x33g5p2x  于2022-02-07 转载在 其他  
字(9.7k)|赞(0)|评价(0)|浏览(255)

1.SBT树的概念及其相关性质

2.SBT树的四种违规类型

3.BST树的插入

4.SBT的删除

5.代码汇总

1.SBT树的概念及其相关性质

Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山记念中学的陈启峰于2006年末完成，php

并在Winter Camp 2007中发表。因为SBT的拼写很容易找到中文谐音， 它常被中国的Oler们戏称为 “傻X树”、html

“Super BT”等。但它的性能并不SB，编写起来也并不BT。偏偏相反，SBT易于实现，且据陈启峰论文中所言  ，node

“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成全部BST的相关操做。并且因为SBT赖数组

以保持平衡的是Size域而不是其余“无用”的域，它能够很方便地实现动态顺序统计中的select和rank。数据结构

1.2SBT树相关性质：

任何一个叔叔节点的个数不能少于侄子节点的个数，举个例子如图所示：

大叔为T3和T4的叔叔节点，二叔为T1和T2的叔叔节点在SBT树种大叔节点的个数必须大于等于T3和T4任何一个节点的个数，二叔的节点个数必须大于T1和T2之中任何一个节点个数。

SBT树不像AVL树一样有这么严格的平衡性，SBT树这样规定的目的是为了保证左边的高度最大不超过右树的两倍或者右树的高度不会超过左树高度的两倍，具体证明请看大佬的文章

陈启峰SBT论文（译）

1.3SBT树节点的定义：

struct SBTNode
{
	SBTNode(const pair<K, V>kv = pair<K, V>())
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_size(1)
	{}
	pair<K, V>_kv;
	SBTNode<K, V>* _left;
	SBTNode<K, V>* _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;//返回调整后的新头部
	}

注意：递归调整放到maintain方法里面 

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;//返回新的头部
	}

LR型违规：

LR型是指B节点的个数大于二叔节点的个数，其调整策略和AVL树一样先对大叔进行一个左旋，在对根进行一个右旋。

经过旋转之后我们发现根，大叔，还B这三个节点的左右孩子发生了变化，因此需要对其进行检查看是否满足SBT树的定义 

RL型同理老铁们可以下去自己画一下。

对应调整代码：

Node* maintain(Node* cur) {
		if (cur == nullptr) {
			return nullptr;
		}
		//将节点的个数拿出来
		int leftSize = cur->_left != nullptr ? cur->_left->_size : 0;
		int leftLeftSize = cur->_left && cur->_left->_left ? cur->_left->_left->_size : 0;
		int leftRightSize = cur->_left && cur->_left->_right ? cur->_left->_right->_size : 0;
		int rightSize = cur->_right? cur->_right->_size : 0;
		int rightLeftSize = cur->_right && cur->_right->_left ? cur->_right->_left->_size : 0;
		int rightRightSize = cur->_right && cur->_right->_right ? cur->_right->_right->_size : 0;
		if (leftLeftSize > rightSize) {//LL型
			cur = rightRotate(cur);//右旋
			cur->_right = maintain(cur->_right);//递归检查
			cur = maintain(cur);
		}
		else if (leftRightSize > rightSize) {//LR型，调整完成之后递归检查
			cur->_left = leftRotate(cur->_left);
			cur = rightRotate(cur);
			cur->_left = maintain(cur->_left);
			cur->_right = maintain(cur->_right);
			cur = maintain(cur);
		}
		else if (rightRightSize > leftSize) {//RR型，调整后并且检查
			cur = leftRotate(cur);
			cur->_left = maintain(cur->_left);
			cur = maintain(cur);
		}
		else if (rightLeftSize > leftSize) {//RL型，调整后并检查
			cur->_right = rightRotate(cur->_right);
			cur = leftRotate(cur);
			cur->_left = maintain(cur->_left);
			cur->_right = maintain(cur->_right);
			cur = maintain(cur);
		}
		return cur;//返回调整后的头部
   }

3.BST树的插入

BST树的插入和搜索二叉树的插入基本一样只不过多了调整部分如果不太清楚的老铁可以去看我之前的博客

对应代码：

// 现在，以cur为头的树上，新增，加(key, value)这样的记录
		// 加完之后，会对cur做检查，该调整调整
		// 返回，调整完之后，整棵树的新头部
	Node* add(Node* cur, const pair<K, V>& kv) {
		if (cur == nullptr) {
			return new Node(kv);
	    }
		else {
			cur->_size++;
			if (cur->_kv.first > kv.first) {
				cur->_left = add(cur->_left, kv);//去左边插入
			}
			else {
				cur->_right = add(cur->_right, kv);//去右边插入
			}
		}
		return maintain(cur);//返回插入好的新头部
  }
	bool Insert(const pair<K, V>& kv) {
		Node* lastNode = findLastIndex(kv.first);
		if (lastNode && lastNode->_kv.first == kv.first) {//已经存在
			return false;
		}
		_root = add(_root, kv);
		return true;
	}

4.SBT的删除

SBT的删除和AVL树删除的情况基本一样至少调整方式不一样，如果不太清楚可以看一下我的哪篇文章。

Node* Delete(Node* cur, K key) {
		cur->_size--;
		if (cur->_kv.first > key) {
			cur->_left = Delete(cur->_left, key);
		}
		else if (cur->_kv.first < key) {
			cur->_right = Delete(cur->_right, key);//左边删并将新的头部返回
		}
		else {
			if (!cur->_left && !cur->_right) {//左为空并且右为空
				delete cur;
				cur = nullptr;
			}
			else if (!cur->_left && cur->_right) {//左为空但右不为空
				Node* subR = cur->_right;
				delete cur;
				cur = subR;
			}
			else if (cur->_left && !cur->_right) {//左不为空但右为空
				Node* subL = cur->_left;
				delete cur;
				cur = subL;
			}
			else {//左右都不为空找后继节点
				Node* pre = nullptr;
				Node* des = cur->_right;
				des->_size--;
				while (des->_left) {
					pre = des;
					des = des->_left;
					des->_size--;
				}
				if (pre) {//链接cur的左右孩子
					pre->_left = des->_right;
					des->_right = cur->_right;
				}
				des->_left = cur->_left;
				des->_size = des->_left->_size + (des->_right ? des->_right->_size:0) + 1;//更新size
				delete cur;
				cur = des;
			}
		}
		cur = maintain(cur);//平衡
		return cur;//返回新头部
	}
	void Erase(K key) {
		Node* lastNode = findLastIndex(key);
		if(lastNode)
		_root = Delete(_root,key);
		else {
			return;
		}
}

 5.代码汇总

#pragma once 
#include<math.h>
#include<iostream>
#include<vector>
using namespace std;
template<class K,class V>
struct SBTNode
{
	SBTNode(const pair<K, V>kv = pair<K, V>())
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_size(1)
	{}
	pair<K, V>_kv;
	SBTNode<K, V>* _left;
	SBTNode<K, V>* _right;
	int _size;//节点的个数
};
template<class K,class V>
class SizeBalancedTreeMap {
	typedef SBTNode<K, V> Node;
public:
	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;//返回调整后的新头部
	}
	
	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;//返回新的头部
	}

	Node* maintain(Node* cur) {
		if (cur == nullptr) {
			return nullptr;
		}
		//将节点的个数拿出来
		int leftSize = cur->_left != nullptr ? cur->_left->_size : 0;
		int leftLeftSize = cur->_left && cur->_left->_left ? cur->_left->_left->_size : 0;
		int leftRightSize = cur->_left && cur->_left->_right ? cur->_left->_right->_size : 0;
		int rightSize = cur->_right? cur->_right->_size : 0;
		int rightLeftSize = cur->_right && cur->_right->_left ? cur->_right->_left->_size : 0;
		int rightRightSize = cur->_right && cur->_right->_right ? cur->_right->_right->_size : 0;
		if (leftLeftSize > rightSize) {//LL型
			cur = rightRotate(cur);//右旋
			cur->_right = maintain(cur->_right);//递归检查
			cur = maintain(cur);
		}
		else if (leftRightSize > rightSize) {//LR型，调整完成之后递归检查
			cur->_left = leftRotate(cur->_left);
			cur = rightRotate(cur);
			cur->_left = maintain(cur->_left);
			cur->_right = maintain(cur->_right);
			cur = maintain(cur);
		}
		else if (rightRightSize > leftSize) {//RR型，调整后并且检查
			cur = leftRotate(cur);
			cur->_left = maintain(cur->_left);
			cur = maintain(cur);
		}
		else if (rightLeftSize > leftSize) {//RL型，调整后并检查
			cur->_right = rightRotate(cur->_right);
			cur = leftRotate(cur);
			cur->_left = maintain(cur->_left);
			cur->_right = maintain(cur->_right);
			cur = maintain(cur);
		}
		return cur;//返回调整后的头部
   }
	// 现在，以cur为头的树上，新增，加(key, value)这样的记录
		// 加完之后，会对cur做检查，该调整调整
		// 返回，调整完之后，整棵树的新头部
	Node* add(Node* cur, const pair<K, V>& kv) {
		if (cur == nullptr) {
			return new Node(kv);
	    }
		else {
			cur->_size++;
			if (cur->_kv.first > kv.first) {
				cur->_left = add(cur->_left, kv);//去左边插入
			}
			else {
				cur->_right = add(cur->_right, kv);//去右边插入
			}
		}
		return maintain(cur);//返回插入好的新头部
  }
	bool Insert(const pair<K, V>& kv) {
		Node* lastNode = findLastIndex(kv.first);
		if (lastNode && lastNode->_kv.first == kv.first) {//已经存在
			return false;
		}
		_root = add(_root, kv);
		return true;
	}

	Node* Delete(Node* cur, K key) {
		cur->_size--;
		if (cur->_kv.first > key) {
			cur->_left = Delete(cur->_left, key);
		}
		else if (cur->_kv.first < key) {
			cur->_right = Delete(cur->_right, key);//左边删并将新的头部返回
		}
		else {
			if (!cur->_left && !cur->_right) {//左为空并且右为空
				delete cur;
				cur = nullptr;
			}
			else if (!cur->_left && cur->_right) {//左为空但右不为空
				Node* subR = cur->_right;
				delete cur;
				cur = subR;
			}
			else if (cur->_left && !cur->_right) {//左不为空但右为空
				Node* subL = cur->_left;
				delete cur;
				cur = subL;
			}
			else {//左右都不为空找后继节点
				Node* pre = nullptr;
				Node* des = cur->_right;
				des->_size--;
				while (des->_left) {
					pre = des;
					des = des->_left;
					des->_size--;
				}
				if (pre) {//链接cur的左右孩子
					pre->_left = des->_right;
					des->_right = cur->_right;
				}
				des->_left = cur->_left;
				des->_size = des->_left->_size + (des->_right ? des->_right->_size:0) + 1;//更新size
				delete cur;
				cur = des;
			}
		}
		cur = maintain(cur);//平衡
		return cur;//返回新头部
	}
	void Erase(K key) {
		Node* lastNode = findLastIndex(key);
		if(lastNode)
		_root = Delete(_root,key);
		else {
			return;
		}
	}

	Node* findLastIndex(K key) {
	      Node* pre = _root;
		Node* cur = _root;
		while (cur != nullptr) {
			pre = cur;
			if (cur->_kv.first==key) {
				break;
			}
			else if (cur->_kv.first>key) {
				cur = cur->_left;
			}
			else {
				cur = cur->_right;
			}
		}
		return pre;
	}

	 Node* findLastNoSmallIndex(K key) {
	      Node* ans = nullptr;
		Node* cur = _root;
		while (cur != nullptr) {
			if (cur->_kv.first==key) {
				ans = cur;
				break;
			}
			else if (cur->_kv.first>key) {
				ans = cur;
				cur = cur->_left;
			}
			else {
				cur = cur->_right;
			}
		}
		return ans;
	}

      Node* findLastNoBigIndex(K key) {
		  SBTNode<K, V> ans = nullptr;
		Node* cur = _root;
		while (cur != nullptr) {
			if (cur->_kv.first==key) {
				ans = cur;
				break;
			}
			else if (cur->_kv.first>key) {
				cur = cur->_left;
			}
			else {
				ans = cur;
				cur = cur->_right;
			}
		}
		return ans;
	}
	  bool  containsKey(K key) {
		  
		 Node* lastNode = findLastIndex(key);
		  return lastNode && lastNode->_kv.first==key? true : false;
	  }

	void _Inorder(Node* root) {
		if (!root)return;
		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}
	void Inorder() {
		_Inorder(_root);
	}

private:
	Node* _root = nullptr;
};

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_56999918/article/details/122774352

内容来源于网络，如有侵权，请联系作者删除！

p2p网络协议网络

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com