红黑树 川长思鸟来 2021-10-24 01:48 392阅读 0赞 二叉查找树（BST） 1.**左**子树上所有结点的值均**小于或等于**它的根结点的值。 2.**右**子树上所有结点的值均**大于或等于**它的根结点的值。 3.左、右子树也分别为二叉排序树。 下图为一个二叉查找树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70][] 在插入节点时，会造成 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 1][] 从而使得查找速度大打折扣，几乎变成了线性结构。 解决二叉查找树多次插入新节点的不平衡问题有红黑树，AVL树，树堆…… 下面介绍一下红黑树： 红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的基本特性为还具有下列特性： 1.节点是红色或黑色。 2.根节点是黑色。 3.每个叶子节点都是黑色的空节点（NIL节点）。 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 下图中这棵树，就是一颗典型的红黑树： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 2][] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70]: /images/20211023/6c25b3aa39d845749ba16cc0f7cbc087.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 1]: /images/20211023/710c9eda32074878846f7550c4b00e81.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 2]: /images/20211023/9079d89d1ae440d891b8aebe5dcf3c58.png
相关 红黑树 [https://baijiahao.baidu.com/s?id=1641940303518144126&wfr=spider&for=pc][https_baijiahao 水深无声/ 2023年07月12日 03:41/ 0 赞/ 18 阅读
相关 红黑树 红黑树也是一颗平衡二叉树，平衡二叉树参考文章[平衡二叉树][Link 1] 红黑树基本介绍 红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf B Love The Way You Lie/ 2023年07月12日 03:39/ 0 赞/ 21 阅读
相关 红黑树 红黑树的定义 每个节点要么是红色，要么是黑色。 根节点必须是黑色， 每个叶子节点是黑色（叶子节点包含NULL）。 红色节点不能连续（红色节点的孩子和父亲 Dear 丶/ 2022年12月13日 04:18/ 0 赞/ 8 阅读
相关 红黑树 红黑树（Red Black Tree） 是一种自平衡二叉查找树，红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，它虽然 谁践踏了优雅/ 2022年06月15日 12:57/ 0 赞/ 482 阅读
相关 红黑树 > 3.3 Balanced Search Trees > [http://algs4.cs.princeton.edu/33balanced/][http_algs4.c ╰+攻爆jí腚メ/ 2022年06月09日 12:48/ 0 赞/ 345 阅读
相关 红黑树 红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在[计算机][Link 1]科学中用到的一种[数据结构][Link 2]，典型的用途是实现[关联数组][Lin 刺骨的言语ヽ痛彻心扉/ 2022年04月23日 12:06/ 0 赞/ 288 阅读
相关 红黑树 红黑树 概念 红黑树，又被称为对称二叉B树。 [红黑树模型][Link 1] 其本质是一种二叉查找树，单它在二叉查找树的基础上额外添加了一个标记（颜色），同时具 拼搏现实的明天。/ 2022年04月10日 02:39/ 0 赞/ 437 阅读
相关 红黑树 先Mark，后续补充： [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58 柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 341 阅读
相关 红黑树 二叉查找树（BST） 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下 川长思鸟来/ 2021年10月24日 01:48/ 0 赞/ 393 阅读
相关 红黑树 1. 从 2-3 树说起 一棵标准的 BST （二叉查找树 / 二叉搜索树）是长这个样子的： BST 其中，这棵二叉查找树中的每个结点也叫 2-结点 ，2-结点 就表示树... 系统管理员/ 2020年11月29日 04:30/ 0 赞/ 834 阅读
水深无声
╰+攻爆jí腚メ
刺骨的言语ヽ痛彻心扉
柔情只为你懂
系统管理员
还没有评论，来说两句吧...