定义

红黑树是一种自平衡二叉查找树，它可以在 O($\log(n)$ ) 时间内完成查找、插入和删除，这里的n是树中元素的数目。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 节点是红色或黑色。
2. 根节点是黑色。

定义

矩阵

矩阵是一个具有m行 x n列的数表，共包含m x n个数（元素），每个元素处在确定行和列的交点位置上，都与一对行号和列号唯一对应。
当一个矩阵中的行数和列数相同时，即m = n时则称为n阶矩阵或方阵。

稀疏矩阵（SparseMatrix）是矩阵中的一种特殊情况，其非零元素的个数小于零元素的个数。

对于稀疏矩阵中的每个非零元素，可用它所在的行号、列号以及元素这三元组（i，j，a_ij）来表示。若把所有的三元组按照行号为主序（即主关键字）、
列号为辅序（次关键字）进行排序，就构成一个表示稀疏矩阵的三元组线性表。

((1,1,3),(1,4,5),(2,3,-2),(3,1,1),(3,3,4),(3,5,6),(5,3,-1))

定义

平衡二叉树也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree），所以其本质也是一颗二叉搜索树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树（旋转操作）。

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。Ï

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋与右旋。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

左旋

栈

栈（Stack），也叫后进先出表（Last In First Out），是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。这一端称为栈顶，栈顶的第一个元素被称为栈顶元素，
相对的，另一端称为栈底。向一个栈插入新元素称为进栈或入栈，从一个栈删除元素又称为出栈或退栈。

存储结构

栈分为顺序栈和链式栈，可以使用数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。

顺序存储

链式存储

队列

队列（Queue），也叫先进先出表（First In First Out）仅允许在表的一端（队尾rear）进行插入，在表的另一端（队首front）进行删除。

定义

树是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；