Топ-100
Back

ⓘ Дърво, структура от данни. Дървото в програмирането е рекурсивна структура от данни, която се състои от върхове, които са свързани помежду си с ребра. За дървет ..




Дърво (структура от данни)
                                     

ⓘ Дърво (структура от данни)

Дървото в програмирането е рекурсивна структура от данни, която се състои от върхове, които са свързани помежду си с ребра. За дърветата са в сила твърденията:

  • Всеки връх може да има 0 или повече преки наследници деца.
  • Всеки връх има най-много един баща. Съществува точно един специален връх, който няма предшественици – коренът ако дървото не е празно.
  • Всички върхове са достижими от корена, т.е. съществува път от корена до всички тях.

В практиката често се налага да работа със съвкупност от обекти данни. Данните, организирани в т. нар. структура от данни, позволяват обработване, така че това да доведе до подобрение качеството на работа с тях. Понякога се добавят елементи, понякога се премахват, друг могат да бъдат подредени по специфичен начин. В програмирането дървото е често използвана структура от данни, която изобразява по естествен начин всякакви йерархии от обекти и тяхната взаимосвързаност.

                                     

1. Терминология

  • Ребро – пряка връзка между два върха.
  • Прародител – връх, който е непряк родител.
  • Родител – предшественик на наследник.
  • Височина на дърво – максималната дълбочина.
  • Корен – Най-важния връх в дървото. Няма предшественици.
  • Вътрешен връх – връх, който има и родител, и дете.
  • Братя – върхове с общ родител.
  • Непряк наследник – връх който не е пряк наследник.
  • Дължина на път – броя на ребрата свързващи върховете.
  • Дете – пряк наследник.
  • Дълбочина на връх – дължината на пътя от корена до върха.
  • Външен връх или листо – връх, който няма наследници.
  • Път – поредица от ребра между върховете.
  • Гора – съвкупност от несвързани дървета.
                                     

2. Описание

Дървото се състои от върхове, а линиите посредством които са свързани се наричат ребра. Върхът, който има наследници деца, но няма родители предшестеници се нарича корен root. Всеки друг връх може да има родител, както и 0 или повече деца. Коренът може да достъпи всеки един връх. Абстрактното разстояние от корена до всяко едно разклонение и всеки връх се нарича път. Един връх не може да има повече от един родител. Следователно в едно дърво не може да има затворен кръг.

                                     

3. Тип на данните срещу структура на данните

Съществува разлика между едно дърво като абстрактен тип данни и като конкретна структура от данни, аналогично на разграничението между списък и свързан списък. Като тип данни, дървото има стойност и деца, като и самите деца са дървета; стойността и децата на дървото се интерпретират като стойността на коренът и на поддървета на синовете на коренът. За да се даде възможност на крайните дървета, списъкът на децата трябва да бъде празен в този случай дърветата може да не бъдат празни, или дърветата да бъдат празни, в този случай списъкът на децата може да бъде с определени размери, каквито пожелаем.

Като структура от данни, свързано дърво е група от възли върхове, където всеки възел има стойност и списък с препратки към други възли наследници. Тази структура данни определя насочена графика, защото може да има цикли или няколко препратки към един и същи възел, както свързания списък може да има цикъл. Следователно не може две препратки да сочат към един и същи възел всеки възел има точно по 1 родител с изключение на корена и дърво което нарушава това е "корумпирано".

Поради използването на препратки към дървета в свързано дърво-структура от данни. Дърветата са често имплицитно обсъждани, приемайки се, че те са представлявани от препратки към корена, тъй като това е често прилагана практика. Например, вместо празно дърво, може да няма препратки:дървото никога не е празно, но препратките към него могат да не съществуват.



                                     

4. Двоично дърво

Дърво, в което броят на наследниците на върховете е 0, 1 или 2 се нарича двоично дърво. Преките наследници на всеки връх са два в този случай, затова единият се нарича ляв наследник, а другият – десен наследник може и празно множество. Те, от своя страна, са корени съответно на лявото поддърво и на дясното поддърво на техния родител.

Има няколко основни операции при двоичните дървета: добавяне, изтриване, търсене, обхождане. Примерите по-долу са написани на Java.

Двоичното дърво в Java изглежда по този начин:

                                     

4.1. Двоично дърво Добавяне

Добавянето на елемент в двоично дърво е операция, която има логаритмична сложност по отношение на размера на дървото. Всеки елемент в двоичното дърво има добре определена позиция, затова първо трябва да намерим къде трябва да го поставим, а после и да го направим. Следва и примера за добавяне:

                                     

4.2. Двоично дърво Търсене

Търсенето изглежда като добавянето и отнема логаритмично време logn.

Двоичното дърво има някои интересни характеристики, позволяващи ни да намерим специални елементи много лесно. Например минималният и максималният елемент. Най-малката стойност е тази, която се намира най-вляво, а максималната – най-вдясно.

                                     

4.3. Двоично дърво Изтриване

Изтриването на елемент от дърво е най-трудната операция. Тя също отнема logn време. Има няколко специални ситуации, които трябва да бъдат овладени:

  • Изтриване на елемент без деца – просто освобождаваме паметта.
  • Изтриване на елемент с две деца – това е най-сложната операция. Най-добрият начин за изпълнение е да бъдат разменени стойностите на изтривания елемент и максималната стойност на лявото поддърво или минималната на дясното поддърво защото това ще запази характеристиките на дървото и тогава да изтрием елемент без или с едно дете.
  • Изтриване на елемент само с едно дете – промяна на указателите на родителя да сочат директно към детето на изтривания елемент и освобождаване на паметта.
  • Изтриване на елемент само с едно дете и това е КОРЕНЪТ – преместване на детето на мястото на корена и освобождаване на паметта.
                                     

4.4. Двоично дърво Обхождане на дърво

Съществуват три типа обхождане на двоични дървета:

  • Postorder – посещаване на лявото поддърво, дясното поддърво и корена.
  • Preorder – посещаване на корена, лявото поддърво и дясното поддърво.
  • Inorder – посещаване на лявото поддърво, корена и дясното поддърво.