# 数据结构
# 线性表
- 节点之间的连接线段称为边(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) 。
图例:
# 图
:图形结构。包含一些用边连接的节点。
- 如果两个节点直接相连,则称为相邻。
- 线下结构属于树形结构,而树形结构属于图形结构。
- 如果图形结构中的节点存在层级关系,则形成了树形结构。
- 如果树形结构中只存在一条路径,则形成了线形结构。