本章总结
本章介绍了“树”数据结构， 我们讨论了如下算法：
用于表达式解析和求值的二叉树
用于实现ADT Map的二叉查找树BST树
改进了性能， 用于实现ADT Map的平衡二叉查找树AVL树
实现了“最小堆”的完全二叉树： 二叉堆
ADT Map的实现方法小结
我们采用了多种数据结构和算法来实现ADT Map， 其时间复杂度数量级如下表所示：
| 方法 | 有序表 | 散列表 | 二叉查找树 | AVL树 |
|---|---|---|---|---|
| put | O(n) | O(1) -> O(n) | O(log2n) -> O(n) | O(log2n) |
| get | O(log2n) | O(1) -> O(n) | O(log2n) -> O(n) | O(log2n) |
| in | O(log2n) | O(1) -> O(n) | O(log2n) -> O(n) | O(log2n) |
| del | O(n) | O(1) -> O(n) | O(log2n) -> O(n) | O(log2n) |
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: