SBTree的概念以及代码实现

冷不防 2022-04-22 08:38 27阅读 0赞

SBTree与AVL树具有相同的概念,也具有相同的操作类似**自平衡,旋转操作和旋转的触发**这三方面介绍SBTree

SBTree严格遵循下列公式,如有违反,则需要通过相应的转置操作来达到平衡

### 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结点所在的子树个数,且两个公式必须同时满足

SIZE\[left\[left\[t\]\]\]可以表示成t->left->left,SIZE\[right\[left\[t\]\]\])可表示成t->left->right

这两个公式可能有点难理解:**简单来说就是每个结点所在的子树(分左子树和右子树)的结点个数不小于其兄弟的两个孩子所在子树的结点个数**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70][]

比如说39这个结点,它的右子树结点个数为2,它的兄弟结点的左右子树个数最大值为1,2>1,成立

但是,它的左子树结点个数为0,0<1,不能同时满足两个公式

所以这里39要进行左旋操作

SBTree的调整方法:

### (1)LL型:(SIZE\[left\[left\[t\]\]\] > size\[right\[t\]\]) ###

这种情况种,左子树的左子树比右子树个数要大,会发生不平衡,

首先对子树进行右旋操作,旋转后对t的右子树进行调整,之后再对子树t进行调整

### (2)LR型:(SIZE\[right\[left\[t\]\]\] > size\[right\[t\]\]) ###

首先对t的左子树执行左旋操作,再对t进行右旋操作,之后分别调整结点t的左右子树,最终调整整条子树

### (3)RR型:(SIZE\[right\[right\[t\]\]\] > size\[left\[t\]\]) ###

首先对t的右子树进行左旋,然后分别进行调整

### (4)RL型:(SIZE\[left\[right\[t\]\]\] > size\[left\[t\]\]) ###

首先对右子树进行右旋操作,然后对左子树进行左旋操作

**相关代码的实现**

我们在二叉搜索树的基础上增加左旋,右旋,维护功能,就实现了一个SBTree

首先给出左旋算法,

SBTNode* mleft_rotate(SBTNode* node) {  //左旋操作
    	SBTNode* temp = node->rchild;
    	node->rchild = temp->lchild;
    	temp->lchild->father = node;
    	temp->lchild = node;
    	temp->father = node->father;
    	node->father = temp;
    
    	return nullptr;
    }

右旋算法与左旋算法类似:

SBTNode* mright_rotate(SBTNode* node) {  //右旋操作
    	SBTNode* temp = node->lchild;
    	node->lchild = temp->rchild;
    	temp->rchild->father = node;
    	temp->rchild = node;
    	temp->father = node->father;
    	node->father = temp;
    
    	return nullptr;
    }

这两个算法相对来说比较好理解,作为模板记下即可,在旋转过后,我们还要对结点进行维护操作

SBTree的调整与优化:

在插入后,一共有4种除法旋转的情况,分为LL型,LR型,RR型,RL型,RR型

在我们之前给出的公式种:

### A:SIZE\[right\[t\]\] >= max(SIZE\[left\[left\[t\]\]\], SIZE\[right\[left\[t\]\]\]); ###

### B:SIZE\[left\[t\]\] >= max(SIZE\[left\[right\[t\]\]\], SIZE\[right\[right\[t\]\]\]); ###

LL,LR违反了平衡条件A，RR和RL违反了平衡条件B

对应的,LL,LR能够保证b成立,RR,RL能够保证a成立,所以条件就可以这样进行筛选

维护算法如下:

**(1)处理左子树更高的情况**

(1)LL型:右旋t

(2)LR型:左旋t的左子树,再右旋t

**(2)处理右子树更高的情况**

(1)RL型:右旋t的右子树,再左旋

(2)RR型:左旋t

**(3)递归进行相应的维护**

递归调整左子树中左子树的左子树更高的情况

递归调整右子树中右子树的右子树更高的情况

递归调整当前子树中左子树更高的情况

递归调整当前子树中右子树更高的情况

template <typename Type>
    SBTNode<Type>* maintain(SBTNode<Type>* node, bool flag) {
        
    	if (flag == false) {
    		if (node->lchild->lchild->size > node->rchild->size) {  //LL型树
    			node = right_rotate(node);
    		}
    		else if (node->lchild->rchild->size > node->rchild->size) {  //LR型树
    			node->lchild = left_rotate(node->lchild);
    			node = right_rotate(node);
    		}
    		else {
    			return node;  //正常结点,直接返回即可
    		}
    	}
    	else {
    		if (node->rchild->rchild->size > node->lchild->size) {  //RR型
    			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);
    	
    	maintain(node, false);
    	maintain(node, true);
    	
    	return node;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70]: /images/20220422/6af7f07eda3b4ef18cdb68f49db22f79.png