Я хотел бы лучше понять бит бит, но не нашел источник, который может сломать его до моего уровня.Как вставка и удаление быстрее в красном черном дереве, чем дерево AVL?
Я знаю, что для обоих деревьев требуется не более 2 оборотов для каждой вставки. Тогда как вставка быстрее в красно-черных деревьях?
А как для вставки требуются вращения O (log n) в avl-дереве, а O (1) в красно-черном?
Ну, я не знаю, каков ваш уровень, точно, но, проще говоря, красно-черные деревья менее сбалансированы, чем деревья AVL. Для красно-черных деревьев путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа, тогда как для деревьев AVL существует не более одного разности уровней между двумя соседними поддеревьями. Это делает вставки и удаления немного более дорогостоящими в деревьях AVL, но поиск быстрее. Асимптотическое и худшее поведение двух структур данных идентично (время выполнения (не число вращений) равно O (log n) для вставок в обоих случаях, упомянутый O (1) - это так называемый amortized runtime) ,
См. this paragraph для краткого сравнения двух структур данных.
Спасибо, человек! Я смотрел только на максимальные обороты, но не на средний показатель. После работы с несколькими примерами я ясно вижу, что вы сказали. Я не знаю, какая амортизация будет проверена. – user2626445
Вставка и удаление не происходит в красно-черных деревьях. Это обычное ПРЕДПОЛОЖЕНИЕ, и предположение основано на том факте, что красно-черные деревья выполняют немного меньшее количество оборотов в среднем на каждую вставку, чем AVL (0,6 против 7).
Вы можете проверить себя в Java, сравнивая TreeMap (red-black) с этой реализацией TreeMapAVL, и вы можете получить точные числа вместо обычных, но неверных, допущений. https://github.com/dmcmanam/bbst-showdown
Я не знаю, кто этот придурок, проголосовал за этот вопрос! –