Рассмотрим следующую задачу. Дано $n$ ящиков, пронумерованных числами от $1$ до $n$, в каждом из которых лежит несколько шариков. Известно, что $n$ достаточно велико. Нам нужно уметь быстро выполнять следующие операции:
Каждый узел дерева 2-3-4 имеет до четырех байтовых точек и трех элементов данных.Цифра 2, 3, 4 в имени указывает количество дочерних узлов, которые может содержать узел. Есть три возможных сценария для нелистовых узлов:
① Узел с одним элементом данных всегда имеет два дочерних узла;
② Узел с двумя элементами данных всегда имеет три дочерних узла;
③ Узел с тремя элементами данных всегда имеет четыре дочерних узла;
Короче говоря, количество дочерних узлов нелистового узла всегда на один элемент данных больше, чем он содержит. Если количество дочерних узлов равно L, а количество элементов данных равно D, то: L = D + 1
Структуры данных типа “дерево” исключительно широко используются в программной индустрии. В отличие от списковых структур деревья относятся к нелинейным структурам. Любое дерево состоит из элементов – узлов или вершин, которые по определенным правилам связаны друг с другом рёбрами. В списковых структурах за текущей вершиной (если она не последняя) всегда следует только одна вершина, тогда как в древовидных структурах таких вершин может быть несколько . Математически дерево рассматривается как частный случай графа, в котором отсутствуют замкнутые пути (циклы).
Дерево является типичным примером рекурсивно определённой структуры данных, поскольку оно определяется в терминах самого себя.
Рекурсивное определение дерева с базовым типом Т – это:
Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны 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, представляющее собой дерево с несколькими ветвлениями, и каждый узел имеет до четырех дочерних узлов и три элемента данных.