Наивная реализация

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями. Рис. 1 Бинарное дерево Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде.

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

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

3. Вставьте

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

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

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

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

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

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

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

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

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

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

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

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

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