одну адресу зв'язку; до будь-якого елементу k-го рівня адресу зв'язку йде тільки від елемента (k- 1)-го рівня. Кількість рівнів у ДСД називають рангом. Елементи дерева, які адресуються від загального елемента (k-1)-го рівня, утворюють групу. Максимальне число елементів у групі називається порядком дерева. Дерева з порядком більше двох прийнято називати загальними ДСД, а з порядком 2 - двійковими, або бінарними деревами. Дерево порядку 1 - рядкова структура. Залежно від кількості елементів в групі деякої вершини розрізняють три типи вершин. Якщо n - порядок дерева, то вершини з n елементів називаються повними, вершини, що не мають групи - кінцевими (листям), а решта - неповними. p align="justify"> Для ДСД можна визначити її двонаправлений і кільцевої варіанти. Якщо в однонаправленому варіанті деяка вершина A має адресу зв'язку на вершину B, то в двунаправленном дереві додатково з'явиться адресу зв'язку від B до A. Якщо все кінцеві вершини дерева мають адресу зв'язку на вершину-корінь, то ДСД називається кільцевої. Найбільш поширеним видом ДСД є бінарні дерева, в яких кожна вершина k-го рівня містить дві адреси (правий і лівий) зв'язку на вершини (k +1)-го рівня і один (зворотний) - на вершину (k-1)-го рівня. Безліч вершин, з'єднаних з даної вершиною через лівий адресу зв'язку, утворює ліву гілку цієї вершини. Аналогічно визначається права гілка. p align="justify"> У разі, коли елементи дерева є записами, найбільш поширеним умовою організації бінарних дерев є впорядкованість. Записи забезпечуються ключами з числовими значеннями. Кожен елемент в упорядкованому бінарному дереві (УБС) має на своїй лівій гілці елементи з меншим, ніж у нього, значенням ключа, а на правій гілці - елементи з більшим чи рівною значенням ключа. p align="justify"> Для загальних ДСД часто використовується різновид: B-дерева (збалансовані дерева) із спеціальним алгоритмом їх формування. В алгоритмі формування УБС дерево росте вниз і корінь його не змінюється, а в алгоритмі формування B-дерева воно росте вгору і його корінь може змінюватися. p align="justify"> Табличні структури даних
Табличні структури даних призначені для зберігання інформації про ключові атрибутах заданого набору елементів, що є записами. Зазвичай це роблять з виділенням в пам'яті 3-х областей: вектора опису записів, вектора опису ключів і матриці значень ключів. p align="justify"> Відсутність деяких ключових атрибутів призводить до незаповненим позиціях у матриці значень ключів. Щоб усунути їх, використовуються спеціальні способи ущільнення (наприклад, за допомогою логічної шкали). Таким чином, виділяються ущільнені і неущільненим табличні структури. p align="justify"> Гібридні структури даних містять фрагменти двох різних структур даних. Наприклад, невеликі за обсягом послідовні структури даних з'єднуються між собою за допомогою адрес зв'язку в рядкову структуру. Гібридні структури даних розрізняються залежно ві...
