Дерева по сравнению

1. Основная цель - поиск
2. AVL и красно-черное дерево являются вариантами двоичного дерева поиска.
3. Дерево AVL строго сбалансировано, а красно-черное дерево сбалансировано черным. Но поддержание баланса требует дополнительных операций, что также увеличивает временную сложность структуры данных, поэтому красно-черное дерево можно рассматривать как компромисс между бинарным деревом поиска и деревом AVL, вы можете попытаться сохранить баланс дерева без Слишком много времени, чтобы сохранить природу структуры данных.
4. AVL подходит для красных и черных деревьев Внутренняя память Использовать
Статистическая производительность красно-черных деревьев лучше, чем AVL, но экстремальная производительность немного хуже.

Каждый узел дерева 2-3-4 имеет до четырех байтовых точек и трех элементов данных.Цифра 2, 3, 4 в имени указывает количество дочерних узлов, которые может содержать узел. Есть три возможных сценария для нелистовых узлов:

① Узел с одним элементом данных всегда имеет два дочерних узла;

② Узел с двумя элементами данных всегда имеет три дочерних узла;

③ Узел с тремя элементами данных всегда имеет четыре дочерних узла;

Короче говоря, количество дочерних узлов нелистового узла всегда на один элемент данных больше, чем он содержит. Если количество дочерних узлов равно L, а количество элементов данных равно D, то: L = D + 1

1. 2-3-4 дерева введение

2. Поиск 2-3-4 дерева

3. Вставьте

1. Узел разделения

2. Раскол корня

4. Завершите реализацию исходного кода

5. 2-3-4 дерева и красное черное дерево

①, соответствующие правила

②, эквивалент операции

6. Продуктивность 2-3-4 дерева

Из предыдущего введения мы знаем, что в двоичном дереве каждый узел имеет только один элемент данных, и в нем не более двух дочерних узлов. Если каждому узлу разрешено иметь больше элементов данных и больше дочерних узлов, это дерево с несколькими ветвлениями. В этом блоге мы представим дерево 2-3-4, представляющее собой дерево с несколькими ветвлениями, и каждый узел имеет до четырех дочерних узлов и три элемента данных.