红黑树的原理以及实现 红黑树 目录红黑树红黑树基于二叉查找树的附加特性1. 数据结构2. 左旋以及右旋2.1 左旋2.2 右旋3. 插入4. 删除测试原树（上右下左）删除53删除23删除54添加67代码： 红黑树基于二叉查找树的附加特性 节点是红色或黑色。 根节点是黑色。 每个叶子节点都是黑色的空节点（叶子结点指为空的叶子结点）。 每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。 1. 数据结构 2. 左旋以及右旋 2.1 左旋 
2.2 右旋 
3. 插入 新插入的节点（newNode）为红色。 按照二分查找树插入规则插入。 分情况讨论（以下情况基本都是为了保持上文所讲的的红黑树特性4和特5） 1、若newNode为根节点，则变为黑色，插入完毕，返回 true。 2、若newNode父节点为黑色，则插入完毕，返回 true。 3、如下图所示，若newNode父节点为红色，且叔叔节点存在且为红色，则父节点与叔叔节点变为黑色，祖父节点变为红色，newNode = 祖父节点。 
4、如下图所示，若newNode父节点为红色，叔叔节点不存在或为黑色，且newNode为父节点右孩子，父节点为祖父节点左孩子，则以父节点为轴左旋，进入情况6. 
5、如下图所示，若newNode父节点为红色，叔叔节点不存在或为黑色，且newNode为父节点左孩子，父节点为祖父节点右孩子，则以父节点为轴右旋，进入情况7 
6、如下图，此时以祖父节点为轴进行右旋，将祖父节点变为红色，newNode变为黑色。 
7、如下图，此时以祖父节点为轴进行左旋，将祖父节点变为红色，newNode变为黑色。 
4. 删除 分情况讨论（和插入一样，以下情况基本都是为了保持上文所讲的的红黑树特性4和特5） 如下图，如果待删除节点B有两个非空的孩子节点，转化成待删除节点只有右孩子（或没有孩子）的情况，习惯性选取待删除节点右子树最小节点E替换待删除节点（只是值替换，颜色不变），并将待删除节点变为E。 
根据待删除节点和唯一子节点颜色，分情况处理： 自身O是红色，子节点N是黑色，直接删除。 自身O是黑色，子节点N是红色，直接删除并将子节点N变为黑色。 自身O是黑色，子节点N不存在(不存在即子节点为空黑色节点，也可以用来判断)或也是黑色，较为复杂，先删除，再分情况讨论： 1、N是根节点，则不需要调整。 2、如下图，N的父亲、兄弟、侄子都是黑色，则将兄弟变为红色，父亲视作N，进行递归处理。 
3、（存在镜像）N的兄弟节点是红色，且N为父亲节点左儿子，则以父亲节点为轴左旋（否则右旋），并将旋转后N的祖父节点变为黑色，N的父节点变为红色，进入情况4,5或6. 
4、N的父亲节点是红色，兄弟和侄子节点是黑色，父亲节点变为黑色，兄弟节点变为红色。 
5、（存在镜像）N的父节点颜色随意，兄弟节点为父节点黑色右孩子，左侄子节点为红色，右侄子节点为黑色，以兄弟节点为轴进行右旋，将旋转后N的兄弟节点变为黑色，N的右侄子节点变为红色，进入情况6 
6、（存在镜像）N的父节点随意，兄弟节点为父节点的黑色右儿子，右侄子节点为红色，以N的父节点为轴进行左旋，左旋后的N的祖父节点变为父节点颜色，父节点变黑，叔叔节点变黑。 
测试 原树（上右下左） 
删除53 
删除23 
删除54 
添加67 
代码： https://github.com/DEUSJIN/RBTree
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/78271.html
