C++(数据结构与算法):66---平衡搜索树总体概述

一、平衡树概述

  • 接下来几篇文章将会介绍平衡树结构:
    • 树的高度为O(C++(数据结构与算法):66---平衡搜索树总体概述)
    • 其中有两种平衡二叉树结构:AVL和红黑树。它们适合内部存储的引用
    • 一个树结构:B-树,它的度大于2。其适合外部存储的引用(例如,存储在磁盘上的大型字典)
    • 上面这些平衡树结构可以在最坏情况下用时O(logn)实现字典操作和按名次的操作。当用索引平衡树表示线性表时,操作get、insert、erase的用时为O(logn)
    • 分裂树:高度为O(n),而且在分裂树上的单个字典操作用时为O(n),但是每一个含有u个操作票的序列,其用时仅为O(ulogu)

二、各种字典结构的渐近时间新能比较

  • 下面用到的函数都是Θ的

C++(数据结构与算法):66---平衡搜索树总体概述

三、总结

  • STL的map和multimap使用的是红黑树结构,以保证查找、插入、删除操作都具有对数级的时间性能
  • 关于实际的运行时间性能,AVL和红黑树是相似的;相比之下,分裂树在实施一个含有u个操作的序列时,用时比较少。另外,分裂树的实现方法比较简单
  • AVL和红黑树都是用“旋转”来保持平衡:
    • AVL树对每个插入操作最多需要一次旋转,对每个删除操作最多需要O(logn)次旋转
    • 红黑树对每次插入和删除操作,都只需要一次旋转
    • 这种差别在大多数应用中无关紧要,因为一次旋转仅需用时Θ(1)。但是对那些需要平衡的应用,一次旋转不能在常量时间内完成,这种差别就非常重要了。例如,平衡优先搜索树(McCreight)就是这样一种应用。平衡优先搜索树用于描述具有二维关键字的元素,此时,每个关键字是一数对(x,y)。它是关于y的优先队列,同时又是关于x的搜索树。在这样的树中,每一次旋转都需要耗时O(logn)。如果用红黑树来描述平衡优先搜索树,则因为每一次插入或杀出仅需要一次旋转,所欲插入或删除操作的总时间仍然为O(logn)。当使用AVL树时,则删除操作的时间将变为O(C++(数据结构与算法):66---平衡搜索树总体概述)
  • 虽然对比较小的可以在内存中处理的字典,AVL树、红黑树和分裂树均能提供比较高的性能,但是对大型字典,它们就不适合了。当字典存储在磁盘上时,需要使用度数更大、高度更小的搜索树,例如B-树
C++(数据结构与算法):66---平衡搜索树总体概述C++(数据结构与算法):66---平衡搜索树总体概述 江南、董少 博客专家 发布了1349 篇原创文章 · 获赞 884 · 访问量 25万+ 他的留言板 关注
上一篇:算法之【红黑二叉树】


下一篇:C++小工修炼手册XXVIII------AVL(平衡二叉搜索树)超级详细