平衡树
平衡树？何方神圣平时我们最害怕的是什么！暴力，没错，暴力的的时间复杂度通常会高得可怕，甚至使你一分不得，在“树论”上也是一样的，倘若使用普通的暴力，很难应对极端情况（比如退化成链或者接近于链），那有没有什么方法来优化掉树上暴力呢？设想一下：树上暴力之所以时间复杂度高，还不是因为树长得太奇怪了？既然改变不了自身，那就改变环境！构造一棵较为平衡的树就行了嘛（正所谓错的不是我而是这棵树啊）。
说的好，但如何构造一棵较为平衡的树呢？这意味着最好我从任意一个叶子节点出发，不超过 \(\log n\) 次就能到达根节点，而这又意味着每次向上规模至少 \(\times 2\) ，即树的任意一个节点的左右子树（因为是二叉树）大小的绝对值不超过 \(1\) 。这样构造出来的树相对比较平衡。
平衡树的插入操作
好不容易知道怎么构建一棵平衡树，现在又怎么维护它的平衡性呢？我们知道，如果在现有平衡树的基础上若尝试插入一个节点，大概率会使得这一颗树失去平衡性，久而久之就会退化成一条链（真是太可怕了），因此我们要尝试维护一棵树的平衡性！怎么维护呢？首先，我们令这个插入的破坏了树的平衡性的节点叫做麻烦节点（确实麻烦），而被这个麻烦节点破坏了平衡性的节点我们叫做被破坏节点（无论如何一定包含根节点）。那么被破坏节点和麻烦节点的关系只有可能是以下四种可能：
[*]LL型，当前麻烦节点是距离当前麻烦节点最近的被破坏节点的左儿子的左儿子的子树（或本身），那么需要一次右旋（一会会讲）。
[*]RR型，当前麻烦节点是距离当前麻烦节点最近的被破坏节点的右儿子的右儿子的子树（或本身），那么需要一次左旋（一会也会讲）。
[*]LR型，当前麻烦节点是距离当前麻烦节点最近的被破坏节点的左儿子的右儿子（或本身），那么需要先一次右旋，接着一次左旋（顺序很重要！）。
[*]RL型，当前麻烦节点是距离当前麻烦节点最劲的被破坏节点得到右儿子的左儿子（或本身），那么需要先一次左旋，接着一次右旋（顺序同样很重要！）。
那什么是左旋/右旋呢？过程很简单，一张GIF动图就懂了！
右旋：
左旋:
看懂了吗，以下是对这两种操作的详细讲解：
右旋
由上图可知，我们先把旧根节点叫做 \(u\) ，新的根节点叫做 \(v\) ，注意：若要右旋，则 \(u\) 到 \(v\) 之间必有一条连边，且 \(v\) 是 \(u\) 的左孩子（没有右旋）。
此时，我们把 \(v\) 提上来叫做根节点，\(u\) 变成其右儿子。然后把原来 \(v\) 的整个右子树（没有就不管），变成 \(u\) 的现在的右子树。
举个核桃
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]