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