数据结构:小结(红黑树)
1、栈:
先进后出
2、队列:
先进先出
3、数组:
查询快:数组地址连续,可通过数组的首地址找到数组,通过数组的索引查找某一个元素
增删慢:数组长度固定,要增加或删除一个元素必须新创建一个数组,将原数组数据复制过来
4、链表:
链表中的每一个元素称为一个节点,一个节点包含了一个数据源(存储数组),两个指针域(存储自己的地址,存储下一个节点的地址)
查询慢:链表中地址不连续。每次查询元素,都必须从头开始查询
增删快:链表结构增加或删除一个元素,对整体结构没有影响
单向链表 :链表中只有一条链子,不能保证元素的顺序(存储元素和取出元素的顺序可能不一致)
双线链表:链表中有两条链子,有一条链子是专门记录元素的顺序,是一个有序的集合。
5、红黑树
二叉树:分支不超过两个:左孩子也叫左子树,右孩子也叫右子树
排序树(查找树):在二叉树的基础上,元素有大小顺序,左子树小,右子树大
平衡树:左孩子数量 = 右孩子数量
平衡树:左孩子数量不等于右孩子数量
红黑树
特点:趋近于平衡树,查询叶子节点最大次数和最小次数不能超过2倍
查询速度非常快!
约束:
- 节点可以是红色或者黑色的
- 根节点是黑色的
- 叶子节点(空节点)是黑色的
- 每个红色节点的子节点都是黑色的
- 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
![]()