а перейменувати тип, наприклад, в ulong:
typedefunsignedlong ulong;
2.3 Вставка об'єкта в дерево
Розглянемо вставку об'єкта в дерево. Перший елемент вставляється в порожнє дерево тому необхідно ініціалізувати кореневу вершину і потім вставити об'єкт в цю вершину. Вставка наступних об'єктів буде проводиться до тих пір, поки не заповниться масив покажчиків. Крім того, вставка буде відбувається із збереженням впорядкованості. (Малюнок 3)
В
Малюнок 3. Ілюстрація вставки об'єктів в кореневу вершину
структура двійковий файл шаблон
Далі можливі два випадки: перший - значення об'єкта знаходиться в межах інтервалу значень кореневої вершини, другий - значення об'єкта або менше всіх значень вершини, або більше.
У першому випадку необхідно вставити об'єкт між двома іншими зі збереженням упорядкованості. Для цього необхідно витіснити вже існуючий об'єкт у вершині або вправо, або вліво. Напрямок витіснення залежить від того, куди вставляється новий об'єкт. Визначено наступний правила: якщо вставка відбувається між 0м і 1м або 1м і 2м елементами, то має місце витіснення ліворуч, інакше витіснення праворуч. p align="justify"> Об'єкти, що не потрапили в проміжок значень повної вершини, і витіснення об'єкти вставляються рекурсивно в лівий або правий нащадок за правилами вставки в кореневу вершину.
В
Малюнок 4. Правило витіснення
В
Малюнок 5. Приклад вставки з витісненням
2.4 Видалення об'єкта
Пошук об'єкта для видалення підпорядковується правилам пошуку місця для вставки об'єкта, визначеним у минулому пункті. Коли об'єкт знайдений, то потрібно всього лише стерти покажчик на цей об'єкт в масиві покажчиків і змістити решта вліво. Фактично об'єкт не віддалиться і займатиме пам'ять у файлі. Це свого роду "витік пам'яті" у файлі. Щоб не накопичувалося багато "сміття", необхідно періодично проводити стиск файлу. Про це детальніше у пункті 2.5
В
Малюнок 6. Просте видалення об'єкта
У міру видалення об'єктів з дерева можливі наступні випадки: кінцева вершина порожня (малюнок 7), проміжна вершина порожня (малюнок 8). Для першого нагоди всього лише необхідно обнулити покажчик на вершину. У другому випадку потрібно "зібрати" всі об'єкти з поддерева в масив і побудувати нове піддерево. Тільки в цьому випадку можливе утворення великої кількості "сміття", наприклад, якщо спорожніла коренева вершина, тому необхідно проводити стиснення. br/>В
Малюнок 7. Видалення кінцевий вершини
В
Малюнок 8. Видалення проміжної вершини
Варто відзначити особливість вставки об'єкта в вершину, яка стала неповною після видалення об...
