平衡树(自平衡二叉排序树)前提是一棵二叉排序树。

如果把结点 1、2、3、4、5 依次插入到二叉排序树,得到的结果:

很明显这棵树已经退化为链表,效率降低,需要改进。经过调整得到如下,效率高了不少。

AVL Tree

自平衡条件:平衡因子 = 左子树层数 – 右子树层数,平衡因子为0、±1 的结点被认为是平衡的。

插入(或删除)新结点后,如果不满足自平衡条件,就要进行旋转操作。

旋转操作分四种:

  • LL 型:如果新增元素插入到左儿子的左子树中,则进行右旋操作。
  • LR 型:如果新增元素插入到左儿子的右子树中,则进行左旋加右旋操作。
  • RR 型:如果新增元素插入到右儿子的右子树中,则进行左旋操作。
  • RL 型:如果新增元素插入到右儿子的左子树中,则进行右旋加左旋操作。

举例说明 RR 型(LL 型同理)

插入元素 6 后,不再平衡,左旋得到:

注意除了单纯的旋转使 4 变为根结点以外,原 4 的左孩子 3 接到了 2 的右子树上。

举例说明 LR 型(RL 型同理)

插入元素 3 后,不再平衡,先左旋得到:

再右旋得到如下,完美。

SB Tree (Size Balanced Tree, Not Shabi Tree!)

自平衡条件:每个结点所在子树的结点个数不小于其兄弟的两个孩子所在子树的结点个数。

和 AVL 树不同,AVL 树比较的是层数,而SB 树比较的是 Size ,结点的多少。

另一个和 AVL 不太一样的是,SBTree 只有在插入时才可能触发调整,而不需要在删除结点以后进行调整。

旋转操作类似于 AVL 树。

#include <iostream>
 
using namespace std;
 
class SBTNode {
public:
	int data, size, value;
	SBTNode *lchild, *rchild, *father;
	SBTNode(int init_data, int init_size = 0, SBTNode *init_father = NULL);
	~SBTNode();
	void insert(int value);
	SBTNode *search(int value);
	SBTNode *predecessor();
	SBTNode *successor();
	void remove_node(SBTNode *delete_node);
	bool remove(int value);
};
 
class BinaryTree {
private:
	SBTNode *root;
public:
	BinaryTree();
	~BinaryTree();
	void insert(int value);
	bool find(int value);
	bool remove(int value);
};
 
SBTNode ZERO(0);
SBTNode *ZPTR = &ZERO;
 
SBTNode::SBTNode(int init_data, int init_size, SBTNode *init_father) {
	data = init_data;
	size = init_size;
	lchild = ZPTR;
	rchild = ZPTR;
	father = init_father;
}
 
SBTNode::~SBTNode() {
	if (lchild != ZPTR) {
		delete lchild;
	}
	if (rchild != ZPTR) {
		delete rchild;
	}
}
 
SBTNode *left_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;
	temp->size = node->size;
	node->size = node->lchild->size + node->rchild->size + 1;
	return temp;
}
 
SBTNode *right_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;
	temp->size = node->size;
	node->size = node->lchild->size + node->rchild->size + 1;
	return temp;
}
//node表示要调整子树的根结点,flag用来标记是处理左子树更高的情况还是右子树更高的情况
SBTNode *maintain(SBTNode *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) {// RL 的情况
			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;
}
 
SBTNode *insert(SBTNode *node, int value) {
	if (value == node->data) {
		return node;
	}
	else {
		node->size++;
		if (value > node->data) {
			if (node->rchild == ZPTR) {
				node->rchild = new SBTNode(value, 1, node);
			}
			else {
				node->rchild = insert(node->rchild, value);
			}
		}
		else {
			if (node->lchild == ZPTR) {
				node->lchild = new SBTNode(value, 1, node);
			}
			else {
				node->lchild = insert(node->lchild, value);
			}
		}
	}
	return maintain(node, value > node->data);
}
 
SBTNode *SBTNode::search(int value) {
	if (data == value) {
		return this;
	}
	else if (value > data) {
		if (rchild == ZPTR) {
			return ZPTR;
		}
		else {
			return rchild->search(value);
		}
	}
	else {
		if (lchild == ZPTR) {
			return ZPTR;
		}
		else {
			return lchild->search(value);
		}
	}
}
 
SBTNode *SBTNode::predecessor() {
	SBTNode * temp = lchild;
	while (temp != ZPTR && temp->rchild != ZPTR) {
		temp = temp->rchild;
	}
	return temp;
}
 
SBTNode *SBTNode::successor() {
	SBTNode *temp = rchild;
	while (temp != ZPTR && temp->lchild != ZPTR) {
		temp = temp->lchild;
	}
	return temp;
}
 
void SBTNode::remove_node(SBTNode *delete_node) {
	SBTNode *temp = ZPTR;
	if (delete_node->lchild != ZPTR) {
		temp = delete_node->lchild;
		temp->father = delete_node->father;
		delete_node->lchild = ZPTR;
	}
 
	if (delete_node->rchild != ZPTR) {
		temp = delete_node->rchild;
		temp->father = delete_node->father;
		delete_node->rchild = ZPTR;
	}
	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;
}
 
bool SBTNode::remove(int value) {
	SBTNode *delete_node, *current_node;
	current_node = search(value);
	if (current_node == ZPTR) {
		return false;
	}
	size--;
	if (current_node->lchild != ZPTR) {
		delete_node = current_node->predecessor();
	}
	else if (current_node->rchild != ZPTR) {
		delete_node = current_node->successor();
	}
	else {
		delete_node = current_node;
	}
	current_node->data = delete_node->data;
	remove_node(delete_node);
	return true;
}
 
BinaryTree::BinaryTree() {
	root = NULL;
}
 
BinaryTree::~BinaryTree() {
	if (root != NULL) {
		delete root;
	}
}
 
void BinaryTree::insert(int value) {
	if (root == NULL) {
		root = new SBTNode(value, 1);
	}
	else {
		root = ::insert(root, value);
	}
}
 
bool BinaryTree::find(int value) {
	if (root->search(value) == NULL) {
		return false;
	}
	else {
		return true;
	}
}
 
bool BinaryTree::remove(int value) {
	return root->remove(value);
}
 
int main() {
	BinaryTree binarytree;
	int arr[10] = { 8, 9, 10, 3, 2, 1, 6, 4, 7, 5 };
	for (int i = 0; i < 10; i++) {
		binarytree.insert(arr[i]);
	}
	int value;
	cin >> value;
	if (binarytree.find(value)) {
		cout << "search success!" << endl;
	}
	else {
		cout << "search failed!" << endl;
	}
	cin >> value;
 
	if (binarytree.remove(value)) {
		cout << "delete success!" << endl;
	}
	else {
		cout << "delete failed!" << endl;
	}
	return 0;
}