блоковий спосіб | двійковий спосіб | Індексного-послідовний спосіб | Індексного-довільний спосіб | Розміщення елементів в упорядкованому списку | рандомизация | А б в г д е є ж з и й к л м н о п р с т у ф х ц ч ш щ ь ь и е ю я | Прізвище (ключ) Числове значення ключа | Елементи, пов'язані в ланцюг | Оптимізовані ланцюжка елементів |

загрузка...
загрузка...
На головну

ієрархічні структури

  1. I. Бюрократичні структури управління
  2. II. Адаптивні (органічні) структури управління
  3. Аналіз динаміки складу і структури пасивів балансу.
  4. Аналіз складу і структури власного капіталу організації
  5. Аналіз структури і динаміки резервів

Дерево (або ієрархічна структура) - це кінцеве безліч Т елементів, таке, що виконуються наступні умови:

1. є один спеціально виділений елемент, званий коренем дерева;

2. інші елементи (крім кореня) містяться в m ? 0 попарно не перетинаються множини Т1, .... Тm, Кожне з яких в свою чергу є деревом. дерева Т1, .... Тm є піддеревами даного дерева.

Приклад дерева показаний на малюнку 5:

малюнок 5

Дане дерево представляє склад студентів, наприклад, деякого факультету, із зазначенням навчальних груп, в яких вони значаться. Формально, відповідно до цього вище визначенням, в цьому дереві можна виділити наступні компоненти:

1. вихідне безліч Т = {Студенти, 01-АС, 02-ВТ, 01-ІЕ, Федоров Ф. Ф., Петров П. П., Іванов І.І., Сидоров С. С., Яковлєв Я. Я. };

2. як кореня виступає елемент Студенти;

3. непересічні безлічі в складі:

· Т1 = {01-АС, Федоров Ф. Ф.};

· T2 = {02-ВТ, Петров П. П.};

· Т3 = {01-ІЕ, Іванов І.І., Сидоров С. С., Яковлєв Я. Я.}.

Очевидно, безлічі Т1, Т2, Т3 також є деревами з корінням, відповідно, 01-АС, 02-ВТ, 01-ІЕ. В силу цього можна говорити про те, що дані дерева мають в складі піддерева:

· Корінь - 01-АС, безліч Т1 = {Федоров Ф. Ф.};

· Корінь - 02-ВТ, безліч Т1 = {Петров П. П.};

· Корінь 01-ІЕ, непересічні безлічі Т1 = {Іванов І.І.}, Т2 = {Сидоров С. С.}, Т3 = {Яковлєв Я. Я.}.

Аналогічним чином, можна розглядати вершини, відповідні прізвищами і ініціалами студентів, як вироджені дерева, представлені тільки корінням. Для них виконується умова, коли число непересічних підмножин інших елементів безлічі Т дорівнює 0: m = 0.

Таким чином, в дереві малюнка 5 можна виділити кілька дерев (для кращого розуміння вони виділені в окремі малюнки, коріння показані напівжирним шрифтом). Оскільки дерева виділялися послідовно, з кожним кроком виділення дерев зв'яжемо рівень, починаючи з нульового:

а) вихідне дерево - нульового рівня

б) піддерева першого рівня

в) піддерева другого рівня

малюнок 6

За аналогією з термінологією лінійних списків (див. Розділ лінійні списки), Можна інтерпретувати шифри навчальних груп (т. Е коріння піддерев даного дерева) як вторинні ключі, що визначають безлічі елементів - студентів, що значаться в зазначених групах. Прізвища та ініціали студентів можна розглядати як первинні ключі.

Дамо деякі визначення, які знадобляться нам надалі:

1. рівень ієрархії - Показує, на якому за рахунком кроці виділення дерева сформовані дані коріння дерев;

2. подібні елементи - Елементи (вершини дерева), розташовані на одному рівні ієрархії. Такі елементи, як правило, мають однакову внутрішню структуру;

3. породжені елементи- Елементи (вершини дерева), розташовані на наступному рівні ієрархії;

4. батьківські елементи- Елементи (вершини дерева), розташовані на попередньому рівні ієрархії.

Введені поняття прокоментовані на малюнку 7:

малюнок 7

Традиційними способами організації зберігання ієрархічних структур є: множинні посилання на породжені елементи, посилання на подібні і породжені елементи; кільцеві структури; довідники; бітові відображення.



інвертовані списки | Множинні посилання на породжені елементи
загрузка...
© um.co.ua - учбові матеріали та реферати