AVL树的实现

AVL树

        avl其实并不算单独的树，它和map、set是密不可分的，逻辑上大体是相同的，不过它多了一个平衡因子的概念，也就是说，它是依靠平衡因子来决定自己是否失衡需要调整的。

我们可以看到它的结构和map、set并没有什么太大不同，不过多了一个bf的平衡因子和父节点。平衡因子的作用是为了决定自己是否失衡，而父节点则是决定了如果失衡，可以向上调整，类似于单链表进化成了双向链表。甚至于它的插入在不涉及旋转的部分都和前面的map/set一样。

还是老一套的插入，然后更改位置，只不过多了一个parent的修改。

旋转

单旋

这里才是AVL树的重头戏。我们插入之后，这棵树的平衡因子一定要更新，并且还不能只更新插入的那一个，得一直向上更新，来确保这棵树没有失衡。

到这一步都算是省事的插法，虽然略微失衡但是我们不需要去调整这棵树。

但是一旦有平衡因子更新到了2或者-2，就代表它失衡了，我们就得旋转来确保平衡。

我们先来了解旋转是怎么个原理的。

忽略我的垃圾画图技术，我们可以看出来这棵树虽然没有失衡，但是已经算亚健康了，所以假设我们在2的左边插入一个节点时，它就失衡了。

那么这就是完美的一边失衡，我们往右单旋就能解决问题，直接说太抽象了，看我画的图来了解怎么旋的。

首先把4给我们的根节点左边。

然后根节点变为3的右边，3成为新的根节点，这样就算旋转完了。

因为3在更新前就属于小于根节点的状态，并且它的右边大于3但是还是小于根节点5，所以它去替代3成为根节点的新左很合适。然后根节点再去当3的右也很合适。3就成为了新的根，这棵树就平衡了。并且我们可以发现旋转完之后高度恢复到了插入之前的状态，所以我们也不用向上调整，实在是方便。

但是代码就很麻烦，可以回忆一下双向链表的插入，需要改的地方有点多，这里就更多了。

//右单旋
	void RotateR(node* parent)
	{
		//传入的当父节点
		//那么父的左我们称为subl
		//左的右称为sublr
		node* subL = parent->_left;
		node* subLR = subL->_right;
		//然后就是第一步，把左的右也就是lr给parent的左当替代品
		parent->_left = subLR;
		//然后左的右变成parent
		subL->_right = parent;
		//看着好像搞完了，但是实际上差远了，我们的parent指向还没改呢 乱套了

		//首先parent变了，那么我们还得先记录一下parent的parent
		node* pparent = parent->_parent;
		//然后更新parent的parent为我们的subl 
		parent->_parent = subL;

		//然后考虑一下lr可能本来就是空的情况会野指针 所以用if判断改parent
		if (subLR)
		{
			subLR->_parent = parent;
		}
		//然后还得考虑parent可能是根的情况，那么subl就是新根了 也得改 并且subl的parent这种情况下就为空了
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		//不然parent就不是根
		else
		{
			//那我们还得分情况讨论，它是pparent左还是右 然后改过去
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
			subL->_parent = pparent;
			//最后根据旋转后的图所示，它旋转完之后的高度是降为0的 所以更新平衡因子
			parent->_bf = subL->_bf = 0;
		}
	}

我们可以看到说起来的操作好像简单，改改指向就好了，但是里面的弯弯绕绕是真多。

那有右单旋就有左单旋，它们的逻辑就是相反的。

//左单旋
	void RotateL(node* parent)
	{
		node* subR = parent->_right;
		node* subRL = subR->_left;
		parent->_right = subRL;
		subR->_left = parent;

		node* pparent = parent->_parent;
		parent->_parent = subr;

		if (subRL)
		{
			subRL->_parent = parent;
		}
		if (_root = parent)
		{
			_root = subR;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
			subR->_parent = pparent;
			parent->_bf = subR->_bf = 0;
		}
	}

能写右就能写出左来。

双旋

到这都算是happy end，最恶心的是接下来的，它失衡，但是它不往一边失衡，这种情况一个单旋已经解决不了问题了，继续看图

这是一颗更牛马的失衡树，我们用单旋的逻辑会发现它咋旋都不能变到某一边失衡，所以我们需要左右结合一下，再用分置思维来先处理局部再处理整体。

先对3来个左旋，这样就变成一边失衡的情况了，再给它来个右旋

就又平衡了。这个双旋其实就是左右或者右左单旋一下就好，但是它的平衡因子才是不好搞的地方。我们得考虑到它的多种情况。

//左右双旋
	void RotateLR(node* parent)
	{
		//还得先记录左和左的右
		node* subL = parent->_left;
		node* subLR = subL->_right;
		//但是旋完之后平衡因子就不准了 所以旋之前先记录
		//因为双旋的原因RL从孙子辈直接窜到爷爷辈去了
		int bf = subLR->_bf;
		//左旋右旋
		RotateL(parent->_left);
		RotateR(parent);
		//然后来判断平衡因子 如果等于0 好啊 旋之前就是平衡状态
		//也就是说可能亚健康插入个新节点 虽然整体失衡但是局部健康的情况
		if (bf == 0)
		{
			//那这简直完美的一棵树 全等于0
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		//不然就是我们推理的某一段从头到尾都失衡的情况 那么我们分为左或者右失衡
		//也就是往左或者右插入了一个节点 另一边为空的情况
		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		// bf== 1的情况就是上面的图的情况 那么它旋完
		//我们只需要修改根 左 左的右 这三个地方的平衡因子就好
		else if(bf == 1)
		{
			//咱看图平衡因子一目了然
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
	}

bf = 0 的情况图 

一颗很完美的平衡因子都等于0的树

bf = -1的情况

那么右左双旋和单旋一样，逻辑相反。

//右左双旋
	void RotateRL(node* parent)
	{
		
		node* subR = parent->_right;
		node* subRL = subR->_left;

		int bf = subRL->_bf;
	
		
		RotateR(parent->_right);
		RotateL(parent);

		
		if (bf == 0)
		{
			
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		

		else if (bf == -1)
		{
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		
		else if (bf == 1)
		{
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}

那么到这里，插入部分的核心已经都完成了。

收尾

找find

//find
	node* find(const K&key)
	{
		node* cur = _root;
		//往左右找过去
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			//找到了就返回
			else
			{
				return cur;
			}
		}
		//到这说明没找到 返回空
		return nullptr;
	}

计算个数size

//计算节点个数
	int _size(node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		return _size(root->_left) + _size(root->_right) + 1;
	}

判断是否是AVL树

//判断是否是AVL树
	bool _isBalanceTree(node* root)
	{
		if (root == nullptr)
		{
			//空树也是AVL树
			return true;
		}
		int lefthigh = _high(root->_left);
		int righthigh = _high(root->_right);

		int diff = righthigh - lefthigh;
		//如果计算的平衡因子和我们的平衡因子不一样就不是AVL树
		//且左右减的绝对值超过1也一定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << "高度不匹配" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << "平衡因子不匹配" << endl;
			return false;
		}
		//递归判断左右
		return _isBalanceTree(root->_left) && _isBalanceTree(root->_right);
	}

//高度
	int _high(node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int lefthigh = _high(root->_left);
		int righthigh = _high(root->_right);
		return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1;
	}

遍历 (中序)

//中序遍历
	void _inorder(node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_inorder(root->_right);
	}