概述

数据结构是指计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。

常见数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树...

栈

• 后进先出、先进后出

队列

• 先进先出，后进后出

数组

• 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同。（元素在内存中是连续存储的）
• 删除效率低：要将原属数据删除，同时后面每个数据前移。
• 添加效率极低：添加位置后的每个数据后移，再添加元素。

链表

• 链表中的元素是在内存中不连续存储的，每个元素节点包含数据值以及下一个元素的地址。

• 链表查询慢，无论查询哪个数据都要从头开始找

这其实就是一个单链表 

• 链表增删相对较快

 

链表的种类

二叉树

• 只能有一个根节点：每个节点最多支持2个直接子节点
• 节点的度：节点拥有的子树的个数，二又树的度不大于2叶子节点；度为0的节点，也称之为终端结点
• 高度：叶子结点的高度为1，叶子结点的父节点高度为2，以此类推，根节点的高度最高
• 层：根节点在第一层，以此类推
• 兄弟节点：拥有共同父节点的节点互称为兄弟节点

二叉树又分为普通二叉树和二叉查找树，在开发中最常用的是二叉查找树。

二叉查找树

二叉查找树又称为二叉排序树或者二叉搜索树。

特点：

• 每一个节点上最多有两个字节点。
• 左子树上所有节点的值都小于根节点的值。
• 右子树上所有节点的值都大于根节点的值。

二叉查找树存在的问题：

这样就变得像链表一样，查询速度变慢了，所以引入平衡二叉树

平衡二叉树

 平衡二叉树是在满足二叉查找树得大小规则下，让树尽可能矮小，以此提高查数据的性能。

• 任意节点的左右两个子树的高度差不超过1，任意节点的左右两棵子树都是一颗平衡二叉树

平衡二叉树在添加元素后可能导致不平衡

• 基本策略是进行左旋或者右旋保证平衡。

  

平衡二叉树旋转的四种情况：左左、左右、右右、右左

• 左左：当根节点的左子树的左子树有节点插入，导致二叉树不平衡→采用右旋

• 左右： 当根节点的左子树的右子树有节点插入，导致二叉树不平衡→先左旋再右旋

• 右右： 当根节点的右子树的右子树有节点插入，导致二叉树不平衡→左旋

• 右左：当根节点的右子树的左子树有节点插入，导致二叉树不平衡→先右旋再左旋 

红黑树

• 是一种自平衡的二叉查找树
• 每一个节点可以是红或者黑，红黑树不是通过高度平衡的，他的平衡是通过“红黑规则”进行实现的。

红黑规则

• 每一个节点或是红色的，或是黑色，根节点必须是黑色。
• 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为NiL，这些NiL视为叶节点，叶节点是黑色的，如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）。
• 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

添加节点：

• 添加的节点的颜色，可以是黑色也可以是红色。
• 默认用红色效率更高。

默认用黑色：

默认用红色：