|
Навигация
|
Главная » Delphi Нисходящие Б-деревья в DelphiИсточник: codingrus Kest Процедура добавления нового элемента к Б-дереву сначала рекурсивно отыс-кивает по всему дереву сегмент, в который нужно поместить элемент. Когда она пытается вставить новый элемент на свое место, ей может понадобиться разбить блок и переместить один из элементов узла в его родительский узел. При возврате из рекурсивных вызовов вызывающая процедура проверяет, требуется ли разбиение родительского узла. Если не нет, то элемент помещается в родительский узел. При каждом возврате из рекурсивного вызова вызываю- щая процедура должна проверять, не требуется ли разбиение следующего роди- теля. Поскольку разбиение сегментов происходит, когда процедура заканчивает рекурсивное обращение, такой процесс называется восходящей рекурсией. Б-де- ревья, управляемые таким образом, иногда называются также восходящими Б-де- ревъями (bottom-up B-tree). Альтернативная стратегия состоит в том, чтобы разбить любые полные узлы, встречающиеся на пути вниз. Когда процедура ищет сегмент, чтобы поместить в него новый элемент, она разбивает встречающийся узел, который уже заполнен. Каж- дый раз при дроблении узла она передает элемент в родительский узел. Так как ; все расположенные выше полные узлы уже разбиты, то в родительском узле все- гда есть место для нового элемента. Когда процедура достигает листа, в который нужно поместить элемент, в ро- дительском узле обязательно будет место для размещения нового элемента. Если программа должна разбить лист, то всегда есть место для размещения среднего элемента листа в родительском узле. Поскольку эта система работает от вершины вниз, этот тип Б-деревьев называется нисходящим Б-деревом (top-down B-trees). При этом разбиение блоков происходит чаще, чем необходимо. Нисходящее Б-дерево разбивает полный узел, даже если в его дочерних узлах достаточно много свободного места. При нисходящем методе дерево содержит большее количество пустых записей, чем при восходящем. С другой стороны, разбивая узлы заранее, этот метод сокращает риск возникновения длинного каскада разбиений сегментов. К сожалению, не существует нисходящей версии объединения узлов. Проце- дура удаления узлов не может объединять встречающиеся полупустые узлы на пути вниз, потому что в этот момент еще неизвестно, нужно ли будет объединить два дочерних узла и удалить элемент из их родителя. Поскольку также неизвест- но, будет ли удален элемент из родительского узла, нельзя заранее сказать, потре- буется ли слияние родителя с одним из узлов, находящимся на том же уровне. Рекомендации по подготовке к экзаменам Borland. Вызов Delphi DLL из MS Visual C++ (исходники). Создание WEB-приложений в среде Delphi (исходники). Crypt - Delphi программа для шифрования (исходники). FAQ Конференции VBStreets (FAQ). Главная » Delphi |
© 2024 Team.Furia.Ru.
Частичное копирование материалов разрешено. |