Может ли дерево AVL иметь одинаковое значение для ключа в разных узлах?

Question

Я не знаю, как спросить это, но я постараюсь.

, поэтому я реализовал дерево AVL, и оно прекрасно работает со сложностью O (log n).

Я хочу применить к нему некоторые функции, но для этого мне нужно, чтобы мои ключи в какой-то момент имели одинаковое значение (что означает отсутствие уникального ключа). Другими словами, если я добавлю ключ с номером 4 (ключ = 4), я могу сделать вставку к другому ключу с номером 4 (еще один ключ = 4).

В конце концов, мое дерево будет, X в корне, левое поддерево имеет значения меньше X, правое поддерево имеет значения больше или EQUAL до X. (Или, очевидно, может разрешить EQUAL к левому поддереву вместо правого).

Мой вопрос: я понимаю, что это все равно будет считаться бинарным деревом поиска, но будет ли оно все еще рассматриваться как дерево AVL? со сложностью O (log n) во всех его операциях? Я имею в виду, что эта РАВНАЯ вещь НЕ повлияет на что-нибудь? или я что-то упустил!?

Большое спасибо, ребята

Answer 1

Дерево AVL не требует уникальности ключей.Единственная операция, которая требуется от типа элементов, - это операция <, и это допустимая операция, даже если ключи можно считать равными.Вы правы, левое поддерево будет состоять из ключей, которые меньше, но правые элементы поддерева будут иметь значения, которые "не меньше чем" (которые по логике должны быть больше или равны, но элемент не требуется даже иметьпонятие равенства или величия). </p>

Что касается C ++, std :: multiset не требует уникальности ключей и может быть реализован в виде дерева AVL.

Остальное зависит отваша реализация.