我不知道如何问这个问题，但我会尝试。
所以我实现了一个 AVL 树，它的复杂度为 O(log n)。
我想在其上应用一些功能，但为了做到这一点，我必须允许我的键在某个时刻具有相同的值(这意味着没有唯一的键)。换句话说，如果我添加一个数字为 4 的键(key = 4)，我可以对另一个数字为 4 的键进行插入(另一个键 = 4)。
最终我的树将是，根中的 X，左子树的值小于 X，右子树的值大于或 EQUAL 到 X。(或者显然可以允许 EQUAL 到左子树而不是到右侧)。
我的问题是，我知道这仍然会被视为二叉搜索树，但它仍然会被视为 AVL 树吗？所有操作的复杂度都是 O(log n)？我的意思是这个平等的事情不会影响任何事情？或者我错过了什么!？
非常感谢大家
最佳答案
AVL树不需要键的唯一性。它对元素类型所需的唯一操作是操作<，即使在您可以认为相等的键的情况下，这也是一个有效的操作。你是对的，左子树将由小于的键组成，但右子树项目将具有“不小于”的值(逻辑上应该大于或等于，但甚至不需要元素具有平等或伟大的概念)。
对于 C++，std::multiset 不需要键的唯一性，并且可以实现为 AVL 树。
剩下的取决于您的实现。
关于c++ - AVL 树的不同节点中的键值可以相同吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56474065/