የሁለትዮሽ ፍለጋ ዛፍ መተግበር

2024 ደራሲ ደራሲ: Angel Austin | [email protected]. ለመጨረሻ ጊዜ የተሻሻለው: 2023-12-17 05:15

ሁለትዮሽ የፍለጋ ዛፍ - አንጓዎችን የያዘ የተዋቀረ የውሂብ ጎታ፣ ወደ ሌሎች አንጓዎች ሁለት አገናኞች፣ ቀኝ እና ግራ። አንጓዎች የክፍሉ ቁሳቁስ ውሂብ ያለው ነው፣ እና NULL የዛፉን መጨረሻ የሚያመለክት ምልክት ነው።

ብዙውን ጊዜ ልዩ ንብረት ያለው BST ተብሎ ይጠራል፡ ከሥሩ የሚበልጡ አንጓዎች በስተቀኝ እና ትናንሾቹ በስተግራ ይገኛሉ።

አጠቃላይ ፅንሰ-ሀሳብ እና ቃላት

በሁለትዮሽ መፈለጊያ ዛፍ ውስጥ፣ እያንዳንዱ መስቀለኛ መንገድ፣ ሥሩን ሳይጨምር፣ ከአንዱ መስቀለኛ መንገድ ወደ ሌላው በተዘረጋ ጠርዝ ይገናኛል፣ እሱም ወላጅ ይባላል። እያንዳንዳቸው ልጆች ተብለው ከሚጠሩ የዘፈቀደ የአንጓዎች ቁጥር ጋር ሊገናኙ ይችላሉ። "ልጆች" የሌላቸው አንጓዎች ቅጠሎች (ውጫዊ ኖዶች) ይባላሉ. ቅጠሎች ያልሆኑ ንጥረ ነገሮች ውስጣዊ ይባላሉ. ተመሳሳይ ወላጅ ያላቸው አንጓዎች ወንድሞችና እህቶች ናቸው። የላይኛው መስቀለኛ መንገድ ሥር ይባላል. በBST ውስጥ፣ ለእያንዳንዱ መስቀለኛ መንገድ አንድ ኤለመንት መድቡ እና ለእነሱ የተለየ ንብረት እንደተዘጋጀላቸው ያረጋግጡ።

የዛፍ ቃላት፡

የአንድ መስቀለኛ መንገድ ጥልቀት ከሥሩ ወደ እሱ የተገለጹት የጠርዝ ብዛት ነው።
የአንድ መስቀለኛ መንገድ ቁመት ከሱ ወደ ጥልቅ ቅጠሉ የተገለጹት የጠርዝ ብዛት ነው።
የዛፉ ቁመት የሚወሰነው በስሩ ቁመት ነው።
ሁለትዮሽ የፍለጋ ዛፍ ልዩ ንድፍ ነው፣ ምርጡን የከፍታ እና የአንጓዎች ብዛት ሬሾን ያቀርባል።
ቁመት h ከኤን ኖዶች ቢበዛ O (ሎግ N)።

ከነሱ ውስጥ ትልቁን ቁጥር እንደያዘ በማሰብ በየደረጃው ያሉትን ኖዶች በመቁጠር በቀላሉ ማረጋገጥ ይችላሉ፡ n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 ይህንን ለ h መፍታት h=O (log n) ይሰጣል።

የእንጨት ጥቅሞች፡

የመረጃውን መዋቅራዊ ግንኙነቶች ያንጸባርቁ።
ተዋረዶችን ለመወከል ይጠቅማል።
ውጤታማ መጫኑን እና መፈለግን ያረጋግጡ።
ዛፎች በጣም ተለዋዋጭ ውሂብ ናቸው፣ይህም በትንሹ ጥረት ንዑስ ዛፎችን እንዲያንቀሳቅሱ ያስችልዎታል።

የፍለጋ ዘዴ

በአጠቃላይ፣ አንድ እሴት በBST ውስጥ እንዳለ ለማወቅ፣ ሁለትዮሽ የፍለጋ ዛፍ ከሥሩ ይጀምሩ እና መስፈርቶቹን የሚያሟላ መሆኑን ይወስኑ፡

ከሥሩ ይሁኑ፤
በግራ ንዑስ ሥር ይሁኑ፤
በቀኝ ስር ስር።

ምንም የመሠረት መዝገብ ካልረካ፣ ተደጋጋሚ ፍለጋ በተዛመደው ንዑስ ዛፍ ውስጥ ይከናወናል። በእውነቱ ሁለት መሰረታዊ አማራጮች አሉ፡

ዛፉ ባዶ ነው - በውሸት ይመለሱ።
እሴቱ በስር መስቀለኛ መንገድ ውስጥ ነው - እውነት ይመለሱ።

መታወቅ ያለበት ነገር ቢኖር የዳበረ ሼማ ያለው የሁለትዮሽ መፈለጊያ ዛፍ ሁልጊዜ ከሥሩ ወደ ቅጠል በሚወስደው መንገድ መፈለግ ይጀምራል። በጣም በከፋ ሁኔታ ውስጥ, እስከ ቅጠሉ ድረስ ይሄዳል.ስለዚህ, በጣም መጥፎው ጊዜ ከሥሩ እስከ ቅጠሉ ድረስ ካለው ረጅሙ መንገድ ርዝመት ጋር ተመጣጣኝ ነው, ይህም የዛፉ ቁመት ነው. በአጠቃላይ፣ በዛፉ ውስጥ በተከማቹ የእሴቶች ብዛት ለመፈለግ ምን ያህል ጊዜ እንደሚወስድ ማወቅ ያለብዎት በዚህ ጊዜ ነው።

በሌላ አነጋገር፣ በ BST ውስጥ ባሉ የአንጓዎች ብዛት እና በዛፉ ቁመት መካከል እንደ "ቅርፁ" ግንኙነት አለ። በጣም በከፋ ሁኔታ ውስጥ, አንጓዎች አንድ ልጅ ብቻ አላቸው, እና ሚዛናዊ የሁለትዮሽ ፍለጋ ዛፍ በመሠረቱ የተያያዘ ዝርዝር ነው. ለምሳሌ፡

ይህ ዛፍ 5 ኖዶች እና ቁመት=5. ከ16-19 እና 21-29 ባለው ክልል ውስጥ እሴቶችን መፈለግ ከሥሩ ወደ ቅጠሉ (እሴቱን 20 የያዘው መስቀለኛ መንገድ) የሚከተለውን መንገድ ይፈልጋል።, ከአንጓዎች ብዛት ጋር ተመጣጣኝ ጊዜ ይወስዳል. በጥሩ ሁኔታ ሁሉም 2 ልጆች አሏቸው እና ቅጠሎቹ በተመሳሳይ ጥልቀት ላይ ይገኛሉ።

ይህ የሁለትዮሽ መፈለጊያ ዛፍ 7 አንጓዎች እና ቁመት=3. በአጠቃላይ እንደዚህ ያለ ዛፍ (ሙሉ ዛፍ) ቁመት በግምት ሎግ 2 (N) ይሆናል, N በዛፉ ውስጥ ያሉት የአንጓዎች ቁጥር ነው.. የምዝግብ ማስታወሻ 2 (N) ዋጋ ዜሮ ከመድረሱ በፊት N ሊከፋፈል የሚችለው የጊዜ ብዛት (2) ነው።

ማጠቃለያ፡ BST ውስጥ ለመፈለግ በጣም መጥፎው ጊዜ O (የዛፍ ቁመት) ነው። በጣም መጥፎው የ "መስመራዊ" ዛፍ O (N) ነው, N በዛፉ ውስጥ ያሉት የአንጓዎች ቁጥር ነው. ቢበዛ፣ "የተሟላ" ዛፍ O(log N) ነው።

BST ሁለትዮሽ አስገባ

የት መሆን እንዳለበት እያሰቡ ነው።አዲሱ መስቀለኛ መንገድ በ BST ውስጥ ይገኛል, አመክንዮውን መረዳት ያስፈልግዎታል, ተጠቃሚው በሚያገኘው ቦታ መቀመጥ አለበት. በተጨማሪም፣ ህጎቹን ማስታወስ አለብህ፡

ብዜቶች አይፈቀዱም፣ የተባዛ እሴት ለማስገባት መሞከር ልዩ ያደርገዋል።
የወል የማስገቢያ ዘዴ በትክክል ለማስገባት አጋዥ ተደጋጋሚ "ረዳት" ዘዴን ይጠቀማል።
አዲስ እሴት ያለው መስቀለኛ መንገድ ሁልጊዜ በ BST ውስጥ እንደ ቅጠል ይገባል::
የአደባባይ የማስገቢያ ዘዴ ባዶ ይመልሳል፣ነገር ግን አጋዥ ዘዴው BSTnode ይመልሳል። ይህንን የሚያደርገው መስቀለኛ መንገድ ወደ እሱ የተላለፈበትን ጉዳይ ለማስተናገድ ነው።

በአጠቃላይ የረዳት ዘዴው የሚያመለክተው ዋናው የሁለትዮሽ ፍለጋ ዛፍ ባዶ ከሆነ ውጤቱ አንድ መስቀለኛ መንገድ ያለው ዛፍ ነው። ያለበለዚያ ውጤቱ እንደ መከራከሪያ ወደ ተላለፈው ተመሳሳይ መስቀለኛ መንገድ አመላካች ይሆናል።

ስረዛ በሁለትዮሽ ስልተ ቀመር

እርስዎ እንደሚጠብቁት አንድን ኤለመንት መሰረዝ የሚወገድበትን ዋጋ የያዘ መስቀለኛ መንገድ መፈለግን ያካትታል። በዚህ ኮድ ውስጥ ብዙ ነገሮች አሉ፡

BST ረዳትን፣ ከመጠን በላይ የተጫነ የመሰረዝ ዘዴን ይጠቀማል። የሚፈልጉት ንጥረ ነገር በዛፉ ውስጥ ከሌለ የረዳት ዘዴው በመጨረሻ በ n==ባዶ ይባላል። ይህ እንደ ስህተት አይቆጠርም, ዛፉ በቀላሉ በዚህ ጉዳይ ላይ አይለወጥም. የሰርዝ አጋዥ ዘዴው እሴት ይመልሳል - ወደ ተዘመነው ዛፍ ጠቋሚ።
አንድ ቅጠል ሲወገድ፣ከሁለትዮሽ መፈለጊያ ዛፉ መውጣቱ የወላጁን ተዛማጅ ልጅ ጠቋሚ ያስቀምጣል፣ወይም የሚወገደው ከሆነ ሥሩ ይጠፋል።መስቀለኛ መንገድ ሥር ነው ልጆች የሉትም።
ማስታወሻ የመሰረዝ ጥሪው ከሚከተሉት ውስጥ አንዱ መሆን አለበት፡ root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight() ቁልፍ))። ስለዚህ በሶስቱም ሁኔታዎች የመሰረዝ ዘዴው በቀላሉ ባዶ መመለሱ ትክክል ነው።
የሚሰረዝ እሴት የያዘ መስቀለኛ መንገድ ፍለጋ ሲሳካ ሶስት አማራጮች አሉ የሚጠፋው መስቀለኛ መንገድ ቅጠል (ልጆች የሉትም)፣ የሚሰረዘው መስቀለኛ ክፍል አንድ ልጅ አለው፣ ሁለት አለው ልጆች።
የሚወገደው መስቀለኛ መንገድ አንድ ልጅ ሲኖረው፣ በቀላሉ በልጅ መተካት እና ጠቋሚን ለልጁ መመለስ ይችላሉ።
የሚሰረዘው መስቀለኛ መንገድ ዜሮ ወይም 1 ልጆች ካሉት፣ የመሰረዝ ዘዴው ከሥሩ ወደዚያ መስቀለኛ መንገድ "መንገዱን ይከተላል።" ስለዚህ በጣም መጥፎው ጊዜ ከዛፉ ቁመት ጋር ተመጣጣኝ ነው, ለመፈለግም ሆነ ለማስገባት.

የሚወገደው መስቀለኛ መንገድ ሁለት ልጆች ካሉት፣ የሚከተሉት እርምጃዎች ይወሰዳሉ፡

የሚሰረዘውን መስቀለኛ መንገድ አግኝ፣ ከስር ወደ እሱ የሚወስደውን መንገድ በመከተል።
ትንሿን የቪ እሴት በትክክለኛው ንዑስ ዛፍ ያግኙ፣ ወደ ቅጠሉ በሚወስደው መንገድ ላይ ይቀጥሉ።
የቪን እሴትን በተከታታይ ያስወግዱ፣ በደረጃ 2 ላይ ያለውን ተመሳሳይ መንገድ ይከተሉ።
ስለዚህ በጣም በከፋ ሁኔታ ከሥሩ ወደ ቅጠሉ የሚወስደው መንገድ ሁለት ጊዜ ይከናወናል።

የመተላለፊያዎች ቅደም ተከተል

Traversal በዛፍ ውስጥ ያሉትን ሁሉንም አንጓዎች የሚጎበኝ ሂደት ነው። የC ባለ ሁለትዮሽ የፍለጋ ዛፍ መስመራዊ ያልሆነ የውሂብ መዋቅር ስለሆነ፣ ልዩ የሆነ መሻገሪያ የለም። ለምሳሌ, አንዳንድ ጊዜ በርካታ የመተላለፊያ ስልተ ቀመሮችበሚከተሉት ሁለት ዓይነቶች ይመደባል፡

ጥልቀት መሻገር፤
የመጀመሪያ ማለፊያ።

አንድ ዓይነት ስፋት ማቋረጫ ብቻ ነው - ደረጃውን ማለፍ። ይህ ማቋረጫ አንጓዎች ወደታች እና ግራ፣ ላይ እና ቀኝ ይጎበኛል።

ሦስት የተለያዩ ዓይነት ጥልቅ ማቋረጫዎች አሉ፡

ቅድመ-ትዕዛዝ ማለፍ - መጀመሪያ ወላጅ እና ከዚያ ግራ እና ቀኝ ልጅን ይጎብኙ።
በቅደም ተከተል ማለፍ - የግራውን ልጅ፣ በመቀጠል ወላጁን እና ትክክለኛውን ልጅ መጎብኘት።
ከፖስታ ማዘዙን ያለፈ - ግራውን ልጅ መጎብኘት ፣ ከዚያ የቀኝ ልጅ ፣ ከዚያ ወላጅ።

ምሳሌ ለአራት ተዘዋዋሪዎች የሁለትዮሽ የፍለጋ ዛፍ፡

ቅድመ-ትዕዛዝ - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
በትእዛዝ - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
የፖስታ ትዕዛዝ - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
ደረጃ ትዕዛዝ - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

ሥዕሉ አንጓዎች የሚጎበኙበትን ቅደም ተከተል ያሳያል። ቁጥሩ 1 በአንድ የተወሰነ ማቋረጫ ውስጥ የመጀመሪያው መስቀለኛ መንገድ ነው፣ እና 7 የመጨረሻው መስቀለኛ መንገድ ነው።

እነዚህ አጠቃላይ ጉዞዎች እንደ ነጠላ ስልተ ቀመር ሊወከሉ ይችላሉ፣ ይህም እያንዳንዱ መስቀለኛ መንገድ ሶስት ጊዜ እንደሚጎበኝ በማሰብ ነው። የኡለር ጉብኝት በሁለትዮሽ ዛፍ ዙሪያ የሚደረግ የእግር ጉዞ ሲሆን እያንዳንዱ ጠርዝ ተጠቃሚው ሊሻገር እንደማይችል እንደ ግድግዳ ተደርጎ ይቆጠራል። በዚህ የእግር ጉዞ እያንዳንዱ መስቀለኛ መንገድ በግራ ወይም ከታች ወይም በቀኝ በኩል ይጎበኛል. በግራ በኩል ያሉትን አንጓዎች የሚጎበኘው የኡለር ጉብኝት ቅድመ-ዝንባሌው እንዲያልፍ ያደርገዋል። ከታች ያሉት አንጓዎች ሲጎበኙ, በቅደም ተከተል ይሻገራሉ. እና በቀኝ በኩል ያሉት አንጓዎች ሲጎበኙ - ያግኙደረጃ በደረጃ ማለፍ።

አሰሳ እና ማረም

ዛፉን ማሰስ ቀላል ለማድረግ በመጀመሪያ የግራ ወይም የቀኝ ልጅ መሆናቸውን የሚያረጋግጡ ተግባራትን ይፍጠሩ። የመስቀለኛ መንገድን አቀማመጥ ለመለወጥ በወላጅ መስቀለኛ መንገድ ላይ ወደ ጠቋሚው በቀላሉ መድረስ አለበት. ዛፍን በትክክል መተግበር በጣም ከባድ ነው, ስለዚህ የማረም ሂደቶችን ማወቅ እና መተግበር ያስፈልግዎታል. የሁለትዮሽ ፍለጋ ዛፍ ከትግበራ ጋር ብዙ ጊዜ በትክክል የጉዞ አቅጣጫን የማይጠቁሙ ጠቋሚዎች አሉት።

ይህን ሁሉ ለማወቅ ዛፉ ትክክል መሆን አለመቻሉን የሚፈትሽ እና ብዙ ስህተቶችን ለማግኘት የሚረዳ ተግባር ጥቅም ላይ ይውላል። ለምሳሌ፣ የወላጅ መስቀለኛ መንገድ የሕፃን ኖድ መሆኑን ያረጋግጣል። በማስረጃ(is_wellformed(root)) ብዙ ስህተቶች ያለጊዜው ሊያዙ ይችላሉ። በዚህ ተግባር ውስጥ ሁለት የተሰጡ መግቻ ነጥቦችን በመጠቀም፣ የትኛው ጠቋሚ ስህተት እንደሆነ በትክክል ማወቅ ይችላሉ።

ተግባር Konsolenausgabe

ይህ ተግባር መላውን ዛፍ ወደ ኮንሶል ያጥባል እና ስለዚህ በጣም ጠቃሚ ነው። የዛፉ ውጤት ግብ የሚፈጸምበት ቅደም ተከተል፡

ይህን ለማድረግ በመጀመሪያ በመስቀለኛ መንገድ ምን አይነት መረጃ እንደሚወጣ ማወቅ ያስፈልግዎታል።
እንዲሁም ዛፉ ምን ያህል ስፋት እና ርዝመት እንዳለው ማወቅ አለቦት።
የሚከተሉት ተግባራት ይህንን መረጃ ለዛፉ እና ለእያንዳንዱ ንኡስ ዛፍ ያሰላሉ። ወደ ኮንሶል መስመር በመስመር ብቻ መጻፍ ስለሚችሉ የዛፉን መስመር በመስመር ማተም ያስፈልግዎታል።
አሁን የምንወጣበት ሌላ መንገድ እንፈልጋለንዛፉ በሙሉ፣ በመስመር ብቻ አይደለም።
በቆሻሻ ተግባር በመታገዝ ዛፉን በማንበብ የውጤት ስልተ-ቀመርን በከፍተኛ ሁኔታ ማሻሻል ይችላሉ፣ ፍጥነትን በተመለከተ።

ነገር ግን ይህ ተግባር በትልልቅ ዛፎች ላይ ለመጠቀም አስቸጋሪ ይሆናል።

ገንቢ እና አጥፊ

ይቅዱ

ዛፉ ቀላል የመረጃ መዋቅር ስላልሆነ ኮፒ ገንቢ፣ አጥፊ እና የምደባ ኦፕሬተርን መተግበር የተሻለ ነው። አጥፊው በተደጋጋሚ ለመተግበር ቀላል ነው. በጣም ትላልቅ ለሆኑ ዛፎች "የቆሻሻ ፍሳሽን" መቋቋም ይችላል. በዚህ ጉዳይ ላይ, በተደጋጋሚ ተዘጋጅቷል. ሀሳቡ የሁሉም ቅጠሎች ትንሹን ዋጋ የሚወክል ቅጠሉን ማስወገድ ነው, ስለዚህ ከዛፉ በግራ በኩል ነው. የመጀመሪያዎቹን ቅጠሎች መቁረጥ አዲስ ቅጠሎችን ይፈጥራል, እና ዛፉ ሕልውናውን እስኪያቆም ድረስ ይቀንሳል.

የኮፒ ገንቢው እንዲሁ በተከታታይ ሊተገበር ይችላል፣ነገር ግን የተለየ ነገር ከተጣለ ይጠንቀቁ። አለበለዚያ ዛፉ በፍጥነት ግራ የሚያጋባ እና ለስህተት የተጋለጠ ይሆናል. ለዚህም ነው የድግግሞሽ ስሪት ይመረጣል. ሃሳቡ በአጥፊው ላይ እንደምታደርጉት በአሮጌው ዛፍ እና በአዲሱ ዛፍ ውስጥ ማለፍ ነው, በአሮጌው ዛፍ ውስጥ ያሉትን ግን አዲሶቹን ሳይሆን ሁሉንም አንጓዎች በመዝጋት.

በዚህ ዘዴ፣ የሁለትዮሽ ፍለጋ ዛፍ አተገባበር ሁል ጊዜ በጤናማ ሁኔታ ላይ ያለ እና በአጥፊው ባልተሟላ ሁኔታም ቢሆን ሊወገድ ይችላል። የተለየ ሁኔታ ከተፈጠረ, የሚያስፈልግዎ ነገር በከፊል የተጠናቀቀውን ዛፍ እንዲሰርዝ አጥፊውን ማዘዝ ነው. የምደባ ኦፕሬተርቅጂ እና መለዋወጥን በመጠቀም በቀላሉ መተግበር ይቻላል።

ሁለትዮሽ የፍለጋ ዛፍ በመፍጠር ላይ

ምርጥ የሁለትዮሽ ፍለጋ ዛፎች በአግባቡ ከተያዙ በሚያስደንቅ ሁኔታ ውጤታማ ናቸው። ለሁለትዮሽ ፍለጋ ዛፎች አንዳንድ ህጎች፡

የወላጅ መስቀለኛ መንገድ ቢበዛ 2 የልጅ ኖዶች አሉት።
የግራ ልጅ መስቀለኛ መንገድ ሁልጊዜ ከወላጅ መስቀለኛ መንገድ ያነሰ ነው።
የሚሰራ የህፃን ኖድ ሁል ጊዜ ከወላጅ መስቀለኛ መንገድ ይበልጣል ወይም እኩል ነው።

ሁለትዮሽ መፈለጊያውን ዛፍ ለመገንባት የሚያገለግለው ድርድር፡

የሰባት እሴቶች የመሠረት ኢንቲጀር ድርድር ባልተደረደረ ቅደም ተከተል።
በድርድር ውስጥ ያለው የመጀመሪያው ዋጋ 10 ነው፣ስለዚህ ዛፉን ለመገንባት የመጀመሪያው እርምጃ እዚህ እንደሚታየው 10 root node መፍጠር ነው።
ከስር ኖዶች ስብስብ ጋር ሁሉም ሌሎች እሴቶች የዚህ መስቀለኛ መንገድ ልጆች ይሆናሉ። ህጎቹን በማጣቀስ 7 በዛፉ ላይ ለመጨመር የሚወሰደው የመጀመሪያው እርምጃ ከስር መስቀለኛ መንገድ ጋር ማወዳደር ነው።
እሴቱ 7 ከ10 በታች ከሆነ የግራ ልጅ መስቀለኛ መንገድ ይሆናል።
እሴቱ 7 ከ10 የሚበልጥ ወይም የሚተካከል ከሆነ ወደ ቀኝ ይሄዳል። 7 ከ10 በታች እንደሆነ ስለሚታወቅ፣ እንደ ግራ ልጅ መስቀለኛ መንገድ ተወስኗል።
ለእያንዳንዱ አካል ንፅፅሮችን በተከታታይ ያከናውኑ።
ተመሳሳዩን ስርዓተ-ጥለት በመከተል፣ ተመሳሳይ ንፅፅርን በድርድር ውስጥ ካለው 14ኛ እሴት ጋር አከናውን።
እሴቱን 14 ከ root node 10 ጋር በማነፃፀር 14 ትክክለኛ ልጅ መሆኑን በማወቅ።
በአደራደሩ ውስጥ መሄድ፣ወደ 20 ይምጡ.
አደራደሩን ከ 10 ጋር በማነፃፀር ይጀምሩ ፣ከየትኛው ይበልጣል። ስለዚህ ወደ ቀኝ ይሂዱ እና ከ 14 ጋር ያወዳድሩ፣ እድሜው ከ14 በላይ ነው እና በቀኝ በኩል ምንም ልጅ የሉትም።
አሁን የ1 እሴት አለ። እንደሌሎቹ እሴቶች ተመሳሳይ ስርዓተ-ጥለት በመከተል 1 ለ 10 አወዳድር፣ ወደ ግራ በመሄድ እና ከ 7 ጋር በማነፃፀር እና በመጨረሻም የ7ተኛው መስቀለኛ መንገድ 1 ግራ ልጅ።
እሴቱ 5 ከሆነ ከ10 ጋር ያወዳድሩ። 5 ከ10 ያነሰ ስለሆነ ወደ ግራ ይለፉና ከ7 ጋር ያወዳድሩ።
5 ከ7 ያነሰ መሆኑን በማወቅ ከዛፉ ላይ ወደ ታች ቀጥል እና 5ን ከ1 እሴት ጋር አወዳድር።
1 ልጅ ከሌለው እና 5ቱ ከ1 በላይ ከሆኑ 5ቱ ልክ የሆነ ባለ 1 መስቀለኛ መንገድ ልጅ ነው።
በመጨረሻም እሴቱን 8 በዛፉ ላይ አስገባ።
8 ከ10 በታች ሲሆን ወደ ግራ ያንቀሳቅሱት እና ከ 7 ጋር ያወዳድሩ ፣ 8 ከ 7 ይበልጣል እና ወደ ቀኝ ያንቀሳቅሱት እና ዛፉን ያጠናቅቁ ፣ 8 ትክክለኛ የ 7 ልጅ ያድርጉት።

የተመቻቸ የሁለትዮሽ ፍለጋ ዛፎችን ቀላል ውበት ማግኘት እና መገምገም። በፕሮግራም አወጣጥ ውስጥ እንዳሉት ብዙ ርዕሰ ጉዳዮች፣ የሁለትዮሽ የፍለጋ ዛፎች ኃይል የሚመጣው መረጃን ወደ ትናንሽ ተያያዥ አካላት የመፍታት ችሎታቸው ነው። ከአሁን በኋላ፣ ከሙሉ የውሂብ ስብስብ ጋር በተደራጀ መንገድ መስራት ይችላሉ።

የሁለትዮሽ ፍለጋ ጉዳዮች

የሁለትዮሽ የፍለጋ ዛፎች በጣም ጥሩ ናቸው፣ግን ማስታወስ ያለብን ጥቂት ማስጠንቀቂያዎች አሉ። ብዙውን ጊዜ ውጤታማ የሆኑት ሚዛናዊ ከሆኑ ብቻ ነው. ሚዛናዊ የሆነ ዛፍ በውስጡ ያለ ዛፍ ነውበዛፉ ውስጥ በሚገኙት የማንኛውም መስቀለኛ ክፍሎች ከፍታዎች መካከል ያለው ልዩነት ቢበዛ አንድ ነው. ደንቦቹን ለማብራራት የሚረዳ አንድ ምሳሌ እንመልከት። ድርድር እንደ መደርደር እንደጀመረ እናስብ።

በዚህ ዛፍ ላይ የሁለትዮሽ መፈለጊያ ዛፍ አልጎሪዝምን ለማስኬድ ከሞከሩ የሚፈለገው እሴት እስኪገኝ ድረስ በድርድር ውስጥ እየደጋገመ እንደሚሄድ በትክክል ይሰራል። የሁለትዮሽ ፍለጋ ኃይል የማይፈለጉ እሴቶችን በፍጥነት የማጣራት ችሎታ ላይ ነው። ዛፉ ሚዛናዊ ካልሆነ፣ ሚዛናዊ ከሆነው ዛፍ ጋር ተመሳሳይ ጥቅም አይሰጥም።

ሁለትዮሽ የፍለጋ ዛፍ ሲፈጥሩ ተጠቃሚው እየሠራበት ያለውን ውሂብ መመርመር በጣም አስፈላጊ ነው። እሱን ለማመጣጠን የሁለትዮሽ የፍለጋ ዛፍ ለኢቲጀር ከመተግበሩ በፊት እንደ ድርድር randomization ያሉ የዕለት ተዕለት ተግባራትን ማቀናጀት ይችላሉ።

ሁለትዮሽ ፍለጋ ስሌት ምሳሌዎች

25 በሚከተለው ሁለትዮሽ መፈለጊያ ዛፍ ውስጥ ከገባ ምን አይነት ዛፍ እንደሚያመጣ መወሰን አለብን፡

5 15

/ /

2 12 20

x ገና x በሌለው ዛፍ T ውስጥ ሲያስገቡ ቁልፉ x ሁል ጊዜ በአዲስ ቅጠል ውስጥ ይቀመጣል። ከዚህ ጋር ተያይዞ አዲሱ ዛፍ የሚከተለውን ይመስላል፡

5 15

/ /

2 12 20

ወደሚከተለው ሁለትዮሽ የፍለጋ ዛፍ 7 ካስገቡ ምን አይነት ዛፍ ያገኛሉ?

5 15

/ /

2 12 20

መልስ፡

5 15

/ / /

2 7 12 20

ሁለትዮሽ መፈለጊያ ዛፍ ማንኛውንም ነገር ለማከማቸት ጥቅም ላይ ሊውል ይችላል። ከተያያዘ ዝርዝር ይልቅ የሁለትዮሽ መፈለጊያ ዛፍ መጠቀም ጥቅሙ ዛፉ በተመጣጣኝ ሁኔታ ሚዛናዊ ከሆነ እና እንደ "ሙሉ" ዛፍ ከ"ሊነር" የበለጠ ከሆነ ማስገባት, መፈለግ እና ሁሉም የማጥፋት ስራዎች ወደ ውስጥ ለመግባት ሊተገበሩ ይችላሉ. ኦ(ሎግ N) ጊዜ።