数据结构

线性表

• 节点之间的连接线段称为边（edge）。

树

：树形结构。包含一些用边连接的节点，存在层级关系。

• 特点：

  • 有且仅有一个根节点。
  • 除了根节点以外，其它节点都有且仅有一个父节点。
  • 除了叶子节点以外，其它节点都有一个或多个子节点。

• 图例：

  

• 相关概念：

  • 森林（Forest）：包含多个不相交的树。
  • 根节点：唯一一个没有父节点的节点，是其它节点的父节点或祖父节点。
  • 叶子节点（leaf nodes）：没有子节点的节点，又称为外部节点（external nodes）。
  • 内部节点（internal node）：非叶子节点。
  • 节点的度（degree）：指该节点的子节点个数。
    • 叶子节点的度为 0 。
    • 树中节点的最大度数，称为树的阶数（order）。
  • 节点的路径（path）：指从根节点到该节点依次经过了哪些节点。
  • 节点的深度（depth）：指从根节点（深度为 0 ）往下到该节点经过的边数。
  • 节点的高度（height）：指从叶子节点（高度为 0 ）往上到该节点经过的边数。
    • 树中节点的最大高度（总是根节点），称为树的高度。

二叉树

：Binary Tree

• 特点：每个节点最多有两个子节点，称为左子树、右子树。

二叉树的常见类型：

• 满二叉树（Full Binary Tree）
  • 特点：内部节点都拥有两个子节点。
  • 只存在根节点时，也属于满二叉树。
• 完美二叉树（Perfect Binary Tree）
  • 特点：属于满二叉树，且叶子结点都位于最底一层，即深度相同。
• 完全二叉树（Complete Binary Tree）
  • 特点：叶子结点都位于最底一层，且集中在左侧。
  • 完全二叉树相当于完美二叉树去掉了最底一层的右侧部分叶子节点。
  • 例如上图属于完全二叉树，不属于满二叉树、完美二叉树。
• 平衡二叉树（Balanced Binary Tree）
  • 特点：在同一个父节点下，左子树与右子树的高度差不超过 1 。

遍历

将二叉树转换成线形结构时，有多种遍历方法：

• 层序遍历（level order traversal）
  • ：从上到下逐层遍历，每层从左到右遍历。
  • 上图的遍历顺序是 abcdef 。
• 前序遍历（preorder traversal）
  • ：先访问父节点，再访问左子树的所有节点，最后访问右子树的所有节点。
    • 前序是指父节点最先访问。
    • 对于子树则递归遍历。
  • 上图的遍历顺序是 abdecf 。
• 中序遍历（inorder traversal）
  • ：先访问左子树，再访问父节点，最后访问右子树。
  • 上图的遍历顺序是 dbeafc 。
• 后序遍历（postorder traversal）
  • ：先访问左子树，再访问右子树，最后访问父节点。
  • 上图的遍历顺序是 debfca 。

Python 代码示例：

class Node:
    def __init__(self, name, data=None, left=None, right=None):
        self.name  = name   # 节点名，必须指定
        self.data  = data   # 节点存储的数据，默认为空
        self.left  = left   # 左子节点，默认为空
        self.right = right  # 右子节点，默认为空
    def __repr__(self):
        return "Node('{}')".format(self.name)

def preorder(node):
    """ 前序遍历 """
    if not node:
        return []
    result = []
    result.append(node)
    result.extend(preorder(node.left))
    result.extend(preorder(node.right))
    return result

# 创建各节点
root            = Node('a')
root.left       = Node('b')
root.right      = Node('c')
root.left.left  = Node('d')
root.left.right = Node('e')
root.right.left = Node('f')
# 开始遍历
preorder(root)

改进 Node 的定义：

class Node:
    node_dict = {}    # 记录所有节点
    def __new__(cls, name, *args, **kwargs):
        """ 创建节点时，如果已存在同名节点，则返回其实例 """
        instance = cls.node_dict.get(name)
        if instance:
            return instance
        else:
            instance = super().__new__(cls)
            cls.node_dict[name] = instance
            return instance
    def __init__(self, name, data=None, left=None, right=None):
        self.name  = name
        self.data  = data
        self.left  = left
        self.right = right
    def __repr__(self):
        return "Node('{}')".format(self.name)

Node('a').left  = Node('b')
Node('a').right = Node('c')

• 这里的每个 Node 存放一个数据元素，只需指定节点的 name ，就可找到对应的 data 。
  • 多个 Node 之间通过比较 name 的大小来排序。

排序

二叉树常见的排序算法：

• 二叉查找树（Binary Search Tree ，BST）

  • ：一种便于查找节点的二叉树，将所有节点中序排列，即：
    • 左子树的所有节点都小于父节点。
    • 右子树的所有节点都大于父节点。
  • 读取一个节点时，可以根据二分法快速定位，时间复杂度为 O(log n) 。
    • 插入、删除一个节点时，需要先根据二分法定位，然后移动中序的后继节点，比较麻烦。
  • 如果二叉查找树只存在一条路径，呈线形结构，则定位的时间复杂度为 O(n) 。
    • 使用 AVL tree 可以保证树的自平衡，避免这种情况。

• AVL tree

  • ：一种自平衡的二叉查找树。
  • 每个节点会记录自己的平衡因子，其值等于左子树的高度 - 右子树的高度，取值范围为 -1、0、1 。
  • 插入、删除节点时，通常需要进行左旋、右旋操作，移动节点的位置，从而维持平衡。

• B tree（B- Tree）

  • ：一种具有自平衡、查找特性的树，不属于二叉树 。特点如下：
    • 叶子结点都位于最底一层。
    • 假设树的阶数为 n ，则每个节点拥有 [n/2, n] 个子节点。
    • 每个节点存放最多 n-1 个数据元素。
      • 每个元素以 name:data 键值对形式存储，按升序排列。
      • 根节点可以只存放 1 个元素。
      • 叶子节点的元素数量等于子节点数减一，从而与子节点呈中序排列。
  • 与 AVL tree 相比，B tree 的每个节点存放更多元素，因此减少了节点数，减少了左旋、右旋操作，减少了磁盘 IO 。

• BPlus tree（B+ tree）

  • ：在 B tree 的基础上，增加定义：

    • 内部节点只存放元素 name ，用于索引。其完整的元素 name、data 存放在叶子节点，是叶子节点中的第一个元素。
    • 在最底一层，每个叶子节点会记录相邻的下一个叶子节点的指针，因此形成了线形结构，允许进行更快的顺序遍历。

  • 例：一个 4 阶的 B+ tree 图

    

  • 例：B+ tree 的节点定义

    class BPTreeNode:
        def __init__(self, order):
            self.order      = order   # 记录树的阶数
            self.values     = []      # 一组元素的值
            self.keys       = []      # 一组元素的名称
            self.parent     = None    # 父节点
            self.children   = []      # 一组子节点
            self.next       = None    # 下一个叶子节点
            self.check_leaf = False   # 表示该节点是否为叶子节点
    

• 红黑树（Red-Black Tree，rbtree）

  • ：一种具有自平衡、查找特性的二叉树，采用较弱的平衡条件：
    • 叶子节点为空，只有内部节点存放数据元素。
    • 根节点、叶子节点总是黑色。
    • 其它内部节点可以是黑色或红色，只需要满足以下条件：
      • 每个红色节点的子节点都是黑色。
      • 对于任一节点，从该节点到其各个叶子节点，经过的黑色节点数相同。
  • 与 BST 相比，红黑树的平衡性保证了树中的最长路径不超过最短路径的两倍，因此查找耗时更稳定。
  • 与 AVL tree 相比，红黑树的平衡性较弱，减少了左旋、右旋操作，因此开销更低。

字典树

：又称为前缀树、trie ，是将前缀相同的单词存放在树的同一条路径上，方便查找单词。

• 原理：

  • 除了根节点以外，每个节点存放一个字母。
  • 每个节点可以有任意个子节点，每个子节点存放的字母不同。

• 使用单词的存放路径作为 key ，查找单词的 value 。

  • 树的高度等于最长的一个单词的长度。假设树的高度为 n ，则查找一个单词的时间复杂度为 O(n) 。

• 图例：

  

图

：图形结构。包含一些用边连接的节点。

• 如果两个节点直接相连，则称为相邻。
• 线下结构属于树形结构，而树形结构属于图形结构。
  • 如果图形结构中的节点存在层级关系，则形成了树形结构。
  • 如果树形结构中只存在一条路径，则形成了线形结构。