数据结构和算法

数据结构-树

介绍

结点和边组成的，不存在环的一种数据结构。

树满足递归定义的特性。也就是说，如果一个数据结构是树结构，那么剔除掉根结点后，得到的若干个子结构也是树，通常称作子树。

存储结构

分支和层次关系

根节点

父节点

子节点

叶子节点：没有子节点

分类

1.二叉树

介绍

存储结构

数据操作

遍历

时间复杂度：O(n)

• 前(先)序遍历，对树中的任意结点来说，先打印这个结点，然后前序遍历它的左子树，最后前序遍历它的右子树。

  public static void preOrderTraverse(Node node) {
      if (node == null)
          return;
      System.out.print(node.data + " ");
      preOrderTraverse(node.left);
      preOrderTraverse(node.right);
  }

• 中序遍历，对树中的任意结点来说，先中序遍历它的左子树，然后打印这个结点，最后中序遍历它的右子树。

  // 中序遍历
  public static void inOrderTraverse(Node node) {
      if (node == null)
          return;
      inOrderTraverse(node.left);
      System.out.print(node.data + " ");
      inOrderTraverse(node.right);
  }

• 后序遍历，对树中的任意结点来说，先后序遍历它的左子树，然后后序遍历它的右子树，最后打印它本身。

  // 后序遍历
  public static void postOrderTraverse(Node node) {
      if (node == null)
          return;
      postOrderTraverse(node.left);
      postOrderTraverse(node.right);
      System.out.print(node.data + " ");
  }

2.二叉搜索树

介绍

特性：

• 在二叉查找树中的任意一个结点，其左子树中的每个结点的值，都要小于本结点的值。
• 在二叉查找树中的任意一个结点，其右子树中每个结点的值，都要大于这个结点的值。
• 在二叉查找树中，会尽可能规避两个结点数值相等的情况。（《数据结构》严蔚敏-数值不能相同）
• 对二叉查找树进行中序遍历，就可以输出一个从小到大的有序数据队列。

存储结构

数据操作

新增

时间复杂度：O(logn)。

如果要插入的数据比根结点的数据大，且根结点的右子结点不为空，则在根结点的右子树中继续尝试执行插入操作。直到找到为空的子结点执行插入动作。

删除

时间复杂度为 O(logn)。

删除操作会比较复杂，这是因为删除完某个结点后的树，仍然要满足二叉查找树的性质。分为下面三种情况。

• 要删除的结点是某个叶子结点，则直接删除。将其父结点指针指向 null 即可。
• 如果要删除的结点只有一个子结点，只需要将其父结点指向的子结点的指针换成其子结点的指针即可。
• 如果要删除的结点有两个子结点，则有两种可行的操作方式。
  • 第一种，找到这个结点的左子树中最大的结点，替换要删除的结点。
  • 第二种，找到这个结点的右子树中最小的结点，替换要删除的结点。

查询

时间复杂度为 O(logn)。

查询步骤：

• 首先判断根结点是否等于要查找的数据，如果是就返回。
• 如果根结点大于要查找的数据，就在左子树中递归执行查找动作，直到叶子结点。
• 如果根结点小于要查找的数据，就在右子树中递归执行查找动作，直到叶子结点。

总结

• 数据有序存储
• 遍历逻辑复杂一些
• 根据数值查询时间复杂度O(logn)
• 新增时间复杂度O(logn)
• 删除时间复杂度O(logn)

二叉搜索树算法题

应用场景

3.满二叉树

满二叉树，定义为只有最后一层无任何子结点，其他所有层上的所有结点都有两个子结点的二叉树。

4.完全二叉树

完全二叉树，定义为除了最后一层以外，其他层的结点个数都达到最大，并且最后一层的叶子结点都靠左排列。

之所以称为完全二叉树，是从存储空间利用效率的视角来看的。对于一棵完全二叉树而言，仅仅浪费了下标为 0 的存储位置。而如果是一棵非完全二叉树，则会浪费大量的存储空间。

存储结构

• 链式存储法

  也就是像链表一样，每个结点有三个字段，一个存储数据，另外两个分别存放指向左右子结点的指针

• 顺序存储法-数组

  按照规律把结点存放在数组里，如下图所示，为了方便计算，我们会约定把根结点放在下标为 1 的位置。随后，B 结点存放在下标为 2 的位置，C 结点存放在下标为 3 的位置，依次类推。

  结点 X 的下标为 i，那么 X 的左子结点总是存放在 2 * i 的位置，X 的右子结点总是存放在 2 * i + 1 的位置。

  

5.二叉堆

介绍

特点：

• 二叉堆是一棵完全二叉树

• 堆中某个节点的值总是不大于其父节点的值（所以也叫做大根堆），或者堆中某个节点的值总是不小于其父节点的值（所以也叫做小根堆）

• 注意：层次大的元素值不一定小于层次小的元素

数据操作

建立堆

从倒数第一个非叶子节点（22）开始shift-Down，直到所有非叶子节点。

时间复杂度：O(n)

新增

• 添加元素，依据完全二叉树，添加在最后

• 递归Shift Up，递归地和父节点比较，交换

时间复杂度：O(logn)

删除

• 取出最大元素
• 完全二叉树最后的值放到堆顶
• 递归Shift down，堆顶递归的与孩子节点比较并交换

时间复杂度：O(logn)

6.红黑树 TODO

7.前缀（字典）树 Trie

介绍

字符串集合的前缀进行合并，每个根结点到叶子结点的链条就是一个字符串。

特点：

第一，根结点不包含字符；

第二，除根结点外每一个结点都只包含一个字符；

第三，从根结点到某一叶子结点，路径上经过的字符连接起来，即为集合中的某个字符串。

字典树算法题

输入一个字符串，判断它在已有的字符串集合中是否出现过?（假设集合中没有某个字符串与另一个字符串拥有共同前缀且完全包含的特殊情况，例如 deep 和 dee。）

8.线段树

介绍

一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和。

适用于数据很多，而且需要频繁更新并求和的操作。

更新数组里某个元素的数值，时间复杂度 O(logn)。

对数组某个区间段里的元素进行求和，时间复杂度O(logn)

LeetCode 315. TODO

9.树状数组