数据结构是一系列解决方案的重要抽象，很多复杂问题的解决就是建立在数据结构的基础上进行抽象分化解决的。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的合集，包括逻辑结构和存储结构。

数据的逻辑结构包括如下：

• 线性结构
  • 线性表
    • 一般线性表
      • 线性表
    • 特殊线性表
      • 栈和队列
      • 字符串
    • 线性表的推广
      • 数组
      • 广义表
• 非线性结构
  • 树结构
    • 树
    • 二叉树
  • 图结构
    • 有向图
    • 无向图

存储结构包括如下：

• 顺序存储结构
• 链式存储结构

算法

算法是为了解决某类问题而规定的一个有限长的操作序列，具有：有穷性、确定性、可行性、输入、输出等五个重要特性。

一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数 f(n)，算法的时间复杂度记做：

T(n)=O(f(n))

它表示随着问题规则 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度(Time Complexity)。

线性表

顺序存储实现

线性表的顺序存储实现指的是用一组地址连续的存储单元依次存储线性表的数据元素，即为顺序表（Sequential List）。简单理解就是数组。

二叉树

二叉树上节点的平衡因子（Balance Factor）就是该节点左子树和右子树的深度之差。

二叉排序树

Binary Sort Tree 二叉排序树又称二叉查找树，是一种对排序和查找都很有用的树。

• 定义

二叉排序树或者是空树，或者是具有如下性质的二叉树：

1. 若其左子树非空，则左子树上所有节点的值均小于它的根节点的值
2. 若其右子树非空，则右子树上所有节点的值均大于它的根节点的值
3. 它的左、右子树也分别为二叉排序树

• 特性

二叉排序树是递归定义的，可以得出其一个重要性质：中序遍历一棵二叉排序树可以得到一个结点值递增的有序序列。

• 查找算法

树高度越小，查找速度越快。

查找的时间复杂度为 O(n)

假如二叉排序树的结构合理，则其查找算法时间复杂度可以达到 O(log₂n)。

平衡二叉树

Balanced Binary Tree 或 Height-Balanced Tree 平衡二叉树是一种特殊类型的二叉排序树，又叫 AVL 树，定义如下：

• 定义

平衡二叉树或者是空树，或者是具有如下性质的二叉排序树：

1. 左子树和右子树的深度之差的绝对值不超过 1
2. 左子树和右子树也是平衡二叉树

若插入节点后破坏了平衡二叉树的特性，则可以旋转节点进行调整。

• 特性

平衡二叉树上所有节点的平衡因子只可能是 -1、0、1，否则就是不平衡二叉树。

B-Tree

当文件比较大时需要从外存加载后再进行查找操作，为了优化查找效率转而使用了一种适用于外查找的平衡多叉树—— B 树。磁盘目录管理、数据库索引管理都基于 B-Tree 结构。

• 定义

一棵 m 阶的 B-Tree，或为空树，或为满足下列特性的 m 叉树：

B+Tree