别再让搜索树变竹竿！AVL 旋转四连招详解！

template<class K,class V>
struct AVLTreeNode {
    pair<K, V> _kv;					// 键值对
    AVLTreeNode<K, V>* _left;		// 指向左子树
    AVLTreeNode<K, V>* _right;		// 指向右子树
    AVLTreeNode<K, V>* _parent;		// 指向父节点
    int _bf;						// balanced factor 右子树高度-左子树高度

    // 构造
    AVLTreeNode(const pair<K,V>& kv)
        :_kv(kv)
            ,_left(nullptr)
            ,_right(nullptr)
            ,_parent(nullptr)
            ,_bf(0){ }
};
template<class K, class V>
class AVLTree{
public:
    typedef AVLTreeNode<K, V> Node;
private:
    Node* _root; 					// 根节点
};

// 插入节点
bool insert(const pair<K,V>& kv){
    // 1. 按照搜索树插入逻辑插入
    Node* cur = _root;
    Node* parent = nullptr; 		// 记录cur的父节点 便于插入后链接

    // 1> 查找合适的插入位置
    // 标准二分逻辑
    while(cur){
        if(kv.first < cur->_kv.first) {				// 小于往左走
            parent = cur;
            cur = cur->_left;
        }else if(kv.first > cur->_kv.first){		// 大于往右走
            parent = cur;
            cur = cur->_right;
        }else return false;							// 相同值不插入 保持搜索树的性质
    }

    // 2> 执行插入操作
    // cur的位置就是待插入位置
    Node* newNode = new Node(kv)
        if(parent->_left == cur) parent->_left = kv.first;
    else parent->_right = kv.first;

    // 2. 更新平衡因子
    /*
			cur插入之后，parent的平衡因子一定要调整
			插入之前， parent的平衡因子分为 0 1 -1 三种情况

			parent		    &
				           /
			newNode(左)   &
			cur插入到parent的左侧 parent._bf-1

			parent		    &
							 \
			newNode(右) 	  &
			cur插入到parent的左侧 parent._bf+1

			插入之后，parent的平衡因子可能有 0 +-1 +-2 这三种情况
			1> parent._bf==0  	说明插入之前为+-1 插入之后调整为0 满足AVL树 插入成功
			2> parent._bf==+-1 	说明插入前一定为0 插入之后调整为+-1 
								此时以parent为根的树高度增加 需要向上更新
			3> parent._bf==2	违反了AVL树性质 旋转处理
		*/

    while(parent){
        // 更新父节点的平衡因子
        if(cur == parent->_left) parent->_bf--;
        else parent->_right++;

        // 更新后检测父节点的平衡因子
        if(0 == parent->_bf) break; 	
        else if(1 == parent->_bf || -1 == parent->_bf){
            // 插入前父节点的平衡因子是0 说明是以parent为根的二叉树
            // 高度增加了一层 需要继续向上调整
            cur = parent;
            parent = cur->_parent;
        }
        else{
            // 父节点的平衡因子为+-2 旋转操作
            if(2 == parent->_bf){

            }else{

            }
        }

        return true;
    }

// 右旋
void rotateRight(Node* node){
    Node* child = node->_left;			// 失衡节点的左孩子
    Node* childKid = child->_right; 	// 失衡节点左孩子的右孩子
    Node* nodeParent = node->_parent;	// 失衡节点的父节点

    // 右旋操作 
    // 1). 以child为支撑点旋转 node成为child的右孩子
    // 2). childNext成为node的左孩子
    /*
		node -->	50                           30
				   /  \           右旋          /  \
		child --> 30  60        =====>        10   50
				 /  \                        /    /  \
				10  40 <-- childKid         0   40   60
			   /
			  0
		*/	

    // 1. 下沉node 提高child
    child->_right = node;
    node->_parent = child;

    node->_left = childKid;
    if(childKid) childKid->_parent = node;

    // 2.接回父节点和根
    child->_parent = nodeParent;
    if(nodeParent == nullptr) _root = child;
    else if(nodeParent->_left == node) nodeParent->_left = child;
    else nodeParent->_right = child;

    // 3. 更新平衡因子
    node->_bf = child->_bf = 0;
}

// 左旋
void rotateLeft(Node* node){
    Node* child = node->_right;			// 失衡节点的右孩子
    Node* childKid = child->_left; 		// 失衡节点左孩子的左孩子
    Node* nodeParent = node->_parent;	// 失衡节点的父节点

    // 左旋操作 
    // 1). 以child为支撑点旋转 node成为child的左孩子
    // 2). childNext成为node的右孩子
    /*
			node -->	 10									 40
						/  \								/  \
					   0   40    <--- child	 左旋	      10   50
						  /  \			    =====>		  /  \   \
		  childNext ---> 30  50				             0   30  60
							   \
							   60     		 
		*/

    // 1. 下沉node 提高child
    child->_left = node;
    node->_parent = child;

    node->_right = childKid;
    if(childKid) childKid->_parent = node;

    // 2.接回父节点和根
    child->_parent = nodeParent;
    if(nodeParent == nullptr) _root = child;
    else if(nodeParent->_left == node) nodeParent->_left = child;
    else nodeParent->_right = child;

    // 3. 更新平衡因子
    node->_bf = child->_bf = 0;
}

// 先左旋后右旋
void rotateLR(Node* node){
    Node* child = node->_left;
    Node* childKid = child->_right;
    int bf = childKid->_bf;

    rotateLeft(child);
    rotateRight(node);

    // 更新平衡因子
    if(0 == bf){
        child->_bf = 0;
        node->_bf = 0;
        childKid->_bf = 0;
    }
    else if(1 == bf){			// 右边插入
        child->_bf = -1;
        node->_bf = 0;
        childKid->_bf = 0;
    }
    else if(-1 == bf){			// 左边插入
        child->_bf = 0;
        node->_bf = 1;
        childKid->_bf = 0;
    }
    else assert(false);
}

// 先右旋后左旋
void rotateRL(Node* node){
    Node* child = ndoe->_right;
    Node* childKid = child->_left;
    int bf = childKid->_bf;			//  小孙子一路往上 平衡因子先记录下来

    rotateRight(child);
    rotateLeft(node);

    // 更新平衡因子
    if(0 == bf){		// 自己是新增
        child->_bf = 0;
        childKid->_bf = 0;
        node->_bf = 0;
    }
    else if(1 == bf){ // 右边插入
        child->_bf = 0;
        childKid->_bf = 0;
        node->_bf = -1;
    }
    else if(bf == -1){ // 左边插入
        child->_bf = 1;
        childKid->_bf = 0;
        node->_bf = 0;
    }
    else assert(false);
}