Complete Binary Tree vs Full Binary Tree
Ang Binary tree ay isang puno kung saan ang bawat node ay may isa o dalawang anak. Sa isang binary tree, ang isang node ay hindi maaaring magkaroon ng higit sa dalawang anak. Sa isang binary tree, ang mga bata ay pinangalanan bilang "kaliwa" at "kanan" na mga bata. Ang mga child node ay naglalaman ng reference sa kanilang magulang. Ang kumpletong binary tree ay isang binary tree kung saan ang bawat antas ng binary tree ay ganap na napuno maliban sa huling antas. Sa unfilled level, ang mga node ay nakakabit simula sa pinakakaliwa na posisyon. Ang full binary tree ay isang puno kung saan ang bawat node sa puno ay may dalawang anak maliban sa mga dahon ng puno.
Ano ang Full Binary Tree?
Full binary tree ay isang binary tree kung saan ang bawat node sa tree ay may eksaktong zero o dalawang anak. Sa madaling salita, ang bawat node sa puno maliban sa mga dahon ay may eksaktong dalawang anak. Ang Figure 1 sa ibaba ay naglalarawan ng isang buong binary tree. Sa isang buong binary tree, ang bilang ng mga node (n), bilang ng mga laves (l) at ang bilang ng mga panloob na node (i) ay nauugnay sa isang espesyal na paraan na kung alam mo ang alinman sa mga ito maaari mong matukoy ang iba pang dalawa. mga halaga tulad ng sumusunod:
1. Kung ang isang buong binary tree ay may mga panloob na node:
– Bilang ng mga dahon l=i+1
– Kabuuang bilang ng mga node n=2i+1
2. Kung ang isang buong binary tree ay may n node:
– Bilang ng mga panloob na node i=(n-1)/2
– Bilang ng mga dahon l=(n+1)/2
3. Kung ang isang buong binary tree ay may l dahon:
– Kabuuang Bilang ng mga node n=2l-1
– Bilang ng mga panloob na node i=l-1
Ano ang Complete Binary Tree?
Tulad ng ipinapakita sa figure 2, ang kumpletong binary tree ay isang binary tree kung saan ang bawat antas ng puno ay ganap na napupuno maliban sa huling antas. Gayundin, sa huling antas, ang mga node ay dapat na nakakabit simula sa pinakakaliwa na posisyon. Ang isang kumpletong binary tree ng taas h ay nakakatugon sa mga sumusunod na kundisyon:
– Mula sa root node, ang antas sa itaas ng huling antas ay kumakatawan sa isang buong binary tree na may taas h-1
– Maaaring may 0 o 1 bata ang isa o higit pang node sa huling antas
– Kung ang a, b ay dalawang node sa antas sa itaas ng huling antas, ang a ay may mas maraming anak kaysa sa b kung at kung ang a ay nasa kaliwa ng b
Ano ang pagkakaiba ng Complete Binary Tree at Full Binary Tree?
Ang mga kumpletong binary tree at full binary tree ay may malinaw na pagkakaiba. Habang ang isang full binary tree ay isang binary tree kung saan ang bawat node ay may zero o dalawang bata, ang isang kumpletong binary tree ay isang binary tree kung saan ang bawat antas ng binary tree ay ganap na napuno maliban sa huling antas. Ang ilang mga espesyal na istruktura ng data tulad ng mga tambak ay kailangang maging kumpletong binary tree habang hindi naman kailangang maging full binary tree ang mga ito. Sa isang full binary tree, kung alam mo ang bilang ng kabuuang mga node o ang bilang ng mga laves o ang bilang ng mga panloob na node, madali mong mahahanap ang dalawa pa. Ngunit ang isang kumpletong binary tree ay walang espesyal na ari-arian na nauugnay sa tatlong katangiang ito.
