вставить Btree с указателями родителей - PullRequest
Новая
       12

вставить Btree с указателями родителей

0 голосов
/ 02 июня 2018

Я пытался написать код вставки в Java для Btree, но не могу правильно разделить узлы, кто-нибудь может подсказать мне хороший алгоритм вставки, разделения и nonfullInset в Btrees?

спасибо

1 Ответ

0 голосов
/ 08 апреля 2019

Для каждого узла:

  • максимальное количество дочерних элементов для D,
  • максимальное количество ключей K = D-1,
  • минимальное количествопотомков d = D / 2,
  • минимальное количество ключей k = D / 2-1

вот алгоритмы:

  • Вставить : поиск в дереве, чтобы найти листовой узел для хранения ключа.Вставьте ключ.Проверьте, не перегружен ли ключ (количество ключей больше, чем D-1), если операция не завершена.При переполнении Разделить узел на 2 узла (сам и новый) переместите последние (k) ключи в новый узел, оставив узел (конечный узел) с ключами k +1.Переместите последний ключ в листовом узле к родительскому.Если родитель переполнен, повторите эти шаги.

  • Удалить : поиск в дереве, чтобы найти узел, содержащий ключ, который вы хотите удалить.Возможны 2 случая.Контейнерный узел является листовым или внутренним неконечным узлом.Если это внутренний узел, сначала найдите непосредственный предшественник ключа в узле, который всегда исходит от ведущего узла.Затем замените ключ этим ключом-предшественником.Теперь вам нужно удалить ключ из листового узла.(обратите внимание, что удаление из внутреннего узла всегда сводится к удалению из конечного узла).Если конечный узел, удалите ключ из конечного узла.Проверьте, не запущен ли конечный узел (имеет менее k ключей), если операция не завершена.Если под полетом, однако возможны 3 случая.Если у узла есть левый брат, у которого есть по крайней мере k + 1 ключей, тогда выполните правое вращение через родителя.Иначе, если у узла есть правый родной брат, у которого есть по крайней мере k + 1 ключей, тогда выполните левый поворот через родителя.Иначе, если у узла нет ни одного родного брата с хотя бы k + 1 ключами, то присоедините узел к одному из его родных братьев, одновременно сбивая ключ у родителя.Затем проверьте, является ли родительский объект недопустимым, если он выпал, повторите эти шаги для исправления родительского элемента.

  • Поиск : аналогично бинарному дереву поиска, основное отличие заключается вчто теперь вам также необходимо выполнить поиск в каждом узле, поскольку каждый узел имеет отсортированные ключи, вы можете выполнить двоичный поиск по каждому узлу.

...