目录 一、概念 二、特性 三、接口实现 1、插入 情况一：p为黑，结束 情况二：p为红 1）叔叔存在且为红色 2）u不存在/u存在且为黑色 （1）p在左，u在右 （2）u在左，p在右 2、检查平衡 四、对红黑树的理解 五、原码 一、概念 红黑树：AVL树不好控制（严格平衡），所以推出了红黑树 不用高度控制平衡，用颜色 最长路径<= 最短路径*2 红黑树是近似平

@[TOC]红黑树 一 红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 简单来说红黑树通过了对颜色的控制进而对树的长度做出了限制，不再需要平衡因子。 红黑树性质 每个节点不是红色就是黑色根节点为黑色如果一个节点

文章目录 红黑树概念红黑树的性质红黑树 VS AVL树红黑树的结点与树的描述——定义类红黑树的插入操作步骤一：按照二叉搜索树的规则插入新结点步骤二：检测新节点插入后，红黑树的性质是否造到破坏情况一：uncle存在且为红情况二：uncle不存在或者uncle存在且为黑 验证一棵红黑树是否符合规则 红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色 ，

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。  目录 一、红黑树简介 1、红黑树的简介 2、红黑树的性质 二、红黑树的插入（看叔叔的颜色就行） 1、为什么新插入的节点必须给红色？ 2、插入红色节点后，判定红黑树性质是否被破坏 2.1情况一：