常用数据结构和算法
- 线性结构：数组、链表、队列、栈、哈希表
- 树结构：二叉树、二分搜索树、平衡二叉树、红黑树
- 图结构：邻接矩阵
什么是二叉树的基本性质？链表实现
二叉树是每个节点最多有两个子树节点的有序树，左边的节点要比右边的节点大
平衡二叉树
- 任何一个节点的左子树与右子树的高度之差的绝对值不超过1，可以是空树
- avl和红黑树都是平衡二叉树，红黑数不是完全平衡的二叉树
- 线段树不是完全二叉树，是平衡二叉树
- 平衡二叉树整颗树的高度和她的节点的关系一定是一个log之间的关系；
完全二叉树
- 完全二叉树空缺的节点在整棵树的右下部分；
- 完全二叉树就是一层一层的放，直到放不下为止；
- 堆是一个完全二叉树，永远不会退化成链表（构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)）
大量的算法是以数据结构为基础
avl和红黑树都是平衡二叉树，红黑数不是完全平衡的二叉树
数组、链表、队列、栈、堆(最大堆/最小堆)、优先队列
二叉搜索树一定程度上可以提高搜索效率
AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大；
红黑树：红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的；
堆中两个最总要的操作：向堆中添加元素(数据上浮)和取出堆中最大的元素(数据下沉)，取出最大元素就是堆排序；heapify和sift down操作
AVL树是最先发明的自平衡二叉查找树，维护自平衡的方式是左旋转和右旋转；是很经典的操作；
2-3树，满足二分搜索树的基本性质，节点可以是1-2个元素；2-3树的对任意节点来说，左右子树的高度一定是相等的；
满二叉树：最后一层全部是叶子节点；完全二叉树：最后那一行可能不是完整的，但所缺失的部分一定是右下角某个连续的部分
数据结构和算法的应用：
- 单链表反转(n)、字符串反转(n/2)、排序算法(n->nlogn->n^2)、扫描文件目录(n^2)、无限极分类(n^2)；
- 6类12中写法，排序算法(n->nlogn->n^2)、单链表反转(n)、字符串反转(n/2)、扫描文件目录(n^2)、无限极分类(n^2)；
-
排序和二分搜索：冒泡和快排(nlogn)、递归的二分搜索；
-
链表：生成链表、链表反转的两种方式，递归和while;
-
字符串反转：while和for $len/2
-
遍历目录下的文件(两种方式)：按目录区分文件返回一个数组，直接输出文件和目录
-
无限极分类的两种方式，递归(level)和引用(array_column,没有id索引的和有id索引的)
-
二叉树：度度优先遍历(栈)和广度优先遍历(队列)，left和right 前中后序遍历的区别 前序是先访问根，再访问左子树、访问右子树 中序是先访问左子树、再访问根、再访问右子树 后序是先访问左子树、右子树，最后访问根
-
堆：最大堆和最小堆；堆是一个完全二叉树 向堆中添加元素 Sift Up 操作 从堆中取出最大元素 Sift Down 操作
-
常用排序算法，冒泡、快排、堆排序、桶排序
-
二叉树和链表有点关系，其它都是解决各自问题；