红黑树的基本概念

红黑树的基本概念

虽然平衡二叉树的查找效率很高 可是数据一旦多起来 构建平衡二叉树就太费力了 要来回孤岛很多次 对计算机的性能是一个很大的损耗，因此不长用于生产实际中 生产实际中运用较多的是一种 红黑树

红黑树 即兼顾了平衡二叉树的查找速率有兼顾了 对于计算机性能的损耗 所有他的限制是非常多的

1：红黑树的结点非黑即红；2：一个结点到自己后代节点路径上经过的黑结点数目是一样的

3：红黑树的叶子结点都是黑的 4：红黑树的跟结点是红的；5：如果一个结点是红色的那么他的子结点一定是黑色的。

红黑树没有一条路径的长度是其他路径的二倍，是内存中最优的数据结构 （兼顾了时间复杂度趋近logn也兼顾计算机损耗(调整 *** 作较小)）

红黑树的基本形式：

有一点需要注意 因为红色结点的子节点必定是黑色的那么要插入一个红色结点 那么他就必有两个叶子结点 叶子结点不用存放数据 可以理解为null

这是红黑树的基本形式： 方型的是叶子结点 存在但并没有存在数据（我自己的理解可以存数据但没必要 不如不存来的整洁）

插入 3