qidao123.com技术社区-IT企服评测·应用市场

标题: 平衡树 [打印本页]

作者: 商道如狼道 时间: 2025-5-2 18:06
标题: 平衡树
平衡树？何方神圣

平常我们最害怕的是什么！暴力，没错，暴力的的时间复杂度通常会高得可怕，甚至使你一分不得，在“树论”上也是一样的，倘若利用平凡的暴力，很难应对极端环境（比如退化成链或者接近于链），那有没有什么方法来优化掉树上暴力呢？设想一下：树上暴力之以是时间复杂度高，还不是因为树长得太奇怪了？既然改变不了自身，那就改变环境！构造一棵较为平衡的树就行了嘛（正所谓错的不是我爱是这棵树啊）。
说的好，但如何构造一棵较为平衡的树呢？这意味着最好我从任意一个叶子节点出发，不超过 \(\log n\) 次就能到达根节点，而这又意味着每次向上规模至少 \(\times 2\) ，即树的任意一个节点的左右子树（因为是二叉树）巨细的绝对值不超过 \(1\) 。这样构造出来的树相对比较平衡。
平衡树的插入操作

好不轻易知道怎么构建一棵平衡树，如今又怎么维护它的平衡性呢？我们知道，如果在现有平衡树的基础上若尝试插入一个节点，大概率会使得这一颗树失去平衡性，久而久之就会退化成一条链（真是太可怕了），因此我们要尝试维护一棵树的平衡性！怎么维护呢？首先，我们令这个插入的粉碎了树的平衡性的节点叫做贫苦节点（确实贫苦），而被这个贫苦节点粉碎了平衡性的节点我们叫做被粉碎节点（无论如何肯定包含根节点）。那么被粉碎节点和贫苦节点的关系只有可能是以下四种可能：

LL型，当前贫苦节点是距离当前贫苦节点最近的被粉碎节点的左儿子的左儿子的子树（或自己），那么必要一次右旋（一会会讲）。
RR型，当前贫苦节点是距离当前贫苦节点最近的被粉碎节点的右儿子的右儿子的子树（或自己），那么必要一次左旋（一会也会讲）。
LR型，当前贫苦节点是距离当前贫苦节点最近的被粉碎节点的左儿子的右儿子（或自己），那么必要先一次右旋，接着一次左旋（顺序很重要！）。
RL型，当前贫苦节点是距离当前贫苦节点最劲的被粉碎节点得到右儿子的左儿子（或自己），那么必要先一次左旋，接着一次右旋（顺序同样很重要！）。
那什么是左旋/右旋呢？过程很简单，一张GIF动图就懂了！

右旋：

左旋:

看懂了吗，以下是对这两种操作的详细讲解：
右旋

由上图可知，我们先把旧根节点叫做 \(u\) ，新的根节点叫做 \(v\) ，注意：若要右旋，则 \(u\) 到 \(v\) 之间必有一条连边，且 \(v\) 是 \(u\) 的左孩子（没有右旋）。
此时，我们把 \(v\) 提上来叫做根节点，\(u\) 变成其右儿子。然后把原来 \(v\) 的整个右子树（没有就不管），变成 \(u\) 的如今的右子树。
举个核桃
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)