数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学数据结构中搜索树的比较
在这里，我们将看到一些搜索树及其区别。存在许多不同的搜索树，它们本质上有所不同。基本的搜索树是二叉搜索树 (BST)。其他一些搜索树包括 AVL 树、B 树、红黑树、伸展树等。
这些树可以根据它们的运算进行比较。我们将看到这些树的时间复杂度。
| 搜索树 | 平均情况 | ||
|---|---|---|---|
| 插入 | 删除 | 查找 | |
| 二叉搜索树 | O(log n) | O(log n) | O(log n) |
| AVL树 | O(log2 n) | O(log2 n) | O(log2 n) |
| B树 | O(log n) | O(log n) | O(log n) |
| 红黑树 | O(log n) | O(log n) | O(log n) |
| 伸展树 | O(log2 n) | O(log2 n) | O(log2 n) |
| 搜索树 | 最坏情况 | ||
|---|---|---|---|
| 插入 | 删除 | 查找 | |
| 二叉搜索树 | O(n) | O(n) | O(n) |
| AVL树 | O(log2 n) | O(log2 n) | O(log2 n) |
| B树 | O(log n) | O(log n) | O(log n) |
| 红黑树 | O(log n) | O(log n) | O(log n) |
| 伸展树 | O(log2 n) | O(log2 n) | O(log2 n) |
更新于：2019年8月27日
2K+ 次浏览
广告