搜索树

目录

• 引入
• 二叉搜索树
• 平衡二叉树（AVL树）
• B树
• 红黑树

引入

使用线性表查找元素的时间复杂度是O(n)；
若使用二分法，平均时间复杂度为O(logn)，但是添加、删除的平均时间复杂度还是O(n)；

所以想到使用二叉树的结构，添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)。

一、二叉搜索树

1 二叉搜索树介绍

二叉搜索树（Binary Search Tree）：一棵二叉树，它可以为空；如果不为空，满足以下性质：

1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.它的左、右子树也分别为二叉排序树。

2 二叉搜索树的问题

二叉搜索树可能退化为链表；当n较大时，一个非常均衡的二叉搜索树和聊表的性能差异非常大。也就是说二叉搜索树非常不稳定。

所以我们寻找一些能让它稳定的措施。

二、平衡二叉树（AVL树）

平衡二叉树（Balanced Binary Tree）具有以下特点：

1.每个节点的左右子树的高度差不超过1
2.搜索、添加、删除的时间复杂度是O(logn)

三、B树 / B-树

B树是平衡的多路搜索树，多用于文件系统、数据库的实现。

m阶B树的性质：（假设一个节点存储的元素个数为x）

1. 根节点：1 <= x <= m - 1；
2. 非根节点：┌m/2┐ - 1 <= j <= m - 1；
3. 如果有子节点，子节点个数：y = x + 1；
4. 每个节点的所有子树高度一致；

四、红黑树

1 定义

红黑树也是一种自平衡的二叉搜索树。

2 红黑树的平衡

那5条性质，可以保证红黑树等价于四阶B树。

（黑色节点和相邻红色节点融合在一起，即形成一个四阶B树节点。）

红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的两倍。（由性质4和性质5可以得到）

3 AVL树 和 红黑树 的比较

平衡标准：

• AVL树平衡标准比较严格：每个左右子树的高度差不超过1
• 红黑树平衡标准比较宽松：没有一条路径会大于其他路径的2倍

时间复杂度：搜索、添加、删除都是O(logn)复杂度

• AVL树添加仅需O(1)次旋转调整、删除最多需要O(logn)次旋转调整
• 红黑树添加、删除仅需O(1)次旋转调整

总结：

• 搜索的次数远远大于插入和删除，选择AVL树；
• 搜索、插入、删除次数几乎差不多，选择红黑树

相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树，实际应用中更多选择使用红黑树。