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

Дърво (или дървовидна структура) в програмирането е рекурсивна структура от данни, която се състои от върхове, които са свързани помежду си с ребра. За дърветата са в сила твърденията:
В практиката често се налага да работа със съвкупност от обекти (данни). Данните, организирани в т. нар. структура от данни, позволяват обработване, така че това да доведе до подобрение качеството на работа с тях. Понякога се добавят елементи, понякога се премахват, друг могат да бъдат подредени по специфичен начин. В програмирането дървото е често използвана структура от данни, която изобразява по естествен начин всякакви йерархии от обекти и тяхната взаимосвързаност.
Дървото се състои от върхове, а линиите посредством които са свързани се наричат ребра. Върхът, който има наследници (деца), но няма родители (предшестеници) се нарича корен (root). Всеки друг връх може да има родител, както и 0 или повече деца. Коренът може да достигне всеки един връх. Абстрактното разстояние от корена до всяко едно разклонение и всеки връх се нарича път. Един връх не може да има повече от един родител. Следователно в едно дърво не може да има затворен кръг.
Съществува разлика между едно дърво като абстрактен тип данни и като конкретна структура от данни, аналогично на разграничението между списък и свързан списък. Като тип данни, дървото има стойност и деца, като и самите деца са дървета; стойността и децата на дървото се интерпретират като стойността на коренът и на поддървета на синовете на коренът. За да се даде възможност на крайните дървета, списъкът на децата трябва да бъде празен (в този случай дърветата може да не бъдат празни), или дърветата да бъдат празни, в този случай списъкът на децата може да бъде с определени размери, каквито пожелаем.
Като структура от данни, свързано дърво е група от възли (върхове), където всеки възел има стойност и списък с препратки към други възли (наследници). Тази структура данни определя насочена графика,, защото може да има цикли или няколко препратки към един и същи възел, както свързания списък може да има цикъл. Следователно не може две препратки да сочат към един и същи възел (всеки възел има точно по 1 родител с изключение на корена) и дърво което нарушава това е „корумпирано“.
Поради използването на препратки към дървета в свързано дърво-структура от данни. Дърветата са често имплицитно обсъждани, приемайки се, че те са представлявани от препратки към корена, тъй като това е често прилагана практика. Например, вместо празно дърво, може да няма препратки:дървото никога не е празно, но препратките към него могат да не съществуват.
Дърво, в което броят на наследниците на върховете е 0, 1 или 2, се нарича двоично дърво. Преките наследници на всеки връх са два в този случай, затова единият се нарича ляв наследник, а другият – десен наследник (може и празно множество). Те от своя страна са корени съответно на лявото поддърво и на дясното поддърво на техния родител.
Има няколко основни операции при двоичните дървета: добавяне, изтриване, търсене, обхождане. Примерите по-долу са написани на Java.
Двоичното дърво в Java изглежда по този начин:
Добавянето на елемент в двоично дърво е операция, която има логаритмична сложност по отношение на размера на дървото. Всеки елемент в двоичното дърво има добре определена позиция, затова първо трябва да намерим къде трябва да го поставим, а после и да го направим. Следва и примера за добавяне:
Търсенето изглежда като добавянето и отнема логаритмично време (logn).
Двоичното дърво има някои интересни характеристики, позволяващи ни да намерим специални елементи много лесно. Например минималният и максималният елемент. Най-малката стойност е тази, която се намира най-вляво, а максималната – най-вдясно.
Изтриването на елемент от дърво е най-трудната операция. Тя също отнема logn време. Има няколко специални ситуации, които трябва да бъдат овладени:
Съществуват три типа обхождане на двоични дървета: