ሙሉ ሁለትዮሽ ዛፍ ከሙሉ ሁለትዮሽ ዛፍ
ሁለትዮሽ ዛፍ እያንዳንዱ መስቀለኛ መንገድ አንድ ወይም ሁለት ልጆች ያሉትበት ዛፍ ነው። በሁለትዮሽ ዛፍ ውስጥ አንድ መስቀለኛ መንገድ ከሁለት በላይ ልጆች ሊኖረው አይችልም. በሁለትዮሽ ዛፍ ውስጥ ልጆች "ግራ" እና "ቀኝ" ልጆች ይባላሉ. የሕፃኑ አንጓዎች የወላጆቻቸውን ማጣቀሻ ይይዛሉ። የተሟላ የሁለትዮሽ ዛፍ ከመጨረሻው ደረጃ በስተቀር እያንዳንዱ የሁለትዮሽ ዛፍ ሙሉ በሙሉ የተሞላበት የሁለትዮሽ ዛፍ ነው። ባልተሞላው ደረጃ, አንጓዎቹ ከግራ-ብዙ ቦታ ጀምሮ ተያይዘዋል. ሙሉ ሁለትዮሽ ዛፍ ከዛፉ ቅጠሎች በስተቀር በዛፉ ውስጥ ያለው እያንዳንዱ መስቀለኛ መንገድ ሁለት ልጆች ያሉትበት ዛፍ ነው.
ሙሉ ሁለትዮሽ ዛፍ ምንድነው?
ሙሉ ሁለትዮሽ ዛፍ ሁለትዮሽ ዛፍ ሲሆን በዛፉ ውስጥ ያለ ማንኛውም መስቀለኛ መንገድ በትክክል ዜሮ ወይም ሁለት ልጆች ያሉት ነው። በሌላ አገላለጽ, ከቅጠሎቹ በስተቀር በዛፉ ውስጥ ያለው እያንዳንዱ መስቀለኛ መንገድ በትክክል ሁለት ልጆች አሉት. ከታች ያለው ምስል 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 ከመጨረሻው ደረጃ በላይ ባለው ደረጃ ላይ ሁለት አንጓዎች ከሆኑ፣ ሀ ከ b በላይ ልጆች ያሉት ሲሆን ከ b በስተግራ የሚገኝ ከሆነ ብቻ ነው።
በሙሉ ሁለትዮሽ ዛፍ እና ሙሉ ሁለትዮሽ ዛፍ መካከል ያለው ልዩነት ምንድነው?
የተሟሉ ሁለትዮሽ ዛፎች እና ሙሉ ሁለትዮሽ ዛፎች ግልጽ የሆነ ልዩነት አላቸው። አንድ ሙሉ የሁለትዮሽ ዛፍ ሁለትዮሽ ዛፍ ሲሆን እያንዳንዱ መስቀለኛ መንገድ ዜሮ ወይም ሁለት ልጆች ያሉት ሲሆን, የተሟላ ሁለትዮሽ ዛፍ ከመጨረሻው ደረጃ በስተቀር እያንዳንዱ የሁለትዮሽ ዛፍ ሙሉ በሙሉ የተሞላበት ሁለትዮሽ ዛፍ ነው. እንደ ክምር ያሉ አንዳንድ ልዩ የመረጃ አወቃቀሮች ሙሉ ሁለትዮሽ ዛፎች ሲሆኑ ሙሉ ሁለትዮሽ ዛፎች መሆን አያስፈልጋቸውም። ሙሉ ባለ ሁለትዮሽ ዛፍ ውስጥ, የጠቅላላ ኖዶች ብዛት ወይም የላቭስ ብዛት ወይም የውስጥ ኖዶች ብዛት ካወቁ, ሌሎች ሁለቱን በቀላሉ ማግኘት ይችላሉ. ነገር ግን የተሟላ ሁለትዮሽ ዛፍ ሶስት ባህሪያትን የሚመለከት ልዩ ንብረት የለውም።
