2-3 дерева, хранение данных

Question

Привет всем, я пытаюсь понять, как работают 2-3 дерева, я понял понятие о ключах, но где я на самом деле храню данные, только в листьях или в узлах с 1 ключом (внутренний узел), и 2 ключа (внутренний узел) также, заранее спасибо

Answer 1

Есть примеры, когда сами данные хранятся только в листьях, а внутренние узлы хранят указатели (см. Структуры данных и алгоритмы , автор Aho, Hopcroft & Ullman) i

Структура данных, алгоритмы вставки и удаления одинаковы (но для деталей), и хотя требование к пробелу может быть вдвое больше, чем в приведенных выше примерах, высота дерева увеличится только на 1, поэтому у вас все еще есть очень хорошие времена поиска.

Answer 2

Отказ от ответственности: я не использовал эту структуру данных;но статья Википедии довольно ясна.

Данные хранятся в виде полей 1 или 2 на каждом узле, внутреннем или листовом;Я думаю, что вы называете «ключами» именно те данные, которые вы пытаетесь сохранить.Каждый внутренний узел с двумя дочерними элементами имеет один элемент данных;этот элемент больше, чем все элементы, произошедшие от его левого потомка, и меньше или равен всем элементам, произошедшим от его правого потомка (left < data <= right).В случае 3-дочернего узла данные таковы: left < data_1 <= middle < data_2 <= right.

Answer 3

Я не эксперт по этой древовидной структуре, но первое предложение со страницы Википедии о 2-3 Деревья , кажется, отвечает на ваш вопрос о том, где хранятся данные:

2-3 дерева в информатике тип структуры данных, дерево где каждый узел с детьми (внутренний узел) имеет либо двух детей и одного элемент данных (2-узлы) или три дети и два элемента данных (3-узлов).

Мне кажется, вы храните данные в каждом узле дерева. На странице Wiki также есть ссылка на Java-апплет, демонстрирующий вставки .

РЕДАКТИРОВАТЬ: После прочтения вашего комментария и повторного поиска примера кода, я склонен думать, что ваши данные и ключ (как вы его называете) - это одно и то же (как Чоулетт упомянул в своем ответе).

Глядя на этот пример кода (они хранят только целые числа), я бы создал класс twoThreeNode, который содержит указатели на сохраняемые вами данные, гарантируя, что класс данных имеет перегруженные операторы сравнения, что позволяет им быть отсортирован. Затем следуйте алгоритму, как и раньше.

Я нашел интересную статью с исходным кодом здесь: Сбалансированные деревья, Часть 2: Внутренние деревья 2-3