Pema e plotë binare kundrejt pemës së plotë binare
Pema binare është një pemë ku çdo nyje ka një ose dy fëmijë. Në një pemë binare, një nyje nuk mund të ketë më shumë se dy fëmijë. Në një pemë binare, fëmijët emërtohen si fëmijë "të majtë" dhe "djathtas". Nyjet e fëmijëve përmbajnë një referencë për prindin e tyre. Një pemë binare e plotë është një pemë binare në të cilën çdo nivel i pemës binare është plotësisht i mbushur me përjashtim të nivelit të fundit. Në nivelin e paplotësuar, nyjet bashkohen duke filluar nga pozicioni më i majtë. Një pemë e plotë binare është një pemë në të cilën çdo nyje në pemë ka dy fëmijë përveç gjetheve të pemës.
Çfarë është Pema binare e plotë?
Pema binare e plotë është një pemë binare në të cilën çdo nyje në pemë ka saktësisht zero ose dy fëmijë. Me fjalë të tjera, çdo nyje në pemë përveç gjetheve ka saktësisht dy fëmijë. Figura 1 më poshtë përshkruan një pemë të plotë binare. Në një pemë binare të plotë, numri i nyjeve (n), numri i nyjeve (l) dhe numri i nyjeve të brendshme (i) lidhet në një mënyrë të veçantë, kështu që nëse njihni ndonjë prej tyre, mund të përcaktoni dy të tjerët. vlerat si më poshtë:
1. Nëse një pemë binare e plotë ka i nyje të brendshme:
– Numri i gjetheve l=i+1
– Numri total i nyjeve n=2i+1
2. Nëse një pemë binare e plotë ka n nyje:
– Numri i nyjeve të brendshme i=(n-1)/2
– Numri i gjetheve l=(n+1)/2
3. Nëse një pemë binare e plotë ka l gjethe:
– Numri total i nyjeve n=2l-1
– Numri i nyjeve të brendshme i=l-1
Çfarë është Pema binare e plotë?
Siç tregohet në figurën 2, një pemë binare e plotë është një pemë binare në të cilën çdo nivel i pemës është plotësisht i mbushur me përjashtim të nivelit të fundit. Gjithashtu, në nivelin e fundit, nyjet duhet të ngjiten duke filluar nga pozicioni më i majtë. Një pemë binare e plotë me lartësi h plotëson kushtet e mëposhtme:
– Nga nyja rrënjësore, niveli mbi nivelin e fundit përfaqëson një pemë binare të plotë me lartësi h-1
– Një ose më shumë nyje në nivelin e fundit mund të kenë 0 ose 1 fëmijë
– Nëse a, b janë dy nyje në nivelin mbi nivelin e fundit, atëherë a ka më shumë fëmijë se b nëse dhe vetëm nëse a ndodhet majtas nga b
Cili është ndryshimi midis Pemës së plotë binare dhe pemës së plotë binare?
Pemët binare të plota dhe pemët binare të plota kanë një ndryshim të qartë. Ndërsa një pemë binare e plotë është një pemë binare në të cilën çdo nyje ka zero ose dy fëmijë, një pemë binare e plotë është një pemë binare në të cilën çdo nivel i pemës binare është plotësisht i mbushur me përjashtim të nivelit të fundit. Disa struktura të veçanta të të dhënave si grumbujt duhet të jenë pemë të plota binare ndërsa nuk kanë nevojë të jenë pemë të plota binare. Në një pemë të plotë binare, nëse e dini numrin e nyjeve totale ose numrin e nyjeve ose numrin e nyjeve të brendshme, mund t'i gjeni shumë lehtë dy të tjerat. Por një pemë binare e plotë nuk ka një veti të veçantë që lidhet me këto tre atribute.
