RB-Tree详解
红黑树具有很优秀的特性，其自平衡性特性，局部调整特性使得红黑树插入，删除，以查找，以及这些过程的内存资源的占用，的综合性能是非常高的（通常我们会拿红黑树和AVL树进行对比）。
对于红黑树的这些特性，在此不再赘述。我们在此讨论红黑树的插入，删除的过程。
先讨论插入过程：
1 插入节点为根结点，则红色变黑色
2 插入节点的父亲节点为黑节点，则插入节点为红色节点，不需要变色
3 若爷爷节点为根节点，父亲节点和叔叔节点为红色，则，插入节点仍为红色，父亲节点和叔父节点变为黑色，爷爷节点仍然为黑色（根结点必须为黑色）
4 若爷爷节点不是根节点，父亲节点和叔叔节点为红色，则，插入节点仍为红色，父亲节点和叔父节点变为黑色，爷爷节点变为红色。
5 插入节点的 父亲节点为红色，父亲的兄弟，即叔叔节点为黑色时（没有叔叔节点时，叶子节点存在，且也为黑色），此时要经过旋转变换。
上述插入的是节点40
上述是插入节点70
可见，针对情况五，是存在不同情况的。需要区分插入的节点是父亲节点的左节点，还是右节点。
如果是左节点，围绕插入节点的父亲节点向右旋转，父亲节点变成黑色，新插入的节点和爷爷节点变成黑色节点
如果是右子节点，需要经过两次旋转，使得插入节点旋转为父亲节点，并变为黑色，插入节点的父亲节点和爷爷节点变为红色儿子节点
版权声明：本文为shaonianpi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。