tips:叶子结点,没有子结点的节点。nil等同于java中的null。
根据特点4,得出不能有连续的红色结点,特点5又说从任一结点到每个叶子节点的左右路径都包含相同数目的黑色节点。可以推出最长的路径就是一黑一红交叉排列,最短路径就是全黑。因此最长路径不会超过最短路径的二倍,所以说红黑树是近似平衡的,并不是严格意义上的平衡。需要了解平衡二叉树的童靴们,漫画:初识二叉树。
红黑树的查找,添加,删除,时间复杂度为O(log n),具体它是如何做到的,我们下次来说。
文章篇幅较短,希望大家能在简单轻松的氛围学习,小编更新的内容不多,但希望每次的文都能对大家有帮助,继续努力。同时大家可以把自己想学习了解的发到我的公众号后台,也可以在联系我的页面加微信,欢迎大家哦。
最后感谢你这么优秀,还来看我的文章,点个小心心再走呗。
领取专属 10元无门槛券
私享最新 技术干货