【基础知识】_数据结构笔记

发表于 | 分类于

数据结构笔记

复杂度

  • 空间复杂度一般指程序指令所需占用的存储空间，时间复杂度一般指程序指令的执行次数(执行时间)，一般评价一个算法程序的优劣用时间复杂度来衡量。

  • 每次for循环的条件语句中的三个语句都要计算执行步骤，while循环中的条件语句则不用计算执行步骤。

  • 对数阶的复杂度一般忽略底数，如下图

    logn

  • 常见的复杂度(进行复杂度比较时，所有的程序复杂度都化成最简单的形式，然后来进行比较。)

    常见的复杂度

  • 多个数据规模的情况

    常见的复杂度

集合框架

  • 集合框架图（实线边框为实现类，折线边框为抽象类，点线边框为接口，空心箭头为继承关系，实心箭头为有一个抽象方法返回值为该类关系(无关紧要)）

    集合框架图

  • Iteraor迭代器接口：用于遍历集合中元素的接口，主要有三个用于往后遍历的方法，通常无序集合实现的都是这个接口，比如HashSet、HashMap。

  • Collection主要包含了List和Set两大分支：

    • List是一个有序的队列，实现类有4个：LinkedList、ArrayList、Vector、Stack。
    • Set是一个不允许有重复元素的集合，实现类有3个：TreeSet(元素有序存放)、HashSet(底层元素由HashMap的键来实现，元素需要实现hashCode()方法)、LinkedHashSet。

  • Map是一个映射接口，即key-value键值对，一个Map中不能包含相同的key，每个key都只能映射一个value，作为key的对象都必须实现hashCode方法和equals方法：

    • AbstractMap是个抽象类，它实现了Map接口中的大部分API，实现类有6个：TreeMap、HashMap、LinkHashMap、IdentityHashMap、WeakHashMap、HashTable。
    • SortedMap是继承于Map的接口，内容是排序的键值对，通过比较器Comparator来实现排序。

  • 各个类的使用场景

    各个类的适用场景

动态数组ArrayList

  • StringBuilder：用StringBuilder来拼接字符串比String效率高，如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
StringBuilder string = new StringBuilder();
//用StringBuilder来拼接字符串比用String效率高。

string.append("size=").append(size).append(", [");//append:附加。
//StringBuilder.append()方法的用法，可以将各种基本类型数据拼接到字符串上。

for(int i = 0;i < size;i ++){
    string.append(elements[i]);
    if(i != size - 1) {
        string.append(", ");
    }
}
string.append("]");

return string.toString();
//该函数设定返回参数类型为String，所以用StringBuilder拼接完字符串后还要转成String类型才能返回。

链表LinkedList

  • JDK中的LinkedList是双向链表，哈希表中的设计则运用的是单向链表。

栈Stack

队列Queue

  • 双端队列(Deque)就是能在头为两端添加、删除的队列。
  • JDK中的Queue和Deque都是通过双向链表作为底层来实现的。

二叉树Binary Tree

  • 树的基本性质

    • 层数：根节点在第1层，根节点的子节点在第2层，以此类推。
    • 节点的深度：从根节点到当前节点的唯一路径上的节点总数。
    • 节点的高度：从当前节点到最远叶子节点的路径上的节点总数。

  • 二叉树的性质

    • 非空二叉树的第i层，最多有2^(i - 1)个节点。
    • 在高度为h的二叉树上最多有2^h - 1个节点。
    • 如果二叉树的叶子节点个数为n0，度为2的节点个数为n2，则有：n0=n2+1。

  • 真二叉树（Proper Binary Tree）：所有节点的度要么为0，要么为2。

  • 满二叉树（Full Binary Tree）：最后一层节点的度都为0，其他节点的度都为2。

    • 满二叉树的高度为h，总结点数量为n，则有n=2^h - 1。

  • 完全二叉树（Complete Binary Tree）：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应。

    完全二叉树

  • 面试题：一个完全二叉树有768个节点，求叶子节点的个数。

    • 假设总节点个数为n，叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2，所以有n=n0+n1+n2=2n0+n1 - 1。
    • 完全二叉树的n1要么为0，要么为1。则当n1为1时，n=2n0，n必然时偶数，叶子节点数即为n0=n/2；当n1为0时，n=2n0 - 1，n必然是奇数，叶子节点数即为n0=(n+1)/2。
    • 综上分析，768为偶数，所以该完全二叉树的叶子节点个数即为384。

  • 前序遍历（Preorder Traversal）即为循环步骤：访问根节点、前序遍历左子树、前序遍历右子树。（左、右子树可交换）

  • 中序遍历（Inorder Traversal）即为循环步骤：中序遍历左子树、访问根节点、中序遍历右子树。（左、右子树可交换）

  • 后序遍历（Postorder Traversal）即为循环步骤：后序遍历左子树、后续遍历右子树、访问根节点。（左、右子树可交换）

  • 层序遍历（Level Order Traversal）：从上到下、从左到右依次访问每一个节点。（主要使用队列来辅助完成，先将根节点入队，然后不断循环以下操作直到队列为空：将对头节点A出队，进行访问，将A的左子节点入队，将A的右子节点入队。）

  • 根据遍历结果重构二叉树

    • 前序遍历结果+中序遍历结果：可以重构出唯一的一棵二叉树
    • 后序遍历结果+中序遍历结果：可以重构出唯一的一棵二叉树
    • 前序遍历结果+后序遍历结果：如果二叉树是以一颗真二叉树，则可以重构出唯一的一棵二叉树，不然重构不出。

  • 前驱节点（predecessor）：中序遍历时的前一个节点；后继节点（successor）：中序遍历时的后一个节点。

二叉搜索树Binary Sesrch Tree

  • 二叉搜索树的性质：

    • 二叉搜索树时二叉树的一种，是一种用于存储有序元素的数据结构。相比于同样用于存储有序元素的动态数组，二叉搜索树的增删改查操作的时间复杂度更小。
  • 任意一个节点的值都大于其左子树所有节点的值。
  • 任意一个节点的值都小于其右子树所有节点的值。
  • 它的左右子树也是一棵二叉搜索树。
  • 二叉搜索树存储的元素必须具备可比较性，不是单单比较出是否相等，而要比较出大小，所以也不能为null。

平衡二叉搜索树Balanced Binary Search Tree

  • 一棵达到适度平衡的二叉搜索树，就是平衡二叉搜索树，也就是在节点数相同的情况下，尽量使树的高度减小的二叉搜索树。
  • 比较经典常见的平衡二叉搜索树有AVL树和红黑树，这两者都是二叉搜索树的子类。

AVL树

  • 平衡因子：某节点的左、右子树的高度差
  • AVL树的特点：
    • 每个节点的平衡因子只能是1、0、-1。
    • 增、删、查的平均时间复杂度都是0(logn)。
  • 添加节点造成的失衡情况：
    • LL：在节点的左子节点的左子树上添加了元素导致该节点的平衡因子为2而失衡。
    • RR：在节点的右子节点的右子树上添加了元素导致该节点的平衡因子为-2而失衡。
    • LR：在节点的左子节点的右子树上添加了元素导致该节点的平衡因子为2而失衡。
    • RL：在节点的右子节点的左子树上添加了元素导致该节点的平衡因子为-2而失衡。
  • 解决添加节点造成的失衡的方法：
    • LL：右旋转（单旋）
    • RR：左旋转（单选）
    • LR：先左旋转，再右旋转（双旋）
    • RL：先右旋转，再左旋转（双旋）
  • AVL树中添加元素可能会导致所有祖先节点都失衡，但是只要调整使高度最低的失衡节点恢复平衡，整棵树就会恢复平衡；删除元素可能会导致父节点或者祖先节点中的一个节点失衡，但是调整恢复该节点平衡之后可能会导致更高层的祖先节点失衡，要一步一步往上调整。
  • 递归的缺点：递归就是一个方法调用它自己，每次递归就会往栈中添加一个栈帧，这样会造成栈空间的过度消耗。

红黑树RBT

  • ​红黑树也是一种自平衡的二叉搜索树，满足下述5个条件就认为红黑树平衡了：

    • 节点是RED或BLACK
    • 根节点是BLACK
    • 叶子节点（外部节点，空节点）都是BLACK
    • RED节点的子节点都是BLACK
      • RED节点的parent节点都是BLACK
      • 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
    • 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

    （上述用于判断是不是红黑树的5大性质中所说的叶子节点指的都是我们假象出来的null节点。）

  • 红黑树和4阶B树（2-3-4树）具有等价性，BLACK节点与它的RED子节点融合再一起，形成一个B树节点。

  • 红黑树的平均时间复杂度：增、删、查都是O(logn)。

  • AVL树与红黑树进行比较：

    • 增、删、查的平均时间复杂度都是O(logn)，但是AVL树的添加仅需O(1)次旋转调整、删除最多需要O(logn)次调整；红黑树添加和删除都仅需O(1)次旋转调整。
    • 相比于AVL树来说，红黑树牺牲了部分平衡性来换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
    • 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树。

集合Set与映射Map

  • Set和Map只是两个接口，JDK库中的这两个接口中只有抽象方法，一般需要借助其他动态数组或者二叉搜索树结构的实现类作为底层结构，创建实现类继承这两个接口。
  • JDK库中Map的实现类可以使用红黑树作为底层数据结构来实现的，这种实现方式就是将每个key-value键值对作为一个红黑树节点的节点元素，这就是TreeMap。
  • JDK库中Set的实现类TreeSet就是以TreeMap为底层结构创建的。
  • 用红黑树结构作为Set或者Map的底层结构比用动态数组作底层结构具有较高的效率，更低的时间复杂度，但是这就要求每一个节点的元素必须具备可比较性（其中Map是要求每一个节点中的key对象具有可比较性，当key相等直接覆盖节点）。如果即想要高的效率，又不想要求节点元素具有可比较性，那么就可以选择哈希表。
  • JDK库中是没有红黑树这个类的，但是JDK库中的TreeMap和HashMap都是用到了红黑树的结构来编写和实现一部分属性方法的，比如说设置节点颜色为红色或者黑色等。

哈希表Hash Table

  • 哈希表一般不直接使用，一般通过以哈希表为底层实现Map创建HashMap的形式来使用哈希表。也就是说我们所说的使用哈希表，在代码编写上一般是调用和实例化JDK库中的HashMap实现类。
  • 哈希表的增、删、查操作的时间复杂度都是0(1)级别。
  • TreeMap是用红黑树作为底层结构来编写的Map接口的实现类，而用HashTable代替红黑树作为底层来编写Map接口得到的实现类为HashMap，这种Map中的key不用考虑顺序和可比较性，平均时间复杂度可以达到0(1)级别。
  • HashMap的存储形式主要是把一对一对的键值对作为一个一个的节点，HashMap的最底层是一个数组Table，按节点中key对象计算出的数组索引将这些节点存放的数组相应位置。当不同的节点中的key对象计算出的数组索引值相同，则在该节点后面再通过next引用加上一个节点，加的节点多了这个单链表就变成一棵红黑树，存储在数组中的第一个获得该索引值的节点就是红黑树的根节点。
  • HashMap中数组索引相同的键值对要放到同一棵红黑树中，但是我们要求键值对中的key对象并不具备可比较性，所以我们必须从键值对的其他方面入手，定义出一种判断键值对的大小关系的方法来使得键值对节点可以正常存入红黑树中。比如依次比较节点的哈希值、节点中key的类名等，反正要自定义出一种比较大小的方法。

二叉堆Binary Heap

  • 堆的时间复杂度：获取最大值O(1)、删除最大值O(logn)、添加元素O(logn)。
  • 二叉堆只是在逻辑上是一棵完全二叉树，用完全二叉树的形式来思考增删查方法，实际上二叉堆的底层是用普通数组实现的。
  • 可以直接利用二叉堆作为优先级队列(Priority Queue)的底层。（优先级队列就是按照优先级高低进行出队的一种队列，比如永远是队列中优先级最高的元素先出队。）

比较器Comparable和Comparator

Comparable：
1
2
3
4
5
6
package java.lang;
import java.util.*;

public interface Comparable<T> {
    public int compareTo(T o);
}
  • Comparable是一个排序接口，如果一个类实现了该接口，就意味着该类支持排序，该类的实例化对象具有可比较性。
  • 在类中重写compareTo方法，定义该类的实例化对象的大小比较准则。
  • 实现该接口时泛型T写成实现它的类。
Comparator：
1
2
3
4
5
6
package java.util;

public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
}
  • Comparator是比较器接口，当我们要控制某个类的实例化对象的次序，使其具有可比较性，但是该类本身没有实现Comparable接口时，我们可以新建一个Comparator接口的实现类，用于比较该类实例化对象的大小。
  • 在该比较器实现类中重写compare方法，定义需要比较大小的实例化对象的比较准则。
  • 编写实现类时泛型T写成需要比较大小的类，且这种比较器实现类最常用的情况就是匿名类，如下代码：
1
2
3
4
5
6
7
8
9
10
11
Collections.sort(list2,new Comparator<Person2>(){

    @Override
    public int compare(Person2 o1, Person2 o2)
    {
    if(o1 == null || o2 == null)
    return 0;
    return o1.getAge()-o2.getAge();
    }

});
  • Comparator接口中的equals方法并不一定要实现，因为Java中的Object类已经实现类一种equals方法，如果想要不同的方法内容才需要重写。
Comparable与Comparator的区别
  • 想要一个类的实例化对象具有可比较性时，使该类实现Comparable接口就必须改变类自身，即在自身类中实现接口中相应的方法；而使用Comparator接口则是另外创建一个类使其实现该类的可比较性。
  • 像String这种JDK中已经定义死的类，我们可以运用Comparator重写String大小比较方法；或者一些无法继承其他类或者接口的类的可比较性也只能由Comparator来实现。
  • Comparable相当于和一个具体类绑定；Comparator比较灵活，可以被用于各个需要比较功能的类使用。
  • Comparable相当于一个内部比较器，而Comparator相当于一个外部比较器。

哈夫曼编码Huffman Coding

  • 哈夫曼编码不会产生歧义的原因：每个哈夫曼编码都不是另一个哈夫曼编码的前缀。
  • 带权路径长度：哈夫曼树中所有叶子节点的权值乘上其到根节点的路径长度。带权路径长度与最终的哈夫曼编码总长度乘正比关系。