Ръководство за начинаещи по бинарни дървета

Ако сте посещавали курс по структури от данни във вашата степен по компютърни науки или сте програмист-самоук, има вероятност сте попаднали на термина „двоични дървета“. Въпреки че може да звучат малко преобладаващо и сложно, концепцията за двоично дърво е доста проста.

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

Какво представляват двоичните дървета?

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

Първият възел в двоично дърво се нарича „корен“. Възлите на последното ниво в дърво се наричат ​​листа.

Всеки възел съдържа елемент от данни и два указателя на възел. Празно двоично дърво е представено с нулев указател. Както може би вече сте разбрали, двоичните дървета могат да имат само две деца (оттук и името).

Видове двоични дървесни структури

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

Свързани: Най -добрите начини да научите как да кодирате безплатно

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

Важно е да се отбележи, че височината на балансираното двоично дърво е O (logn), където n е броят на възлите в дървото.

В някои случаи, ако всеки възел има само едно ляво или дясно дете, тогава двоичното дърво може да се превърне в изкривено двоично дърво. Тогава той ще се държи като свързан списък, такива дървета се наричат ​​също дегенерирано дърво.

Какво представляват бинарните дървета за търсене?

Двоично дърво за търсене (BST) е по същество подредено двоично дърво със специално свойство, известно като свойството "двоично дърво за търсене". Свойството BST означава, че възли с ключова стойност по -малка от корена са поставени в лявото поддърво, а възли с ключова стойност по -голяма от корена са част от дясното поддърво.

BST свойството трябва да е вярно за всеки следващ родителски възел в дървото.

Двоичните дървета за търсене предлагат бързо вмъкване и търсене. Операциите по вмъкване, изтриване и търсене имат най-лошата времева сложност на O (n), която е подобна на свързан списък.

Ползите от бинарните дървета

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

Също така е много лесно да се внедри и поддържа двоично дърво. Двоичното дърво предлага на програмистите предимствата на подреден масив и свързан списък; търсенето в двоично дърво е толкова бързо, колкото и в сортиран масив, а операциите по вмъкване или изтриване са толкова ефективни, колкото и в свързани списъци.

Двоичните дървета са важни структури от данни

Двоичните дървета са много важна структура от данни и е от решаващо значение програмистите да ги прилагат удобно в своите програми. Често интервюиращите задават прости проблеми с двоично дърво като обхождания, максимална дълбочина, дублиране и др.

Силно препоръчваме да разберете концепцията за двоично дърво и да сте запознати с типичните проблеми на интервюто.

TreeViz: Прост начин за визуализиране на структури от данни

Прочетете Напред

За автора