[数据结构与算法]2021-09-05 基于map-set 平衡搜索树（平衡因子）

//红黑树
//AVL树 平衡的二叉搜索树
//平衡因子 每个节点的左右子树的高度差
template
struct AVLNode
{

AVLNode<T>* _Left; // 该节点的左孩子
AVLNode<T>* _Right; // 该节点的右孩子
AVLNode<T>* _Parent; // 该节点的双亲
T _val;
int _bf; // 该节点的平衡因子

AVLNode(const T& _data = T())
	:_pParent(nullptr)
	, _Left(nullptr)
	, _Right(nullptr)
	, _val(val)
	, _bf(0)
{}

};

template
class AVLTree
{
public:
typedef AVLNode Node;

//插入的接口
bool insert(const T& val)
{
//二叉搜索树插入
	//现在是空树，可以直接进行插入
	if (_root == nullptr)
	{
		_root = new Node(val);
		return true;
	}

	//_root
	//*****************
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		parent = cur;
		//判断插入的值是否是已经存在的。
		if (cur->_val == val)
			return false;
		//使用的还是搜索二叉树的节奏就是左小右大
		else if (cur->_val > val)
			cur = cur->_left;
		else
			cur = cur->_right;
	}

	//平衡因子的调整
	cur = new Node(val)
		if (parent->_val > val)
			parent->_left = cur;
		else
			parent->_right = cur;
	cur->_parent = parent;

	//调整  从parent开始
	if (parent->_left == cur)
		--parent->_bf;
	else
		++parent->_bf;

	//更新父节点的平衡因子
	while (parent)
	{
    if(parent->_bf==0)  //parent的比较短的子树高度+1
	//结束更新
	else if (parent->_bf == 1 || parent->_bf == -1)
		//继续向上更新
	{
		//更新调整位置
		cur = parent;
		parent = parent->_parent;
	}

	//下边的情况就是表示的是需要对结构进行操作的情况（就是平衡因子更新的根节点时候，根节点的平衡因子已经是不平衡的）
	//使用的方法是旋转  目的通过调整结构就是让平衡因子缩小在范围控制（0-->+/-2）
	//旋转的实现是通过修改指针的指向来实现的。

	//****注意旋转的开始的点是-2/+2的点进行开始****
	else if (abs(parent->_bf) == 2)
	{
		if(parent->_bf) == -2&&cur->_bf==-1)
		{
		//左边的左边高、
		//右旋
		RotateR(parent)
        }
	}
	break;
	}
}
//插入成功
return true;


//右旋转
//          parent
//    subL
//          subLR

void RotateR((Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	subL->_right = parent;
	parent->_left = subLR;

	if (subLR)
		subLR->_parent = parent;

	//判断parent是不是根节点
	if (parent == _root)
	{
		//根节点
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
     Node* pparent = parent->_parent;
	if (pparent->_left == parent)
		pparent->_left = subL;
	else
		pparent->_right = subL;
	subL->_parent = pparent;

	
	}
	parent->_parent = subL;

	subL->_bf = parent->_bf = 0;
}


//注意旋转的话一定注意大方向的把握。才能书写正确的代码
//左旋
//  parent
//                  subR
//        subL
void RotateL((Node* parent)
{
	Node* subR=parent->_right;
	Node* subRL =subR->_left;

	subR->_left = parent;
	parent->_right = subRL;

	if (subRL)
		subRL->_parent = parent;

	//判断parent是不是根节点
	if (parent == _root)
	{
		//根节点
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		Node* pparent = parent->_parent;
		if (pparent->_left == parent)
			pparent->_left = subR;
		else
			pparent->_right = subR;
		subR->_parent = pparent;
	}
	parent->_parent = subR;
	//更新平衡因子。
	subL->_bf = parent->_bf = 0;
}

private:
Node* _root = nullptr;
};

void test()
{
AVLTree avl;
avl.insert(5);
avl.insert(3);
avl.insert(2);
avl.insert(1);
avl.insert(0);
avl.insert(-1);
}

int main()
{
test();
return 0;
}