Будова дерева сортування


Піраміда (сортувальне дерево, бінарна купа) − бінарне дерево з впорядкованим листям (корінь дерева − найменший чи найбільший елемент). Піраміду можна уявити у вигляді масиву. Перший елемент піраміди є найменшим або найбільшим, що залежить від ключа сортування. Його називають коренем або вершиною піраміди.



Основна властивість бінарного дерева: значення лівого нащадка менше значення батька, а значення правого нащадка більше значення батька для кожного вузла дерева. Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа. Задана послідовність буде впорядкована у низхідному  порядку за   (n-1) кроків.
        Просіювання − це побудова нової піраміди за наступним алгоритмом: новий елемент поміщається у вершину дерева, далі він переміщається ("просівається") по шляху вниз на основі порівняння з дочірніми елементами. Спуск завершується, якщо результат порівняння з дочірніми елементами відповідає ключу сортування.
Принцип побудови дерева має наступний вигляд: якщо надходить черговий елемент масиву, то починаючи з кореня дерева (в залежності від порівняння поточного елемента з черговою вершиною) йдемо вліво або вправо від неї до тих пір, поки не знайдемо відповідну вершину, до якої можна підключити нову вершину з поточним ключем. Залежно від результату порівняння ключів, нову вершину робимо лівої чи правої для знайденої вершини.

Комментариев нет:

Отправить комментарий