红黑树简单了解

先引入一个问题：

假设有一个大小为10, 000的数组，按大小进行排序，如 【1,3,8,15...】，假设我要在这个数组中查询是否存在 888 这个数字，那么这个算法我们要怎么写呢？

当然肯定有人会说，写个循环遍历一下不就好了吗？
这种做法不能说是错的，但是却不是最好的方法。

这里使用二分查找法的话，效率会更高的。

什么是二分查找法？

【内容来自百度百科】二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

以上的说法可能不够明确，我们来用上边的数组举个例子：

1. 我们首先将这个 10,000 大小的数组平均（大致平均，可能存在正负1的偏差）切分为两部分 也就是下标为 0 ~ 4999， 5000 ~ 9999
2. 取其中下标为5000的记录与 888 对比大小，如果等于则直接返回
3. 如果小于则对 0 ~ 4999 的部分继续执行切分比对的操作
4. 如果大于则对 5000 ~ 9999 的部分继续执行切分比对的操作

以上就是二分查找法的思想。

• 时间复杂度 为 O(log2n)

public static int binarySearch(Integer[] srcArray, int des) {
    //定义初始最小、最大索引
    int start = 0;
    int end = srcArray.length - 1;
    //确保不会出现重复查找，越界
    while (start <= end) {
        //计算出中间索引值
        int middle = (end + start)>>>1 ;//防止溢出
        if (des == srcArray[middle]) {
            return middle;
        //判断下限
        } else if (des < srcArray[middle]) {
            end = middle - 1;
        //判断上限
        } else {
            start = middle + 1;
        }
    }
    //若没有，则返回-1
    return -1;
}

---

二叉树简单了解

【 内容来自百度百科】二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树是遵循了一定的规则生成的一种数据结构，比如它的左子树的元素比根节点的元素要小，右子树的元素比根节点的元素要大。

二叉树的例子

但是对于这个二叉树，虽然可以方便地判定是我要找某一个数据的时候，需要往左边找还是右边找，但是显然会有一种特殊的情况，当插入的顺序在某一段时间内是按照大小顺序插入的时候，就会导致某二叉树不平衡。

不平衡的二叉树

显然对于不平衡的二叉树，会导致查找的效率大大降低。

红黑树简单说明

【来自百度百科】红黑树（Red Black Tree） 是一种自平衡二叉查找树，它是在计算机科学中用来组织数据比如数字的块的一种结构。

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。 ^[2]

由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。 ^[5]

在线演示网址-中文
在线演示网址-英文

• 演示 插入 1,2,3,4,5

红黑树定律:

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

---

如果觉得有收获就点个赞吧，更多知识，请点击关注查看我的主页信息哦~