平衡二叉树-的四种旋转调整（代码，图解）

平衡二叉树-的四种旋转调整（代码，图解）

1.右单旋：

新插入节点插入在较高左子树的左侧（左左右），插入新节点二十：

1.修改parent和curLR的孩子指针域

parent->left = curLR;
// 避免左单支的场景：subLR是nullptr
if (subLR)
		   curLR->parent = parent;

2.修改parent和curL的指针域

curL->right = parent;

3.处理旋转之前parent的双亲的孩子

// 因为parent可能是某个节点的子树，因此在更新parent的双亲前必须先将其之前的双亲记录
		Node* pparent = parent->parent;
		parent->parent = curL;
		curL->parent = pparent;

		// parent可能是根节点：需要修改_root
		// parent也可能是一棵子树: 需要修改pparent的左/右指针域的指向
		if (nullptr == pparent)
		{
			// 旋转之前parent是根节点
			_root = subL;
		}
		else
		{
			// parent是某个节点的子树
			if (parent == pparent->left)
				pparent->left = curL;
			else
				pparent->right = curL;
		}

2.左单旋

新插入节点插入在较高右子树的右侧（右右左），插入新节点60

同理右单旋：

	void RotateLeft(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;

		parent->right = subRL;
		// 避免：右单支
		if (subRL)
			subRL->parent = parent;

		subR->left = parent;

		// 需要更新parent和subR的双亲
		Node* pparent = parent->parent;
		parent->parent = subR;
		subR->parent = pparent;

		// 旋转之前：
		// parent可能是根节点：修改_root的指向
		// parent可能是子树：修改原parent左||右指针域的指向
		if (nullptr == pparent)
		{
			_root = subR;
		}
		else
		{
			if (parent == pparent->left)
				pparent->left = subR;
			else
				pparent->right = subR;
		}
	}

3.左右双旋

新插入节点插入在较高左子树的右侧，先左旋调整为需要右旋的情况，再右旋

	void RotateLR(Node* parent)
	{
		RotateLeft(parent->left);
		RotateRight(parent);
	}

4.右左双旋

新插入节点插入在较高右子树的左侧，先右旋调整为需要左旋的情况，再左旋

	void RotateRL(Node* parent)
	{
		RotateRight(parent->right);
		RotateLeft(parent);
	}