近两日平衡二叉树和红黑树的心得
wpl13112682 · · 算法·理论
近两日平衡二叉树和红黑树的心得
这两天学习了平衡二叉树和红黑树这两个数据结构。平衡二叉树（AVL）是一种通过旋转根叶节点的操作维护树的平衡，防止相邻两层高差超过1产生链状结构的数据结构。平衡二叉树的优点在于可以快速的查找某个数，但是维护等操作比较麻烦。红黑树也是一种通过类似于平衡二叉树的旋转操作和颜色标记（红色、黑色）维持树的平衡的数据结构。红黑树的优点在于维护操作方便，所以删除与插入操作相对于平衡二叉树时间效率更快，但是查找没有平衡二叉树快捷。红黑树允许平衡因子绝对值大于1，颜色约束间接维持平衡。
平衡二叉树的核心操作之一就是判断旋转类型和调整旋转后的二叉树。我在学习平衡二叉树的过程中，也是旋转类型记得不扎实，需要多加练习。平衡二叉树的第二个核心操作是插入删除。
平衡二叉树的操作： ①旋转、调整。 旋转分为LL型、LR型、RR型、RL型四种。第一，记录旋转涉及的节点序号。第二，调整旋转后涉及到的节点的父子关系。最后，自下而上更新平衡因子和高度。 ②删除。 第一，在树上寻找需要删除的值。第二，找到第一个大于要删除的数的节点位置，并用找到的数替代要删的数的值。第三，删除找到的数原来的位置的节点。 ③更新平衡因子和高度（update函数)
这里update函数需要与balance函数进行区别。 balance函数是用来判断如何旋转的，update函数是用来真正更新每个节点的平衡因子和高度的。
在学习平衡二叉树的过程中，我的状态非常不好。这导致了上课的过程中，大家都被迫放慢速度保证我跟上进度（但是学习效果肯定不好，状态好的时候学习效果明显很好），以后上课的时候要提前调整一下状态，比如说可以提前预习了解一下当天上课要学习的内容，这样就不至于出现学习状态不好，拉垮进度的问题了。
红黑树有四条维护准则。①整棵树的根节点必须为黑色，并且整棵树的最底层节点必须为黑色（根底黑）②相邻的两层节点不能都是红色（不红红）③每条路径经过的黑色节点数相同（黑路同）④左根右从小到大的排列顺序（左根右）
红黑树还有一条条件：hmax<hmin2。但在维护过程中，只要满足红黑树四个条件，就能满足hmax<hmin2的条件。
红黑树的操作：
①插入修复。 所有插入的节点都默认为红色。插入修复有两种情况：第一种，插入的地方违反了不红红的规则，但插入节点的叔叔是红色。第二种，插入节点的叔叔是黑色。第一种情况，将叔叔、父亲与爷爷调换颜色。第二种情况，判断（不需要判断平衡因子，判断插入节点是父亲的右儿子还是左儿子）需要旋转的类型，将叔叔、爸爸、爷爷旋转。
实现（这里只有判断父亲是爷爷的左节点）：
int p = tree[z].fa;//p存储新增节点父亲的序号
int g = tree[p].fa;//g存储新增节点爷爷的序号
if (p == tree[g].l) { //父亲是爷爷的左节点
int u = tree[g].r;//u存储g的右儿子序号，新增节点的叔叔的序号
if (isRed(u)) {//若叔叔是红色，叔叔、父亲与爷爷调换颜色
tree[p].color = tree[u].color = BLACK;
tree[g].color = RED;
z = g;//z改成爷爷的序号
} else {
if (z == tree[p].r) { z = p; left(z); }//特判，LR型。先左旋父亲，再右旋爷爷。
tree[tree[z].fa].color = BLACK;
tree[tree[tree[z].fa].fa].color = RED;
right(tree[tree[z].fa].fa);
}最后注意，两两交换的时候，把红色换到root上了，返回 tree[root].color = BLACK;
学习平衡二叉树和红黑树的过程对我来说也是非常曲折，中间的泡泡也冒了不少，在以后学习新算法的过程中，还需要调整自己的状态，多问多想多练习，提高效率。