时间戳

首页 > 解决方案 > 缺少增强 AVL 树的合并和拆分？

c++ - 缺少增强 AVL 树的合并和拆分？

问题描述

Boost 提供了可以配置boost::container::set/map/multiset/multimap底层二叉搜索树 (BST) 的位置，并且可以选择它作为 AVL 树。

一个（也许是最关键的）原因，为什么人们更喜欢 AVL 树而不是红黑树，是复杂性的merge和操作。但是，令我惊讶的是，它似乎不提供这些操作。文档描述为复杂的元素操作（这与底层 BST 实现无关！？），文档甚至没有提到！splitO(logN)boost::containermergeO(NlogN)split

我不能说关于merge，但至于split，我可以假设缺少它可能是由恒定时间size问题所证明的，因此split复杂性O(logN)可能不知道两个结果部分的大小。但这可以通过具有侵入性容器并保持每个节点的子树节点计数来解决。

也有，但我在文档boost::intrusive::avl_set中找不到 AVLmerge和split算法。

所以问题是。

  1. 是否有一个功能齐全、现成的基于 AVL 的实现，set/map/multiset/multimap它提供merge和split操作的复杂性为O(logN)？
  2. 如果没有，我该如何构建一个使用boost::intrusive::avl_set？

标签： c++data-structuresboostavl-treeintrusive-containers

解决方案

推荐阅读