如何构建成一个红黑树 柔光的暖阳◎ 2021-12-16 06:17 144阅读 0赞 一：红黑树的五点特质： 1、每个节点都只能是红色或者黑色 2、根节点是黑色 3、每个叶节点（NIL节点，空节点）是黑色的。 4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。 5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 二：以下五种情况涵盖了**绝大部分（杠精绕行）**的新增可能，不管这棵红黑树多么复杂，都可以根据这五种情况来进行生成： 1：若新插入的节点N没有父节点，则直接当做根据节点插入即可，同时将颜色设置为黑色。 ![20190705112831505.png][] 2:父节点为黑色(C)，并且新增节点(A)为父节点的左子节点，可以直接插入，也不会打乱红色树的五大特质。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70][] 3若父节点A和叔父节点B都是红色，父节点的父节点C是黑色，这样就不能直接插入了，设置节点A和B为黑色，设置节点C为红色,这样满足条件，但是C节点的父节点或许也是红色，这样以C节点为新增节点，向上进行调整。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 2][] 4：这种情况多数是由情况三变色，向上调整所出现情况。新增节点为父节点A的左子节点，并且都为红色，新增节点的父节点的父节点C为黑色，叔叔节点B为黑色或者NIL。这样以节点C为中心进行右单旋并着色。相反进行左单旋并着色。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 4][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 5][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 6][] 5：这种情况多数是由情况三变色，向上调整所出现情况。新增节点为父节点A的右子节点，父节点A为父节点的父节点C的左子节点。首先以父节点A为中心经行左单旋，然后以父节点A的父节点C为中心进行右单旋。相反则先以父节点A为中心右旋，然后再以节点C为中心左旋。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 7][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 8][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 9][] [20190705112831505.png]: /images/20211214/e2142dd3d1ca41afa51aa56b366e00ce.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70]: /images/20211214/82182ba3a72d4fc18be750fe315239da.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190705140300937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 2]: /images/20211214/d1b1d049d7e347799f5ee84ff17234ae.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190705140551813.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 4]: /images/20211214/6cddb536c00a4da29e99f063ea0c12af.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190705141016667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 6]: /images/20211214/bb08f1709d9d4f968f4e16e5a5e51d67.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20190705141615435.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20190705141659313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 9]: /images/20211214/294ca458fab44a43ae3f688a2be6dced.png
相关 红黑树 [https://baijiahao.baidu.com/s?id=1641940303518144126&wfr=spider&for=pc][https_baijiahao 水深无声/ 2023年07月12日 03:41/ 0 赞/ 22 阅读
相关 树：红黑树 1，红黑树引入 红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1，超过后需要进行左旋或者右旋操作再次对树进行平衡，虽然这样能够解决二叉树退化为链表的缺 ╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 144 阅读
相关 红黑树 红黑树的定义 每个节点要么是红色，要么是黑色。 根节点必须是黑色， 每个叶子节点是黑色（叶子节点包含NULL）。 红色节点不能连续（红色节点的孩子和父亲 Dear 丶/ 2022年12月13日 04:18/ 0 赞/ 13 阅读
相关 红黑树 红黑树（Red Black Tree） 是一种自平衡二叉查找树，红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，它虽然 谁践踏了优雅/ 2022年06月15日 12:57/ 0 赞/ 485 阅读
相关 红黑树 > 3.3 Balanced Search Trees > [http://algs4.cs.princeton.edu/33balanced/][http_algs4.c ╰+攻爆jí腚メ/ 2022年06月09日 12:48/ 0 赞/ 353 阅读
相关 红黑树 红黑树 概念 红黑树，又被称为对称二叉B树。 [红黑树模型][Link 1] 其本质是一种二叉查找树，单它在二叉查找树的基础上额外添加了一个标记（颜色），同时具 拼搏现实的明天。/ 2022年04月10日 02:39/ 0 赞/ 442 阅读
相关 红黑树 先Mark，后续补充： [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58 柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 346 阅读
相关 如何构建成一个红黑树 一：红黑树的五点特质： 1、每个节点都只能是红色或者黑色 2、根节点是黑色 3、每个叶节点（NIL节点，空节点）是黑色的。 4、如果一个结点是红的，则它两个子节点都是黑 柔光的暖阳◎/ 2021年12月16日 06:17/ 0 赞/ 145 阅读
相关 红黑树 二叉查找树（BST） 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下 川长思鸟来/ 2021年10月24日 01:48/ 0 赞/ 397 阅读
相关 红黑树 1. 从 2-3 树说起 一棵标准的 BST （二叉查找树 / 二叉搜索树）是长这个样子的： BST 其中，这棵二叉查找树中的每个结点也叫 2-结点 ，2-结点 就表示树... 系统管理员/ 2020年11月29日 04:30/ 0 赞/ 844 阅读
水深无声
╰+攻爆jí腚メ
柔情只为你懂
系统管理员
还没有评论，来说两句吧...