Пълно двоично дърво срещу пълно двоично дърво
Двоичното дърво е дърво, където всеки възел има едно или две деца. В двоично дърво възелът не може да има повече от две деца. В двоично дърво децата се назовават като „ляво“и „дясно“деца. Дочерните възли съдържат препратка към своя родител. Пълното двоично дърво е двоично дърво, в което всяко ниво на двоичното дърво е напълно запълнено с изключение на последното ниво. В незапълнено ниво възлите са прикрепени, започвайки от най-лявата позиция. Пълно двоично дърво е дърво, в което всеки възел в дървото има две деца, с изключение на листата на дървото.
Какво е пълно двоично дърво?
Пълно двоично дърво е двоично дърво, в което всеки възел в дървото има точно нула или две деца. С други думи, всеки възел в дървото с изключение на листата има точно две деца. Фигура 1 по-долу показва пълно двоично дърво. В пълно двоично дърво броят на възлите (n), броят на лаве (l) и броят на вътрешните възли (i) са свързани по специален начин, така че ако познавате някой от тях, можете да определите другите два стойности, както следва:
1. Ако пълно двоично дърво има i вътрешни възли:
- Брой листа l = i + 1
- Общ брой възли n = 2 * i + 1
2. Ако пълно двоично дърво има n възли:
- Брой вътрешни възли i = (n-1) / 2
- Брой листа l = (n + 1) / 2
3. Ако пълно двоично дърво има l листа:
- Общ брой възли n = 2 * l-1
- Брой вътрешни възли i = l-1
Какво е пълно бинарно дърво?
Както е показано на фигура 2, пълно двоично дърво е двоично дърво, в което всяко ниво на дървото е напълно запълнено с изключение на последното ниво. Също така, на последното ниво, възлите трябва да бъдат прикрепени, започвайки от най-лявата позиция. Пълно двоично дърво с височина h отговаря на следните условия:
- От кореновия възел нивото над последното ниво представлява пълно двоично дърво с височина h-1
- Един или повече възли на последно ниво могат да имат 0 или 1 деца
- Ако a, b са два възела в нивото над последното ниво, тогава a има повече деца от b, ако и само ако a се намира вляво от b
Каква е разликата между Пълно двоично дърво и Пълно двоично дърво?
Пълните двоични дървета и пълните двоични дървета имат явна разлика. Докато пълното двоично дърво е двоично дърво, в което всеки възел има нула или две деца, пълното двоично дърво е двоично дърво, в което всяко ниво на двоичното дърво е напълно запълнено с изключение на последното ниво. Някои специални структури от данни като купчините трябва да бъдат пълни двоични дървета, докато не е необходимо да бъдат пълни двоични дървета. В пълно двоично дърво, ако знаете броя на общите възли или броя на лаверите или броя на вътрешните възли, можете да намерите другите два много лесно. Но пълното двоично дърво няма специално свойство, свързано с тези три атрибута.
