红黑树的详细实现(C++)

article/2025/10/1 4:03:43

红黑树概念(concept)

树型结构主要用于搜索，一直是科学领域的重要演算法，当中探讨了树可能遇到的问题：树的成长可能偏向于一边，也就是不平衡现象。

二叉树是常见且广泛使用的一种树，面临其可能退化成链表的潜藏缺点，在使用上难免让人担心其效率。此外，在一些应用上，可能不希望这样的不平衡的可能性发生。所以具有自动平衡左右数量分布效果的演算算法早在 1962 年被提出，称为 AVL 树。这种平衡成长的二叉搜索树被称为自平衡二叉搜索树。

接下来，介绍同为自平衡二叉搜索树的红黑树对平衡性的要求比 AVL 树还要宽松。红黑树是利用节点颜色来检查二叉树每条路径的高度是否差不多，因为发明者定下了以下规则：

  1. 树上的每个结点(node) 只能是 红色 或 黑色。

  2. 根节点(root) 一定是黑色。

  3. 叶子节点(leaf) 一定是 黑色 的 空值节点 (NULL)。

  4. 任一路径上不能有两个连续的红色。注意：黑色节点的子节点颜色没有限制。

  5. 从任何节点出发，其下至叶节点所有路径的黑色节点数目相同。

满足上述的二叉树，相比一般的二叉树更能保持平衡性，往后套用二叉树的算法来查找时能更快速、方便的到达目的地，套用算法的时间复杂度为 O(logn)，因为红黑树保证最长路径不会超过最短路径的两倍（由规则 4 和规则 5）。原因是：当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（规则4限定了不能出现两个连续的红色节点）。而规则5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的 2 倍。

如下是一个红黑树示例图：

红黑树的详细实现-图1

注意：null 节点是指每个叶节点都有两个空的并且颜色为黑的 NULL 节点，一般在示例图中需要它的时候就可以把它看成两个黑色的节点，不需要的时候可以忽视它。

红黑树与AVL的比较：

红黑树和 AVL 树的算法时间复杂度相同，但红黑树不追求完全平衡，换来的是增删节点时转转次数的降低，任何不平衡都会在三次旋转之内解决，但AVL是严格平衡树，旋转次数比红黑树多。插入节点失衡时，AVL 和 RBTree 都是最多两次旋转实现复衡 (O(1))，但删除节点失衡时，AVL 需要维护从被删除节点到根节点路径上所有节点的平衡 (O(logN))，而红黑树最多只需要 3 次 (O(1))，所以 RBTree 在内容极多时优于 AVL，RBTree 的功能、性能、空间开销综合更好。红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在 STL 的 set 和 map 等容器中被优先使用。

因为红黑树也是一种二叉树，所以例如：插入结点、删除结点、查询结点等针对红黑树的操作与二叉树的操作前段演算法相同，只是在每次操作完后可能会让树的结构改变而可能无法满足红黑树的规则，进而可能不具有平衡的性质。为了在操作后仍是一颗红黑树，需要通过变色和旋转调整来满足红黑树的规则。

红黑树插入(Insertion)

在新增的操作上，新插入的节点一律为红色，因此如果插入的节点着色为黑色，那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点数量，因此默认插入的节点必须是红色的，目的是希望红黑树维持上面规则5的约束，也就是任一根节点到叶子节点黑色节点数目相同，但是也可能违反出了规则5外的其他规则，所以做完二叉树新增操作后，需要以新增的节点开始向上检查红黑树是否符合各项规则。

首先先明确以下各个节点的叫法：

红黑树的详细实现-图2

红黑树的插入会有以下几种情况，因为不同情况会采取不同的修正过程：

  • 情况1：当红黑树为空树时，新插入红色节点成为根节点，必须将其变成黑色。

红黑树的详细实现-图3

  • 情况2：插入新的红色节点的父节点为黑色，并不会影响红黑树的平衡，直接插入即可。

红黑树的详细实现-图4

  • 情况3：插入的新的红色节点的父节点是红色，若叔叔结点为红色，则祖父结点一定为黑色，将祖父结点变为红色，而父节点和叔叔结点变为黑色。因为红色结点上移，出现连续的红色节点，形成了情况4，这将再情况4中说明。

红黑树的详细实现-图5

  • 情况4：插入的新的红色节点的父节点是红色，如果叔叔节点是黑色，且新的节点在父节点右边，则先以父节点进行左旋转，形成了情况5，在情况5中处理。

红黑树的详细实现-图6

  • 情况5：插入新的红色节点的父节是红色 ，如果叔叔节点是黑色，且新节点在父节点左边，则先将父节点变成黑色，但是违反了规则5（黑色节点数目不相同），必须再将祖父节点变成红色，以祖父节点进行右旋（直觉上，节点F的左边路径会多一个黑色节点，可以通过右旋把黑色转掉）。

红黑树的详细实现-图7注意：以上都在讨论新插入的红色节点的父节点是红色，且父节点是祖父节点的左分支情况，如果是在右分支，其处理是镜像的，只需要左右互换一下就可以了。

红黑树删除(Deletion)

首先要了解 AVL 的删除操作：

  1. 如果删除的是叶子节点，可以直接删除。

  2. 如果被删除的元素有一个子节点，可以将子节点直接移动到被删除元素的位置。

  3. 如果有两个子节点，这时候就可以把被删除的元素的右分支的最小点（也就是被删除元素左分支的最左边节点）和被删除的元素互换，然后再将被删除元素删除。

但是红黑树加入颜色后，被删除元素和后继元素互换只是值互换，并不是互换颜色。

红黑树的删除操作上，删除一个节点可能会违反规则，需要向上检查红黑树是否符合各项规则，修正红黑树可能会有以下几种情况：

  • 情况1：当被删除节点为黑且为根节点时，直接删除。

  • 情况2：被删除的是红色的节点，不违反任何规则，直接删除。

  • 情况3：被删除的节点是黑色，但是递补上来的节点是红色，直接将该递补上来的节点变为黑色即可。

红黑树的详细实现-图8

情况4：被删除的节点为黑色，且兄弟节点为红色，需要将兄弟节点变为黑色，父节点变为红色，再以父节点进行左旋。形成了情况5，在情况5中处理。

红黑树的详细实现-图9

情况5：被删除的节点为黑色，若兄弟节点为黑色，且兄弟的左孩子节点与右孩子节点都是黑色时，这时如果父节点为红色，将兄弟节点变为红色，父节点变为黑色即可。

红黑树的详细实现-图10

情况6：被删除的节点为黑色，且兄弟节点为黑色，兄弟节点的左孩子节点为红色，这时需要把兄弟节点变为红色，兄弟节点的左孩子节点变为黑色，再以兄弟节点进行右旋操作。形成了情况7，在情况7中处理。

红黑树的详细实现-图11

情况7：被删除的节点为黑色，且兄弟节点为黑色，兄弟节点的右孩子节点为红色，这时需要把兄弟节点变为父节点的颜色，并把父节点和兄弟节点的右孩子节点变为黑色，再以父节点进行左旋即可。

红黑树的详细实现-图12

注意：以上都在讨论删除红黑树的一个节点，且被删除节点是父节点左分支情况，如果是在右分支上，其处理是镜像的。

红黑树的总结(Conclusion)

红黑树的步骤是可以推导出来的，因为把一个平衡但通过插入或删除操作破坏了平衡的红黑树再次平衡，通过转转和变色使其符合红黑树的 5 条规则，旋转操作是为了符合二叉树左小右大的性质，交换颜色是为了保持红黑树的 5 条性质。时刻记得红黑树的一切操作是为了上面的5条规则。

红黑树的实现(Implement)

红黑树的节点类型定义如下：

template <typename Type>
struct RBTNode
{Color color;     //颜色Type key;        //关键字RBTNode *left;   //左孩子RBTNode *right;  //右孩子RBTNode *parent; //父结点
};

下面给出红黑树的 C++ 完整实现代码：

#include <iostream>
#include <assert.h>using namespace std;typedef enum
{RED = 0,BLACK
} Color;//红黑树结点类型
template <typename Type>
struct RBTNode
{Color color;     //颜色Type key;        //关键字RBTNode *left;   //左孩子RBTNode *right;  //右孩子RBTNode *parent; //父结点
};//红黑树类型
template <typename Type>
class RBTree
{
public://构造函数RBTree(){Nil = BuyNode();root = Nil;Nil->color = BLACK;}//析构函数~RBTree(){destroy(root); //销毁创建的非Nil结点delete Nil;    //最后删除Nil结点Nil = NULL;}//中序遍历void InOrder() { InOrder(root); }//插入//1.BST方式插入//2.调整平衡bool Insert(const Type &value){RBTNode<Type> *pr = Nil; //pr用来记住父节点RBTNode<Type> *s = root; //定义变量s指向根while (s != Nil){if (value == s->key){return false;}pr = s; //每次记住s的父节点if (value < s->key){s = s->left;}else{s = s->right;}}//循环后s==Nils = BuyNode(value); //申请结点if (pr == Nil)      //如果父节点pr是根节点，第一次root指向Nil，所以pr==Nil{root = s;root->parent = pr;}else //如果父节点不是根节点{if (value < pr->key){pr->left = s;}else{pr->right = s;}s->parent = pr; //设置新结点s的父节点}//调整平衡Insert_Fixup(s);return true;}//删除key结点(先查找，再调用内部删除)void Remove(Type key){RBTNode<Type> *t;if ((t = Search(root, key)) != Nil){Remove(t);}else{cout << "Key is not exist." << endl;}}//中序遍历打印结点详细的结点颜色void InOrderPrint() { InOrderPrint(root); }protected://申请结点结点，将结点的颜色初始化为红色，初始化结点的关键字，其他的初始化为空RBTNode<Type> *BuyNode(const Type &x = Type()){RBTNode<Type> *s = new RBTNode<Type>();assert(s != NULL);s->color = RED;s->left = s->right = s->parent = Nil;s->key = x;return s;}//中序遍历void InOrder(RBTNode<Type> *root){if (root != Nil){InOrder(root->left);cout << root->key << " ";InOrder(root->right);}}/* 左转，对z结点左转*       zp                 zp*       /                  /*     z                   y*    / \      ===>       / \*   lz  y               z   ry*      / \             / \*     ly  ry          lz  ly  */void LeftRotate(RBTNode<Type> *z){RBTNode<Type> *y = z->right; //用y指向要转动的z结点z->right = y->left;if (y->left != Nil) //y所指结点的左结点不为空{y->left->parent = z;}y->parent = z->parent;if (root == z) //z就是根节点{root = y;}else if (z == z->parent->left) //z在左结点{z->parent->left = y;}else //z在右结点{z->parent->right = y;}y->left = z;z->parent = y;}/* 右转，对z结点进行右转*         zp               zp*        /                 /*       z                 y*      / \    ===>       / \*     y   rz           ly   z   *    / \                   / \*   ly  ry                ry  rz*/void RightRotate(RBTNode<Type> *z){RBTNode<Type> *y = z->left;z->left = y->right;if (y->right != Nil){y->right->parent = z;}y->parent = z->parent;if (root == z) //如果z是根结点{root = y;}else if (z == z->parent->left) //z在左结点{z->parent->left = y;}else //z在右结点{z->parent->right = y;}y->right = z;z->parent = y;}//插入后的调整函数void Insert_Fixup(RBTNode<Type> *s){RBTNode<Type> *uncle;           //叔结点（父结点的兄弟结点）while (s->parent->color == RED) //父节点的颜色也为红色{if (s->parent == s->parent->parent->left) //父节点是左结点{uncle = s->parent->parent->right;if (uncle->color == RED) //叔结点为红色{//父节点和叔结点都变为黑色s->parent->color = BLACK;uncle->color = BLACK;//祖父结点变为红色s->parent->parent->color = RED;//将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色s = s->parent->parent;}else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑){if (s == s->parent->right) //如果调整的结点在右结点{s = s->parent; //先将s指向s的父结点LeftRotate(s); //再左转}//如果调整的结点在左结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转s->parent->color = BLACK;s->parent->parent->color = RED;RightRotate(s->parent->parent);}}else{if (s->parent == s->parent->parent->right) //父节点是右结点{uncle = s->parent->parent->left;if (uncle->color == RED) //叔结点为红色{//父节点和叔结点都变为黑色s->parent->color = BLACK;uncle->color = BLACK;//祖父结点变为红色s->parent->parent->color = RED;//将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色s = s->parent->parent;}else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑){if (s == s->parent->left) //如果调整的结点在左结点{s = s->parent;  //先将s指向s的父结点RightRotate(s); //再右转}//如果调整的结点在右结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转s->parent->color = BLACK;s->parent->parent->color = RED;LeftRotate(s->parent->parent);}}}}root->color = BLACK; //最后始终将根节点置为黑色}//查找key结点RBTNode<Type> *Search(RBTNode<Type> *root, Type key) const{if (root == Nil) //root为空，或key和根的key相同{return Nil;}if (root->key == key){return root;}if (key < root->key){return Search(root->left, key);}else{return Search(root->right, key);}}/* 将u的子节点指向u的指针改变指向v，将v的父节点指针改变为指向u的父节点*      up*        \*         u*        / \*      ul   ur*     / \*    v  ulr*     \*     rv*/void Transplant(RBTNode<Type> *u, RBTNode<Type> *v){if (u->parent == Nil) //u的父节点为空{root = v; //直接令根root为v}else if (u == u->parent->left) //u父节点不为空，且u在左子树{u->parent->left = v;}else //u在右子树{u->parent->right = v;}v->parent = u->parent;}/* 找到最左结点(最小)*      xp*        \*         x*        / \*      xl   xr*     / \*   xll  xlr*/RBTNode<Type> *Minimum(RBTNode<Type> *x){if (x->left == Nil){return x;}return Minimum(x->left);}//删除红黑树结点zvoid Remove(RBTNode<Type> *z){RBTNode<Type> *x = Nil;RBTNode<Type> *y = z;    //y记住传进来的z结点Color ycolor = y->color; //if (z->left == Nil)      //z只有右孩子{x = z->right;Transplant(z, z->right);}else if (z->right == Nil) //z只有右孩子{x = z->left;Transplant(z, z->left);}else //右左孩子和右孩子{y = Minimum(z->right); //y是z右子树的的最左子树ycolor = y->color;x = y->right;if (y->parent == z) //z的右子结点没有左节点或为Nil{x->parent = y;}else //z的右子结点有左节点或为Nil{Transplant(y, y->right);y->right = z->right;y->right->parent = y;}Transplant(z, y);//改变指向y->left = z->left;z->left->parent = y;y->color = z->color;}if (ycolor == BLACK){Remove_Fixup(x);}}//红黑树删除调整void Remove_Fixup(RBTNode<Type> *x){while (x != root && x->color == BLACK) //当结点x不为根并且它的颜色不是黑色{if (x == x->parent->left) //x在左子树{RBTNode<Type> *w = x->parent->right; //w是x的兄结点if (w->color == RED) //情况1{w->color = BLACK;x->parent->color = RED;LeftRotate(x->parent);w = x->parent->right;}if (w->left->color == BLACK && w->right->color == BLACK) //情况2{w->color = RED;x = x->parent;}else{if (w->right->color == BLACK) //情况3{w->color = RED;w->left->color = BLACK;RightRotate(w);w = x->parent->right;}//情况4w->color = w->parent->color;w->parent->color = BLACK;w->right->color = BLACK;LeftRotate(x->parent);x = root; //结束循环}}else //x在右子树{RBTNode<Type> *w = x->parent->left;if (w->color == RED) //情况1{w->parent->color = RED;w->color = BLACK;RightRotate(x->parent);w = x->parent->left;}if (w->right->color == BLACK && w->right->color == BLACK) //情况2{w->color = RED;x = x->parent;}else{if (w->left->color == BLACK) //情况3{w->right->color = BLACK;w->color = RED;LeftRotate(w);w = x->parent->left;}//情况4w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;RightRotate(x->parent);x = root; //结束循环}}}x->color = BLACK;}//销毁红黑树void destroy(RBTNode<Type> *&root){if (root == Nil){return;}if (root->left != Nil){destroy(root->left);}if (root->right != Nil){destroy(root->right);}delete root;root = NULL;}//中序遍历打印结点详细的结点颜色void InOrderPrint(RBTNode<Type> *node){if (node == Nil){return;}if (node->left != NULL){InOrderPrint(node->left);}cout << node->key << "(" << ((node->color == BLACK) ? "BLACK" : "RED") << ")"<< " ";if (node->right != Nil){InOrderPrint(node->right);}}private:RBTNode<Type> *root; //根指针RBTNode<Type> *Nil;  //外部结点，表示空结点，黑色的
};int main(int argc, char *argv[])
{RBTree<int> rb;int arr[] = {10, 7, 8, 15, 5, 6, 11, 13, 12};int n = sizeof(arr) / sizeof(int);for (int i = 0; i < n; i++){rb.Insert(arr[i]);}rb.InOrder();cout << endl;rb.InOrderPrint();cout << endl;rb.Remove(10);rb.InOrder();cout << endl;rb.Remove(21);return 0;
}

http://chatgpt.dhexx.cn/article/Bth9bGrM.shtml

相关文章

二叉树——二叉查找树和红黑树

二叉树——二叉查找树和红黑树

二叉树 二叉树&#xff0c;是一个非常重要的数据结构&#xff0c;在日常的开发中起着很重要的作用&#xff0c;它也衍生出来的各种高效的复杂的数据结构&#xff0c;为我们解决问题提供了高效的解决方案。 二叉树&#xff0c;它是由各个数据节点和左右链接构成的一种类似树的数…
阅读更多...
Java——红黑树

Java——红黑树

概念 红黑树也是一种二叉搜索树&#xff0c;但是和avl树不同&#xff0c;它并不是依靠平衡因子来保证树的平衡的&#xff0c;而是通过颜色 红黑树每个节点中会存储颜色&#xff0c;分为红色和黑色&#xff0c;通过红黑树的限制条件&#xff0c;可以保证从根节点出发到叶子节点…
阅读更多...
二叉树--红黑树

二叉树--红黑树

红黑树 定义 红黑树&#xff0c;顾名思义&#xff0c;就是树的节点只有红色和黑色两种状态&#xff0c;通过这两种状态的标识和规定颜色的使用&#xff0c;来使树达到相对平衡。为什么说相对平衡&#xff1f;因为在红黑树中&#xff0c;所有的条件限制只能保证&#xff0c;所…
阅读更多...
二叉树之红黑树

二叉树之红黑树

红黑树 概述 为什么要有红黑树&#xff1f;&#xff1f;&#xff1f; 特点 红黑规则 如何在红黑树上添加节点&#xff1f; &#xff08;1&#xff09;我们不妨假设加入的节点都是黑色 &#xff08;2&#xff09;如果我们加入的节点都是红色 红黑树添加节点后如何保持红…
阅读更多...
红黑二叉树

红黑二叉树

红黑树 红黑树是每个节点都带有颜色属性的二叉查找树&#xff0c;颜色或红色或黑色。在二叉查找树强制一般要求以外&#xff0c;对于任何有效的红黑树我们增加了如下的额外要求: 节点是红色或黑色。 根节点是黑色。 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有…
阅读更多...
红黑树-Java实现

红黑树-Java实现

目录 一、定义 二、插入 三、删除 四、全部代码 五、颜色效果 一、定义 红黑树是特殊的平衡二叉树&#xff0c;具有以下特性&#xff1a; 1、根节点的颜色是黑色 2、节点颜色要么是黑色、要么是红色 3、如果一个节点的颜色是红色&#xff0c;则它的子节点必须是黑色&…
阅读更多...
红黑二叉树原理分析

红黑二叉树原理分析

1.引言 HashMap的基本结构是数组&#xff0c;链表和红黑树。以数组为基本形态&#xff0c;数组中的元素先以链表形式储存&#xff0c;当链表的长 度超过8时&#xff08;包含数组上的那个链表头&#xff09;就会将链表转换为红黑树&#xff0c;以加快修改和查询效率。当然除了H…
阅读更多...
理解红黑树及代码实现

理解红黑树及代码实现

1.红黑树定义 红黑树是一颗 红-黑的平衡二叉树,它具有二叉树的所有特性,是一颗自平衡的排序二叉树.(树中任何节点值都大于左子节点的值&#xff0c;而且都小于右子节点的值),其检索效率高&#xff0c;它是一颗空树或它的左右两个子树高度差的绝对值不超过1&#xff0c;并且左右…
阅读更多...
红黑二叉树的漫画讲解（轻松理解红黑二叉树原理）

红黑二叉树的漫画讲解（轻松理解红黑二叉树原理）

———————————— 二叉查找树&#xff08;BST&#xff09;具备什么特性呢&#xff1f; 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下图中这棵树&#xff0c;就是…
阅读更多...
Java的二叉树、红黑树、B+树

Java的二叉树、红黑树、B+树

数组和链表是常用的数据结构&#xff0c;数组虽然查找快&#xff08;有序数组可以通过二分法查找&#xff09;&#xff0c;但是插入和删除是比较慢的&#xff1b;而链表&#xff0c;插入和删除很快&#xff08;只需要改变一些引用值&#xff09;&#xff0c;但是查找就很慢&…
阅读更多...
二叉树与红黑树

二叉树与红黑树

二叉树的形成 二叉树是n(n>0)个结点的有限集合&#xff0c;该集合或者为空集&#xff08;称为空二叉树&#xff09;&#xff0c;或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成 二叉树特点 由二叉树定义以及图示分析得出二叉树有以下特点&#xff1…
阅读更多...
红黑树（C++实现）

红黑树（C++实现）

文章目录 红黑树的概念红黑树的性质红黑树结点的定义红黑树的插入红黑树的验证红黑树的查找红黑树的删除红黑树与AVL树的比较 红黑树的概念 红黑树是一种二叉搜索树&#xff0c;但在每个结点上增加了一个存储位用于表示结点的颜色&#xff0c;这个颜色可以是红色的&#xff0c;…
阅读更多...
红黑二叉树详解及理论分析

红黑二叉树详解及理论分析

发表于我的博客网站(prajna.top)&#xff1a; http://prajna.top/doc/2/175 什么是红-黑二叉树&#xff1f; 红-黑二叉树首先是一颗二叉树&#xff0c;它具有二叉树的所有性质&#xff0c;是一种平衡二叉树。普通二叉树在生成过程中&#xff0c;容易出现不平衡的现象&#xff…
阅读更多...
二叉树到红黑树

二叉树到红黑树

二叉树查找树 又叫二叉排序树。二叉查找树或者是一棵空树&#xff0c;或者是一棵具有如下性质的二叉树&#xff1a; 对于任何一个结点X若它的左子树非空&#xff0c;则左子树上所有结点的值均小于等于X的值&#xff1b;若它的右子树非空&#xff0c;则右子树上所有结点的值均大…
阅读更多...
详解c++---红黑二叉树的原理和实现

详解c++---红黑二叉树的原理和实现

目录标题 什么是红黑二叉树树红黑树的性质红黑树的效率分析红黑树的准备工作红黑树的insert函数节点的调整情况一情况二情况三 转换的实现打印函数find函数检查函数 什么是红黑二叉树树 avl树是通过控制平衡因子来控制二叉搜索树的平衡&#xff0c;当某个节点的平衡因子等于2或…
阅读更多...
红黑树和二叉树有什么区别？

红黑树和二叉树有什么区别？

红黑树和二叉树有什么区别&#xff1f; 什么是二叉树&#xff1f;什么是红黑树&#xff1f; 二叉树&#xff08;Binary Tree&#xff09;是指每个节点最多只有两个分支的树结构&#xff0c;即不存在分支大于 2 的节点&#xff0c;二叉树的数据结构如下图所示 这是一棵拥有 6 …
阅读更多...
二叉树系列：红黑树

二叉树系列：红黑树

介绍 红黑树(Red-Black Tree&#xff0c;简称R-B Tree)&#xff0c;它一种特殊的二叉查找树。红黑树是特殊的二叉查找树&#xff0c;意味着它满足二叉查找树的特征&#xff1a;任意一个节点所包含的键值&#xff0c;大于等于左孩子的键值&#xff0c;小于等于右孩子的键值。除了…
阅读更多...
红黑树结构原理的图文讲解（非代码）

红黑树结构原理的图文讲解（非代码）

1.引言 HashMap的基本结构是数组&#xff0c;链表和红黑树。以数组为基本形态&#xff0c;数组中的元素先以链表形式储存&#xff0c;当链表的长度超过8时&#xff08;包含数组上的那个链表头&#xff09;就会将链表转换为红黑树&#xff0c;以加快修改和查询效率。当然除了Ha…
阅读更多...
二叉树与红黑树见解

二叉树与红黑树见解

目录 一、红黑树简介二、 红黑树的特性三、红黑数的应用四、红黑树的原理实现4.1 识别红黑树4.2 红黑树节点的旋转4.3 插入节点4.3.1分情况讨论&#xff1a;4.3.2 代码示例 4.4删除节点相关引用 一、红黑树简介 红黑树是一种自平衡的二叉查找树&#xff0c;是一种高效的查找树…
阅读更多...
什么是红黑树（内存最优的二叉树）

什么是红黑树（内存最优的二叉树）

一.红黑树定义 红黑树(Red Black Tree) 是一种自平衡二叉查找树&#xff0c;是在计算机科学中用到的一种数据结构&#xff0c;典型的用途是实现关联数组。 它是在1972年由Rudolf Bayer发明的&#xff0c;当时被称为平衡二叉B树(symmetric binary B-trees)。后来&#xff0c;在1…
阅读更多...
推荐文章

Copyright @ 2022~2023