data-structures - 使用哈希图平衡 BST？

Question

使用哈希映射而不是指针的 BBST

我正在考虑使用哈希映射实现平衡二叉搜索树的想法。一个实现可以是这样的：哈希映射的键将是插入树中的值，哈希映射的值将是左值、右值和高度的元组（在 AVL 树的情况下）

    10                     H[10] = {7, 15, 2}
   /  \                    H[7]  = {3, 8, 1}
  7    15          --->    H[15] = {nil, 18, 1}
 / \    \                  H[3] = H[8] = H[18] = {nil, nil, 0}
3   8    18 

我不认为它比树的标准实现提供任何优势，除了您可以在恒定时间内搜索值然后搜索任何后继者或任何其他统计信息 BBST 提供的事实。我们已经可以在维护指向节点的哈希映射的帮助下做到这一点，但在我看来，这种实现更容易。

有没有人试过这个？这是个好主意吗？

标签： data-structureshashmapbinary-search-tree

Answer 1

我不能说这是一个好主意还是坏主意，尽管我看不出它有什么特别的好处。在我看来，插入或删除节点会更加复杂，特别是如果你想保持树的平衡。

如果你的树允许重复键，你也会遇到一些真正的麻烦。

我认为您最好使用传统的树结构，如果您需要 O(1) 查找，请添加哈希映射。