概述
数据结构是指计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。
常见数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树...
栈
- 后进先出、先进后出
队列
- 先进先出,后进后出
数组
- 查询速度快:查询数据通过地址值和索引定位,查询任意数据耗时相同。(元素在内存中是连续存储的)
- 删除效率低:要将原属数据删除,同时后面每个数据前移。
- 添加效率极低:添加位置后的每个数据后移,再添加元素。
链表
- 链表中的元素是在内存中不连续存储的,每个元素节点包含数据值以及下一个元素的地址。
- 链表查询慢,无论查询哪个数据都要从头开始找
这其实就是一个单链表
- 链表增删相对较快
链表的种类
二叉树
- 只能有一个根节点:每个节点最多支持2个直接子节点
- 节点的度:节点拥有的子树的个数,二又树的度不大于2叶子节点;度为0的节点,也称之为终端结点
- 高度:叶子结点的高度为1,叶子结点的父节点高度为2,以此类推,根节点的高度最高
- 层:根节点在第一层,以此类推
- 兄弟节点:拥有共同父节点的节点互称为兄弟节点
二叉树又分为普通二叉树和二叉查找树,在开发中最常用的是二叉查找树。
二叉查找树
二叉查找树又称为二叉排序树或者二叉搜索树。
特点:
- 每一个节点上最多有两个字节点。
- 左子树上所有节点的值都小于根节点的值。
- 右子树上所有节点的值都大于根节点的值。
二叉查找树存在的问题:
这样就变得像链表一样,查询速度变慢了,所以引入平衡二叉树
平衡二叉树
平衡二叉树是在满足二叉查找树得大小规则下,让树尽可能矮小,以此提高查数据的性能。
- 任意节点的左右两个子树的高度差不超过1,任意节点的左右两棵子树都是一颗平衡二叉树
平衡二叉树在添加元素后可能导致不平衡
- 基本策略是进行左旋或者右旋保证平衡。
平衡二叉树旋转的四种情况:左左、左右、右右、右左
- 左左:当根节点的左子树的左子树有节点插入,导致二叉树不平衡→采用右旋
- 左右: 当根节点的左子树的右子树有节点插入,导致二叉树不平衡→先左旋再右旋
- 右右: 当根节点的右子树的右子树有节点插入,导致二叉树不平衡→左旋
- 右左:当根节点的右子树的左子树有节点插入,导致二叉树不平衡→先右旋再左旋
红黑树
- 是一种自平衡的二叉查找树
- 每一个节点可以是红或者黑,红黑树不是通过高度平衡的,他的平衡是通过“红黑规则”进行实现的。
红黑规则
- 每一个节点或是红色的,或是黑色,根节点必须是黑色。
- 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为NiL,这些NiL视为叶节点,叶节点是黑色的,如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
- 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。
添加节点:
- 添加的节点的颜色,可以是黑色也可以是红色。
- 默认用红色效率更高。
默认用黑色:
默认用红色: