面试复习-数据结构

1.栈：

先入后出（一般用于算法中的回溯法）

2.队列：

先入先出（常考算法有：两个栈实现队列、二叉树的层序遍历）

3.链表：

分为单向链表和双向链表，LinkedList的底层，循环遍历效率低，插入和删除效率高（常考的算法有：翻转链表、链表的复制、判断链表是否有环等）

4.散列表：

查找的时间复杂度为O（1），用于构造散列函数的方法有：

• 直接定址法：a*key+b
• 平方取值法：平方后的中间几位
• 除数留余法：key % p
• 随机数法

5.树

• 平衡二叉树：AVL树，首先是一棵二叉排序树，同时，左右子树的高度差绝对值不超过一，子树也是平衡二叉树。

• 完全二叉树：设树有k层，则只有第k层是不满的，且第k层叶子节点全部集中在左边

• 堆：具有以下性质的完全二叉树：每个节点的值都大于（大顶堆）/小于（小顶堆）叶子结点。PriorityBlockingQueue基于堆实现。
  相关场景题:海量数据中找最大的N个数：
  可以用一个大小为N的小顶堆，前N个数放入，然后从N-1个开始遍历，如果比堆顶数大的则替换，重新调整为小顶堆，这样遍历完后堆中的数据就是最大的N个数。

• 红黑树：具有以下特点：
  性质1：每个节点要么是红色，要么是黑色。
  性质2：根节点永远是黑色的。
  性质3：所有的叶子节点都是空节点（即null），并且是黑色的。
  性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点。）
  性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
  插入和查找的时间复杂度：O(log(n))

• 平衡树：又称为B树，平衡树是一颗查找树，并且所有叶子节点位于同一层，采用二分查找。B+ Tree是基于B Tree和叶子节点顺序访问指针进行实现。平衡树查找的时间复杂度和每个结点的出度有关：O(logd(N))，由于红黑树的出度为2，而B+Tree的出度一般很大，所以B+ Tree比红黑树查找更快。同时B+ Tree可以利用磁盘特性，不需要进行磁盘寻道。