[原创] Size-Balance Tree 的详细模板
2020-02-27 本文已影响0人
林甜夏
Powered by hjfzzm
Eromanga_Sensei——Izumi Sagiri
- 最近看了很多平衡树的博客，感觉大家写的真的是不一样啊，代码风格完全不同，我个人觉得链式的最好理解，如果对指针学的好的话，链式理解起来简直easy，反观数组的比较难写，理解起来也有点难，但数组的优点在于速度更快，各有利弊。
- 首先给出平衡条件：
size[right[t]] >= max(size[left[left[t]]], size[right[left[t]]])
size[left[t]] >= max(size[left[right[t]]], size[right[right[t]]])
其中 size[t] 表示 t节点所在子树的结点个数。
- 公式看起来很复杂，形象一点来说，就是每个节点所在子树的结点个数不小于其他兄弟的两个孩子所在子树的结点个数。比如对于这棵二叉查找树
一颗平衡二叉树
对于结点39来说，就不满足SBTree的自平衡条件。因为它的左孩子所在子树的结点个数为0，而右孩子的右子树结点个数为1。
- 左旋右旋不在此描述
- 在调整过程中，一共会有4种会触发旋转的情况
1、LL型(size[left[left[t]]] > size[right[t]]) ：首先对子树t执行右旋操作，旋转以后对t的右子树进行调整，之后再对子树t进行调整。
2、LR型(size[right[left[t]]] > size[right[t]]) ：首先对t的子树执行左旋操作，再对t进行右旋操作。之后分别调整结点t的左右子树最终对结点t进行调整。
3、RR型(size[right[right[t]]] > size[left[t]]) ：首先对t执行左旋操作，旋转以后对t的左子树进行调整，之后再对t进行调整。
4、RL型(size[left[right[t]]] > size[left[t]]) ：首先对结点t的右子树执行右旋操作，再对t进行左旋操作，之后分别调整t的左右子树，最终对t进行调整。
通过递归的进行调整，我们可以最终让不平衡的SBTree回复平衡状态，可以证明，调整操作的均摊时间复杂度为O(1)。和AVL不太一样的是，SBTree只有在插入时才可能触发调整，而不需要在删除结点以后进行调整。
- 从理论上说，SBTree和AVL树相比在均摊时间复杂度上没有区别，每次查询，插入和删除的时间复杂度为O(log n)。在实际运用中，SBTree在查询操作较多的情况下会有效率上的有事。加之为了维护平衡性记录了每个节点所在子树大小，相比其他平衡 二叉查找树而言，更便于求解第k打元素、或求解元素的秩等类似问题。
- 下面给出代码
#include <bits/stdc++.h>
using namespace std;
//全局开关，是否可以插入相同元素
bool SAME = true;
/******************附加---由此向下******************/
struct Adds {
int delta;
};
/******************附加---由此向上******************/
template<typename Type>
class SBTNode {
public:
Type data;
int size, cnt;
Adds ADD;
SBTNode<Type> *lchild, *rchild, *father;
SBTNode(Type init_data, int init_size = 0, SBTNode<Type> *init_father = NULL);
~SBTNode();
void insert(Type value);
SBTNode<Type>* search(Type value);
SBTNode<Type>* predecessor();
SBTNode<Type>* successor();
void remove_node(SBTNode<Type> *delete_node);
bool remove(Type value);
void LDR(SBTNode <Type> *node);
int select(int k);
void remove_LRD(SBTNode<Type> *node);
SBTNode <Type> * selectSBTNode(int k);
void Pre_LRD(SBTNode<Type> *root, SBTNode<Type> *node);
};
template<typename Type>
class BinaryTree {
private:
SBTNode<Type>* root;
public:
BinaryTree();
~BinaryTree();
void insert(Type value);
bool find(Type value);
bool remove(Type value);
void LDR();
int select(int k);
bool remove_root(Type value);
SBTNode <Type> * getRoot() return root;
int BMK(int value, bool flag);
SBTNode <Type> * selectSBTNode(int k);
void Pre_insert(SBTNode<Type>* node);
void Pre_add_root(SBTNode<Type>* node);
void Pre_LRD(SBTNode<Type> *root, SBTNode<Type> *node);
void Splay(SBTNode<Type> *node);
};
SBTNode<int> ZERO(0);
SBTNode<int>* NIL = &ZERO;
/***********以下为 SBTNode (节点)的函数************/
template <typename Type>
SBTNode<Type>::SBTNode(Type init_data, int init_size, SBTNode<Type>* init_father) {
data = init_data;
size = init_size;
lchild = NIL;
rchild = NIL;
father = init_father;
cnt = 1;
/****附加修改区****/
ADD.delta = 0;
}
template <typename Type>
SBTNode<Type>::~SBTNode() {
if(lchild != NIL) delete lchild;
if(rchild != NIL) delete rchild;
}
template <typename Type>
SBTNode<Type>* left_rotate(SBTNode<Type>* node) { //zag
SBTNode<Type>* temp = node->rchild;
node->rchild = temp->lchild;
temp->lchild->father = node;
temp->lchild = node;
temp->father = node->father;
node->father = temp;
temp->size = node->size;
node->size = node->lchild->size + node->rchild->size + 1;
return temp;
}
template <typename Type>
SBTNode<Type>* right_rotate(SBTNode<Type>* node) { //zig
SBTNode<Type>* temp = node->lchild;
node->lchild = temp->rchild;
temp->rchild->father = node;
temp->rchild = node;
temp->father = node->father;
node->father = temp;
temp->size = node->size;
node->size = node->lchild->size + node->rchild->size + 1;
return temp;
}
template <typename Type>
SBTNode<Type>* maintain(SBTNode<Type>* node, bool flag) {
if(flag == false) {
if(node->lchild->lchild->size > node->rchild->size) {
node = right_rotate(node);
} else if(node->lchild->rchild->size > node->rchild->size) {
node->lchild = left_rotate(node->lchild);
node = right_rotate(node);
} else {
return node;
}
} else {
if(node->rchild->rchild->size > node->lchild->size) {
node = left_rotate(node);
} else if(node->rchild->lchild->size > node->lchild->size) {
node->rchild = right_rotate(node->rchild);
node = left_rotate(node);
} else {
return node;
}
}
node->lchild = maintain(node->lchild, false);
node->rchild = maintain(node->rchild, true);
node = maintain(node, false);
node = maintain(node, true);
return node;
}
template <typename Type>
SBTNode<Type>* insert(SBTNode<Type>* node, Type value) {
node->size++;
if(value > node->data) {
if(node->rchild == NIL) {
node->rchild = new SBTNode<Type>(value, 1, node);
} else {
node->rchild = insert(node->rchild, value);
}
} else {
if(node->lchild == NIL) {
node->lchild = new SBTNode<Type>(value, 1, node);
} else {
node->lchild = insert(node->lchild, value);
}
}
return maintain(node, value > node->data);
}
template <typename Type>
SBTNode<Type>* SBTNode<Type>::search(Type value) {
if(data == value) {
return this;
} else if(value > data) {
if(rchild == NIL) {
return NIL;
} else {
return rchild->search(value);
}
} else {
if(lchild == NIL) {
return NIL;
} else {
return lchild->search(value);
}
}
}
template <typename Type>
SBTNode<Type>* SBTNode<Type>::predecessor() {
SBTNode<Type>* temp = lchild;
while(temp != NIL && temp->rchild != NIL) {
temp = temp->rchild;
}
return temp;
}
template <typename Type>
SBTNode<Type>* SBTNode<Type>::successor() {
SBTNode<Type>* temp = rchild;
while(temp != NIL && temp->lchild != NIL) {
temp = temp->lchild;
}
return temp;
}
template <typename Type>
void SBTNode<Type>::remove_node(SBTNode<Type>* delete_node) {
SBTNode<Type>* temp = NIL;
if(delete_node->lchild != NIL) {
temp = delete_node->lchild;
temp->father = delete_node->father;
delete_node->lchild = NIL;
}
if(delete_node->rchild != NIL) {
temp = delete_node->rchild;
temp->father = delete_node->father;
delete_node->rchild = NIL;
}
if(delete_node->father->lchild == delete_node) {
delete_node->father->lchild = temp;
} else {
delete_node->father->rchild = temp;
}
temp = delete_node;
while(temp != NULL) {
temp->size--;
temp = temp->father;
}
delete delete_node;
}
template <typename Type>
bool SBTNode<Type>::remove(Type value) {
SBTNode<Type> * delete_node, * current_node;
current_node = search(value);
if(current_node == NIL) {
return false;
}
if(current_node->lchild != NIL) {
delete_node = current_node->predecessor();
cout << delete_node->data << endl;
} else if(current_node->rchild != NIL) {
delete_node = current_node->successor();
} else {
delete_node = current_node;
}
current_node->data = delete_node->data;
current_node->ADD = delete_node->ADD;
remove_node(delete_node);
return true;
}
// 可在以下添加 SBTNode 的遍历方法
template <typename Type>
void SBTNode<Type>::LDR(SBTNode<Type> *node) {
if(node != NIL) {
LDR(node->lchild);
cout << node->data << " ";
LDR(node->rchild);
}
}
//求解第K小
template <typename Type>
int SBTNode<Type>::select(int k) {
int rank = lchild->size + 1;
if(rank == k) {
return data;
} else if(rank > k) {
return lchild->select(k);
} else {
return rchild->select(k - rank);
}
}
//返回值为指针的求解第K小
template <typename Type>
SBTNode<Type> * SBTNode<Type>::selectSBTNode(int k) {
int rank = lchild->size + 1;
if(rank == k) {
return this;
} else if(rank > k) {
return lchild->selectSBTNode(k);
} else {
return rchild->selectSBTNode(k - rank);
}
}
//后序遍历删除
template <typename Type>
void SBTNode<Type>::remove_LRD(SBTNode<Type> *node) {
if(node != NIL) {
remove_LRD(node->lchild);
remove_LRD(node->rchild);
remove_node(node);
}
}
//与启发式合并相关函数---节点插入
template <typename Type>
SBTNode<Type>* Pre_insert(SBTNode<Type>* node, SBTNode<Type>* rest) {
node->size++;
if(rest->data > node->data) {
if(node->rchild == NIL) {
node->rchild = new SBTNode<Type>(rest->data, 1, node);
} else {
node->rchild = Pre_insert(node->rchild, rest);
}
} else {
if(node->lchild == NIL) {
node->lchild = new SBTNode<Type>(rest->data, 1, node);
} else {
node->lchild = Pre_insert(node->lchild, rest);
}
}
return maintain(node, rest->data > node->data);
}
/***********以下为二叉搜索树SBT的函数************/
template <typename Type>
BinaryTree<Type>::BinaryTree() {
root = NULL;
}
template <typename Type>
BinaryTree<Type>::~BinaryTree() {
delete root;
}
template <typename Type>
void BinaryTree<Type>::insert(Type value) {
if(root == NULL) {
root = new SBTNode<Type>(value, 1);
return ;
} else if(root->search(value) == NIL) {
root = ::insert(root, value);
return ;
}
if(SAME) {
root = ::insert(root, value);
return ;
}
}
template <typename Type>
bool BinaryTree<Type>::find(Type value) {
if(root->search(value) == NIL) {
return false;
} else {
return true;
}
}
template <typename Type>
bool BinaryTree<Type>::remove(Type value) {
return root->remove(value);
}
// 可在以下添加 BinaryTree 遍历方法
template <typename Type>
void BinaryTree<Type>:: LDR() {
root->LDR(root);
}
//求解第K小
template <typename Type>
int BinaryTree<Type>::select(int k) {
return root->select(k);
}
//返回指针的求解第K小
template <typename Type>
SBTNode <Type> * BinaryTree<Type>::selectSBTNode(int k) {
return root->selectSBTNode(k);
}
//删除某个子树包含自己节点
template <typename Type>
bool BinaryTree<Type>::remove_root(Type value) {
SBTNode <Type> * now = root->search(value);
if(now == NULL || now == NIL) {
return false;
}
root -> remove_LRD(now);
root->lchild = maintain(root->lchild, false);
root->rchild = maintain(root->rchild, true);
root = maintain(root, false);
root = maintain(root, true);
return true;
}
//二分查找某个数是第k小的数或大于等于 O(log n * log n)
//flag == true 返回大于等于的值 flag == false 返回大于等于的K
template <typename Type>
int BinaryTree<Type>::BMK(int value, bool flag) {
int l = 1, r = root->size;
while(1) {
int mid = (l + r) / 2;
if(root->select(mid) == value) {
if(flag)
return value;
else
return mid;
}
if(root->select(mid) > value && root->select(mid - 1) < value) {
if(flag)
return root->select(mid);
else
return mid;
}
if(root->select(mid) > value) {
r = mid - 1;
}
if(root->select(mid) < value) {
l = mid + 1;
}
}
}
//与启发式合并关联函数---节点插入
template <typename Type>
void BinaryTree<Type>::Pre_insert(SBTNode<Type> *node) {
if(root == NULL) {
root = new SBTNode<Type>(node->data, 1);
return ;
} else if(root->search(node->data) == NIL) {
root = ::Pre_insert(root, node);
return ;
}
if(SAME) {
root = ::Pre_insert(root, node);
return ;
}
}
//与启发式合并相关函数---后序遍历
template <typename Type>
void BinaryTree<Type>::Pre_LRD(SBTNode<Type> *root, SBTNode<Type> *node) {
if(node != NIL) {
Pre_LRD(root, node->lchild);
Pre_LRD(root, node->rchild);
Pre_insert(node);
}
}
//启发式 合并某个子树到某个节点
template <typename Type>
void BinaryTree<Type>::Pre_add_root(SBTNode<Type> *node) {
Pre_LRD(root, node);
}
/********************自定义函数区*******************/
int main() {
BinaryTree<int>BT;
int n;
cin >> n;
for(int i = 0; i < n; i++) {
int t;
cin >> t;
BT.insert(t);
}
BT.LDR();
return 0;
}
