红黑树是怎么实现的

es)，后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树，就此红黑树出现在软件开发者的视野里!

一、摘要

在上篇文章中，我们详细的介绍到平衡二叉查找树的算法以及代码实践，我们知道平衡二叉查找树是一个高度平衡的二叉树，也就是说树的高度差不能大于1，在删除的时候，可能需要多次调整，也就是左旋转、右旋转操作，在树的深度很大的情况下，删除效率会非常低，如何提高这种效率?

红黑树由此诞生了，了解过红黑树的朋友们一定知道，红黑树是一个基本平衡的二叉树，英文全称：red-black-tree，简称：RBT，特性如下：

• 1.每个节点要么是黑色要么是红色;
• 2.根节点是黑色;
• 3.每个叶子节点是黑色;(注意：这里叶子节点，是指为空的叶子节点)
• 4.如果一个节点是红色的，则它的子节点必须是黑色的;(说明父子节点之间不能出现两个连续的红节点)
• 5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点;

关于它的特性，需要注意的是:

• 特性3中的叶子节点，是只为空(NIL 或 null)的节点;
• 特性5，确保没有一条路径会比其他路径长出俩倍，因而，红黑树是相对的接近平衡的二叉树!(比如，包含相同数目为3的黑节点路线，最短路线：`黑节点 -> 黑节点 -> 黑节点`，长度为3;最长路线：`黑节点 -> 红节点 -> 黑节点 -> 红节点 -> 黑节点`，长度为5)

（编辑：广安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!