একটি বাইনারি অনুসন্ধান গাছের বাস্তবায়ন

2024 লেখক: Angel Austin | [email protected]. সর্বশেষ পরিবর্তিত: 2023-12-17 05:18

বাইনারী সার্চ ট্রি - একটি স্ট্রাকচার্ড ডাটাবেস যেখানে নোড রয়েছে, অন্য নোডের দুটি লিঙ্ক, ডান এবং বামে। নোড হল ক্লাসের একটি অবজেক্ট যাতে ডেটা থাকে এবং NULL হল সেই চিহ্ন যা গাছের শেষে চিহ্নিত করে৷

এটি প্রায়শই BST হিসাবে উল্লেখ করা হয়, যার একটি বিশেষ বৈশিষ্ট্য রয়েছে: মূলের চেয়ে বড় নোডগুলি এটির ডানদিকে এবং ছোটগুলি বাম দিকে অবস্থিত৷

সাধারণ তত্ত্ব এবং পরিভাষা

একটি বাইনারি অনুসন্ধান গাছে, প্রতিটি নোড, রুট বাদ দিয়ে, একটি নির্দেশিত প্রান্ত দ্বারা একটি নোড থেকে অন্য নোডের সাথে সংযুক্ত থাকে, যাকে প্যারেন্ট বলা হয়। তাদের প্রত্যেকটিকে একটি নির্বিচারে সংখ্যার নোডের সাথে সংযুক্ত করা যেতে পারে, যাকে শিশু বলা হয়। "শিশু" ছাড়া নোডগুলিকে পাতা (বাহ্যিক নোড) বলা হয়। যে উপাদানগুলি পাতা নয় তাদের অভ্যন্তরীণ বলা হয়। একই অভিভাবক সহ নোড ভাইবোন। শীর্ষস্থানীয় নোডটিকে মূল বলা হয়। BST-এ, প্রতিটি নোডে একটি উপাদান বরাদ্দ করুন এবং নিশ্চিত করুন যে তাদের জন্য একটি বিশেষ সম্পত্তি সেট আছে।

গাছের পরিভাষা:

1. একটি নোডের গভীরতা হল মূল থেকে এটিতে সংজ্ঞায়িত প্রান্তের সংখ্যা।
2. একটি নোডের উচ্চতা হল এটি থেকে গভীরতম পাতা পর্যন্ত সংজ্ঞায়িত প্রান্তের সংখ্যা।
3. গাছের উচ্চতা মূলের উচ্চতা দ্বারা নির্ধারিত হয়।
4. বাইনারী সার্চ ট্রি একটি বিশেষ নকশা, এটি উচ্চতা এবং নোডের সংখ্যার সর্বোত্তম অনুপাত প্রদান করে।
5. এন নোড সহ উচ্চতা h সর্বাধিক O (লগ N)।

আপনি রুট থেকে শুরু করে প্রতিটি স্তরে নোডগুলি গণনা করে সহজেই এটি প্রমাণ করতে পারেন, ধরে নিতে পারেন যে এতে তাদের মধ্যে সবচেয়ে বেশি সংখ্যা রয়েছে: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 h এর জন্য এটি সমাধান করলে h=O (লগ n) পাওয়া যায়।

কাঠের উপকারিতা:

1. ডেটার কাঠামোগত সম্পর্ক প্রতিফলিত করুন।
2. অনুক্রমের প্রতিনিধিত্ব করতে ব্যবহৃত হয়।
3. দক্ষ ইনস্টলেশন এবং অনুসন্ধান নিশ্চিত করুন।
4. গাছগুলি খুব নমনীয় ডেটা, যা আপনাকে ন্যূনতম প্রচেষ্টায় সাবট্রিগুলি সরাতে দেয়৷

অনুসন্ধান পদ্ধতি

সাধারণত, একটি মান BST-তে আছে কিনা তা নির্ধারণ করতে, এর মূলে একটি বাইনারি অনুসন্ধান ট্রি শুরু করুন এবং এটি প্রয়োজনীয়তা পূরণ করে কিনা তা নির্ধারণ করুন:

• মূলে থাকা;
• মূলের বাম সাবট্রিতে থাকা;
• মূলের ডান উপবৃক্ষে।

যদি কোন বেস রেজিস্টার সন্তুষ্ট না হয়, একটি পুনরাবৃত্ত অনুসন্ধান সংশ্লিষ্ট সাবট্রিতে সঞ্চালিত হয়। আসলে দুটি মৌলিক বিকল্প আছে:

1. গাছটি খালি - রিটার্ন মিথ্যা।
2. মূল্যটি রুট নোডে রয়েছে - সত্য ফেরত দিন।

এটা লক্ষ করা উচিত যে একটি উন্নত স্কিমা সহ একটি বাইনারি অনুসন্ধান গাছ সর্বদা মূল থেকে পাতার পথ বরাবর অনুসন্ধান শুরু করে। সবচেয়ে খারাপ ক্ষেত্রে, এটি পাতার সমস্ত পথ যায়।অতএব, সবচেয়ে খারাপ সময় হল মূল থেকে পাতা পর্যন্ত দীর্ঘতম পথের দৈর্ঘ্যের সমানুপাতিক, যা গাছের উচ্চতা। সাধারণভাবে, যখন আপনি জানতে চান যে গাছে সংরক্ষিত মানের সংখ্যার ফাংশন হিসাবে দেখতে কতক্ষণ লাগে৷

অন্য কথায়, একটি BST-এ নোডের সংখ্যা এবং একটি গাছের উচ্চতার মধ্যে একটি সম্পর্ক রয়েছে, এটি তার "আকৃতির" উপর নির্ভর করে। সবচেয়ে খারাপ ক্ষেত্রে, নোডের শুধুমাত্র একটি সন্তান থাকে এবং একটি সুষম বাইনারি অনুসন্ধান গাছ মূলত একটি লিঙ্কযুক্ত তালিকা। যেমন:

৫০

/

10

15

30

/

20

এই গাছের 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-তে অবস্থিত, আপনাকে যুক্তিটি বুঝতে হবে, এটি অবশ্যই যেখানে ব্যবহারকারী এটি খুঁজে পাবে সেখানে স্থাপন করতে হবে। এছাড়াও, আপনাকে নিয়মগুলি মনে রাখতে হবে:

1. ডুপ্লিকেট অনুমোদিত নয়, একটি সদৃশ মান সন্নিবেশ করার চেষ্টা করলে একটি ব্যতিক্রম হবে৷
2. সর্বজনীন সন্নিবেশ পদ্ধতি আসলে সন্নিবেশ করার জন্য একটি সহায়ক পুনরাবৃত্ত "সহায়ক" পদ্ধতি ব্যবহার করে৷
3. একটি নতুন মান সম্বলিত একটি নোড সর্বদা বিএসটি-তে একটি পাতা হিসাবে ঢোকানো হয়।
4. সর্বজনীন সন্নিবেশ পদ্ধতি অকার্যকর প্রদান করে, কিন্তু সহায়ক পদ্ধতি একটি BSTnode প্রদান করে। এটি সেই ক্ষেত্রে পরিচালনা করতে করে যেখানে নোডটি শূন্য থাকে।

সাধারণত, সহায়ক পদ্ধতিটি নির্দেশ করে যে যদি মূল বাইনারি অনুসন্ধান ট্রি খালি থাকে, ফলাফলটি একটি নোড সহ একটি গাছ। অন্যথায়, ফলাফলটি একই নোডের একটি পয়েন্টার হবে যা একটি যুক্তি হিসাবে পাস করা হয়েছিল৷

বাইনারী অ্যালগরিদমে মুছে ফেলা

আপনি যেমনটি আশা করতে পারেন, একটি উপাদান মুছে ফেলার সাথে একটি নোড খুঁজে বের করা জড়িত যা মুছে ফেলার মান রয়েছে৷ এই কোডে বেশ কিছু জিনিস আছে:

1. BST একটি সহায়ক, ওভারলোডেড মুছে ফেলার পদ্ধতি ব্যবহার করে। আপনি যে উপাদানটি খুঁজছেন সেটি যদি ট্রিতে না থাকে, তাহলে সহায়ক পদ্ধতিটিকে অবশেষে n==null দিয়ে কল করা হবে। এটি একটি ত্রুটি হিসাবে বিবেচিত হয় না, গাছটি কেবল এই ক্ষেত্রে পরিবর্তন হয় না। ডিলিট হেল্পার পদ্ধতি একটি মান প্রদান করে - আপডেট করা ট্রিতে একটি পয়েন্টার৷
2. যখন একটি পাতা সরানো হয়, বাইনারি অনুসন্ধান গাছ থেকে অপসারণ তার পিতামাতার সংশ্লিষ্ট চাইল্ড পয়েন্টারটিকে শূন্য করে দেয়, অথবা যদি সরানো হয় তবে মূলটিকে শূন্য করে দেয়নোডটি একটি রুট এবং এর কোন সন্তান নেই৷
3. মনে রাখবেন যে ডিলিট কলটি অবশ্যই নিম্নলিখিতগুলির মধ্যে একটি হতে হবে: root=মুছুন (রুট, কী), n.setLeft (delete (n.getLeft (), কী)), n.setRight (delete(n. getRight(), কী))। সুতরাং, তিনটি ক্ষেত্রেই এটি সঠিক যে মুছে ফেলার পদ্ধতিটি কেবল শূন্য প্রদান করে।
4. যখন মুছে ফেলার মান সম্বলিত নোডের অনুসন্ধান সফল হয়, তখন তিনটি বিকল্প রয়েছে: যে নোডটি মুছে ফেলা হবে সেটি একটি পাতা (কোনও সন্তান নেই), যে নোডটি মুছে ফেলা হবে তার একটি শিশু রয়েছে, এতে দুটি রয়েছে শিশু।
5. যখন অপসারণ করা নোডটিতে একটি শিশু থাকে, আপনি কেবল এটিকে একটি শিশু দিয়ে প্রতিস্থাপন করতে পারেন, সন্তানের কাছে একটি পয়েন্টার ফেরত দিতে পারেন৷
6. যদি মুছে ফেলা নোডটিতে শূন্য বা 1টি শিশু থাকে, তাহলে মুছে ফেলার পদ্ধতিটি রুট থেকে সেই নোডে "পথ অনুসরণ করবে"। সুতরাং অনুসন্ধান এবং সন্নিবেশ উভয়ের জন্যই সবচেয়ে খারাপ সময় হল গাছের উচ্চতার সমানুপাতিক৷

যদি অপসারণ করা নোডটির দুটি সন্তান থাকে তবে নিম্নলিখিত পদক্ষেপগুলি নেওয়া হয়:

1. মূল থেকে এটির পথ অনুসরণ করে মুছে ফেলার জন্য নোডটি খুঁজুন।
2. ঠিক সাবট্রিতে v-এর ক্ষুদ্রতম মান খুঁজুন, পাতার পথ ধরে চলতে থাকুন।
3. পুনরাবৃত্তভাবে v এর মান মুছে ফেলুন, ২য় ধাপের মতো একই পথ অনুসরণ করুন।
4. এইভাবে, সবচেয়ে খারাপ ক্ষেত্রে, মূল থেকে পাতার পথ দুবার সঞ্চালিত হয়।

অর্ডার অফ ট্রাভার্স

ট্রাভার্সাল হল একটি প্রক্রিয়া যা একটি গাছের সমস্ত নোড পরিদর্শন করে। যেহেতু একটি সি বাইনারি সার্চ ট্রি একটি নন-লিনিয়ার ডেটা স্ট্রাকচার, সেখানে কোনো অনন্য ট্রাভার্সাল নেই। উদাহরণস্বরূপ, কখনও কখনও বেশ কয়েকটি ট্রাভার্সাল অ্যালগরিদমনিম্নলিখিত দুটি প্রকারে বিভক্ত:

• ক্রসিং গভীরতা;
• প্রথম পাস।

প্রস্থ ক্রসিং মাত্র এক প্রকার - লেভেল বাইপাস। এই ট্রাভার্সাল ভিজিট নোড লেভেল নিচে এবং বাম, উপরে এবং ডানে।

তিনটি ভিন্ন ধরনের গভীরতা ক্রসিং আছে:

1. পাসিং প্রি-অর্ডার - প্রথমে অভিভাবক এবং তারপরে বাম এবং ডান সন্তানের সাথে দেখা করুন।
2. পাসিং ইনঅর্ডার - বাম সন্তান, তারপর পিতামাতা এবং ডান সন্তানের সাথে দেখা করা।
3. Post the Order - বাম সন্তান, তারপর ডান সন্তান, তারপর পিতামাতার সাথে দেখা করা।

একটি বাইনারি অনুসন্ধান গাছের চারটি ট্রাভার্সালের উদাহরণ:

1. প্রি-অর্ডার - ৮, ৫, ৯, ৭, ১, ১২, ২, ৪, ১১, ৩।
2. অর্ডার - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11।
3. পোস্টঅর্ডার - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8।
4. লেভেলঅর্ডার - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2।

চিত্রটি দেখায় যে ক্রমে নোডগুলি পরিদর্শন করা হয়৷ নম্বর 1 হল একটি নির্দিষ্ট ট্রাভার্সালের প্রথম নোড এবং 7 হল শেষ নোড৷

এই সাধারণ ট্রাভার্সালগুলিকে একটি একক অ্যালগরিদম হিসাবে উপস্থাপন করা যেতে পারে, ধরে নেওয়া যায় যে প্রতিটি নোড তিনবার পরিদর্শন করা হয়েছে। অয়লার ট্যুর হল একটি বাইনারি গাছের চারপাশে হাঁটা যেখানে প্রতিটি প্রান্তকে একটি প্রাচীর হিসাবে বিবেচনা করা হয় যা ব্যবহারকারী অতিক্রম করতে পারে না। এই হাঁটার মধ্যে, প্রতিটি নোড হয় বাম দিকে, বা নীচে, বা ডানদিকে পরিদর্শন করা হবে। অয়লার ট্যুর, যা বাম দিকের নোডগুলি পরিদর্শন করে, অব্যয়টিকে বাইপাস করে দেয়। যখন নীচের নোডগুলি পরিদর্শন করা হয়, তখন তারা ক্রমানুসারে অতিক্রম করে। এবং যখন ডানদিকে নোডগুলি পরিদর্শন করা হয় - পানধাপে ধাপে বাইপাস।

নেভিগেশন এবং ডিবাগিং

গাছে নেভিগেট করা সহজ করতে, এমন ফাংশন তৈরি করুন যা প্রথমে পরীক্ষা করে দেখুন তারা বাম বা ডান শিশু কিনা। একটি নোডের অবস্থান পরিবর্তন করতে, প্যারেন্ট নোডে পয়েন্টারে সহজে অ্যাক্সেস থাকতে হবে। একটি গাছ সঠিকভাবে বাস্তবায়ন করা খুবই কঠিন, তাই আপনাকে ডিবাগিং প্রক্রিয়া জানতে এবং প্রয়োগ করতে হবে। একটি বাস্তবায়ন সহ একটি বাইনারি অনুসন্ধান গাছে প্রায়শই পয়েন্টার থাকে যা আসলে ভ্রমণের দিক নির্দেশ করে না।

এই সব বের করার জন্য, একটি ফাংশন ব্যবহার করা হয় যা পরীক্ষা করে গাছটি সঠিক কিনা এবং অনেক ত্রুটি খুঁজে পেতে সাহায্য করে। উদাহরণস্বরূপ, এটি প্যারেন্ট নোড একটি চাইল্ড নোড কিনা তা পরীক্ষা করে। assert(is_wellformed(root)) দিয়ে অনেক ত্রুটি অকালে ধরা যায়। এই ফাংশনের মধ্যে কয়েকটি প্রদত্ত ব্রেকপয়েন্ট ব্যবহার করে, আপনি ঠিক কোন পয়েন্টারটি ভুল তা নির্ধারণ করতে পারেন৷

ফাংশন কনসোলেনাউসগাবে

এই ফাংশনটি পুরো ট্রিটিকে কনসোলে ফ্লাশ করে এবং তাই এটি খুবই দরকারী। যে ক্রমে ট্রি আউটপুট লক্ষ্য কার্যকর করা হয় তা হল:

1. এটি করার জন্য, আপনাকে প্রথমে নির্ধারণ করতে হবে কোন তথ্য নোডের মাধ্যমে আউটপুট হবে।
2. এবং আপনাকেও জানতে হবে গাছটি কতটা চওড়া এবং লম্বা হবে তার জন্য কতটা জায়গা ছেড়ে দিতে হবে।
3. নিম্নলিখিত ফাংশনগুলি গাছ এবং প্রতিটি সাবট্রির জন্য এই তথ্য গণনা করে। যেহেতু আপনি শুধুমাত্র লাইন দ্বারা কনসোল লাইনে লিখতে পারেন, তাই আপনাকে লাইন দ্বারা ট্রি লাইন প্রিন্ট করতে হবে।
4. এখন আমাদের প্রত্যাহার করার আরেকটি উপায় দরকারপুরো গাছ, শুধু লাইনে লাইন নয়।
5. ডাম্প ফাংশনের সাহায্যে, আপনি গাছটি পড়তে পারেন এবং আউটপুট অ্যালগরিদমকে উল্লেখযোগ্যভাবে উন্নত করতে পারেন, যতদূর গতির বিষয়ে উদ্বিগ্ন।

তবে, এই ফাংশনটি বড় গাছে ব্যবহার করা কঠিন হবে৷

কপি কনস্ট্রাক্টর এবং ডেস্ট্রাক্টর

যেহেতু একটি ট্রি একটি তুচ্ছ ডেটা স্ট্রাকচার নয়, একটি কপি কনস্ট্রাক্টর, একটি ডেস্ট্রাক্টর এবং একটি অ্যাসাইনমেন্ট অপারেটর প্রয়োগ করা ভাল৷ ধ্বংসকারী পুনরাবৃত্তিমূলকভাবে প্রয়োগ করা সহজ। খুব বড় গাছের জন্য, এটি "হিপ ওভারফ্লো" পরিচালনা করতে পারে। এই ক্ষেত্রে, এটি পুনরাবৃত্তিমূলকভাবে প্রণয়ন করা হয়। ধারণাটি হল সমস্ত পাতার ক্ষুদ্রতম মানের প্রতিনিধিত্বকারী পাতাটি সরিয়ে ফেলা, তাই এটি গাছের বাম দিকে। প্রথম পাতাগুলো কেটে ফেললে নতুন পাতা তৈরি হয় এবং গাছটি সঙ্কুচিত হয় যতক্ষণ না এটি শেষ হয়ে যায়।

কপি কনস্ট্রাক্টরটি পুনরাবৃত্তভাবে প্রয়োগ করা যেতে পারে, তবে একটি ব্যতিক্রম নিক্ষেপ করা হলে সতর্ক থাকুন। অন্যথায়, গাছটি দ্রুত বিভ্রান্তিকর এবং ত্রুটি-প্রবণ হয়ে ওঠে। এই কারণেই পুনরাবৃত্তিমূলক সংস্করণ পছন্দ করা হয়। ধারণাটি হল পুরানো গাছ এবং নতুন গাছের মধ্য দিয়ে যাওয়া, যেমন আপনি ধ্বংসকারীতে করবেন, পুরানো গাছে থাকা সমস্ত নোডগুলিকে ক্লোনিং করুন কিন্তু নতুনগুলি নয়৷

এই পদ্ধতির সাহায্যে, বাইনারি অনুসন্ধান ট্রি বাস্তবায়ন সর্বদা একটি সুস্থ অবস্থায় থাকে এবং এমনকি একটি অসম্পূর্ণ অবস্থায়ও ধ্বংসকারী দ্বারা অপসারণ করা যেতে পারে। যদি একটি ব্যতিক্রম ঘটে, তবে আপনাকে যা করতে হবে তা হল আধা-সমাপ্ত গাছটি মুছে ফেলার জন্য ধ্বংসকারীকে নির্দেশ দেওয়া। নিয়োগ অপারেটরকপি এবং অদলবদল ব্যবহার করে সহজেই প্রয়োগ করা যেতে পারে।

একটি বাইনারি অনুসন্ধান গাছ তৈরি করা

যথাযথভাবে পরিচালিত হলে সর্বোত্তম বাইনারি অনুসন্ধান গাছগুলি অবিশ্বাস্যভাবে কার্যকর। বাইনারি অনুসন্ধান গাছের জন্য কিছু নিয়ম:

1. একটি অভিভাবক নোডে সর্বাধিক 2টি চাইল্ড নোড থাকে৷
2. বাম চাইল্ড নোড সবসময় প্যারেন্ট নোড থেকে কম হয়।
3. একটি বৈধ চাইল্ড নোড সবসময় প্যারেন্ট নোডের চেয়ে বড় বা সমান হয়।

যে অ্যারেটি বাইনারি সার্চ ট্রি তৈরি করতে ব্যবহার করা হবে:

1. সাতটি মানের একটি বেস পূর্ণসংখ্যা বিন্যাস সাজানো হয়নি।
2. অ্যারের প্রথম মান হল 10, তাই ট্রি তৈরির প্রথম ধাপ হল একটি 10 রুট নোড তৈরি করা, যেমনটি এখানে দেখানো হয়েছে৷
3. রুট নোডের একটি সেট সহ, অন্যান্য সমস্ত মান এই নোডের সন্তান হবে। নিয়মগুলি উল্লেখ করে, গাছে 7 যোগ করার প্রথম পদক্ষেপটি হল রুট নোডের সাথে তুলনা করা।
4. যদি 7 মান 10 এর কম হয়, তাহলে এটি বাম চাইল্ড নোড হয়ে যাবে।
5. 7 মান 10 এর থেকে বড় বা সমান হলে, এটি ডানদিকে চলে যাবে। যেহেতু 7 10 এর কম বলে পরিচিত, এটিকে লেফট চাইল্ড নোড হিসাবে মনোনীত করা হয়েছে।
6. প্রতিটি উপাদানের জন্য পুনরাবৃত্তিমূলকভাবে তুলনা সম্পাদন করুন।
7. একই প্যাটার্ন অনুসরণ করে, অ্যারের 14তম মানের সাথে একই তুলনা করুন।
8. মূল 14 এর সাথে রুট নোড 10 এর সাথে তুলনা করা, জেনে রাখা যে 14 সঠিক চাইল্ড।
9. অ্যারের মধ্য দিয়ে হাঁটা,২০ এ আসুন।
10. 10 এর সাথে অ্যারের তুলনা করে শুরু করুন, যেটি বড়। তাই ডানদিকে যান এবং 14 এর সাথে তুলনা করুন, তার বয়স 14 এর বেশি এবং ডানদিকে কোন সন্তান নেই।
11. এখন 1 এর একটি মান রয়েছে। অন্যান্য মানের মতো একই প্যাটার্ন অনুসরণ করে, 1 থেকে 10 এর তুলনা করুন, বামে যান এবং 7 এর সাথে তুলনা করুন এবং অবশেষে 7 তম নোডের 1 বাম সন্তানের সাথে তুলনা করুন।
12. যদি মান 5 হয়, তাহলে 10 এর সাথে তুলনা করুন। যেহেতু 5 10 এর কম, তাই বাম দিকে পাস করুন এবং 7 এর সাথে তুলনা করুন।
13. জানতে যে 5 7 এর থেকে কম, গাছটি চালিয়ে যান এবং 1 মানের সাথে 5 এর তুলনা করুন।
14. যদি 1 টির কোন সন্তান না থাকে এবং 5টি 1 এর থেকে বড় হয়, তাহলে 5 হল 1টি নোডের বৈধ সন্তান৷
15. অবশেষে গাছে 8 মান ঢোকান।
16. 8 যখন 10-এর কম হয়, তখন এটিকে বাম দিকে নিয়ে যান এবং 7-এর সাথে তুলনা করুন, 8টি 7-এর থেকে বড়, তাই এটিকে ডানদিকে নিয়ে যান এবং 8-কে 7-এর উপযুক্ত সন্তান বানিয়ে গাছটি সম্পূর্ণ করুন।

সর্বোত্তম বাইনারি অনুসন্ধান গাছের সহজ মার্জিততা পাওয়া এবং মূল্যায়ন করা। প্রোগ্রামিং এর অনেক বিষয়ের মত, বাইনারি সার্চ ট্রির শক্তি আসে ছোট, সম্পর্কিত উপাদানে ডেটা সমাধান করার ক্ষমতা থেকে। এখন থেকে, আপনি একটি সংগঠিত উপায়ে সম্পূর্ণ ডেটাসেটের সাথে কাজ করতে পারবেন।

সম্ভাব্য বাইনারি অনুসন্ধান সমস্যা

বাইনারী অনুসন্ধান গাছগুলি দুর্দান্ত, তবে মনে রাখতে কয়েকটি সতর্কতা রয়েছে৷ তারা ভারসাম্য থাকলেই সাধারণত কার্যকর হয়। একটি সুষম গাছ একটি গাছ যাগাছের যেকোনো নোডের উপবৃক্ষের উচ্চতার মধ্যে পার্থক্য সর্বাধিক এক। আসুন একটি উদাহরণ দেখি যা নিয়মগুলি স্পষ্ট করতে সাহায্য করতে পারে। আসুন কল্পনা করি যে অ্যারেটি সাজানোর যোগ্য হিসাবে শুরু হয়৷

যদি আপনি এই ট্রিতে একটি বাইনারি সার্চ ট্রি অ্যালগরিদম চালানোর চেষ্টা করেন, এটি ঠিক এমনভাবে কাজ করবে যেন এটি কাঙ্খিত মান না পাওয়া পর্যন্ত অ্যারের মাধ্যমে পুনরাবৃত্তি করছে। বাইনারি অনুসন্ধানের শক্তি অবাঞ্ছিত মানগুলিকে দ্রুত ফিল্টার করার ক্ষমতার মধ্যে রয়েছে। যখন একটি গাছ সুষম নয়, তখন এটি একটি সুষম গাছের মতো একই সুবিধা প্রদান করবে না।

বাইনারি সার্চ ট্রি তৈরি করার সময় ব্যবহারকারী যে ডেটা নিয়ে কাজ করছেন তা পরীক্ষা করা খুবই গুরুত্বপূর্ণ। পূর্ণসংখ্যার জন্য একটি বাইনারি সার্চ ট্রি প্রয়োগ করার আগে আপনি অ্যারে র্যান্ডমাইজেশনের মতো রুটিনগুলিকে একীভূত করতে পারেন।

বাইনারী অনুসন্ধান গণনার উদাহরণ

নিম্নলিখিত বাইনারি সার্চ ট্রিতে 25 ঢোকানো হলে কি ধরনের গাছের ফল হবে তা আমাদের নির্ধারণ করতে হবে:

10

/

/

5 15

/ /

/ /

2 12 20

এখনও x ধারণ করে না এমন একটি গাছ T-এ x ঢোকানোর সময়, x কী সবসময় একটি নতুন পাতায় রাখা হয়। এর সাথে, নতুন গাছটি দেখতে এরকম হবে:

10

/

/

5 15

/ /

/ /

2 12 20

25

আপনি যদি নিচের বাইনারি সার্চ ট্রিতে ৭টি ঢোকান তাহলে আপনি কী ধরনের গাছ পাবেন?

10

/

/

5 15

/ /

/ /

2 12 20

উত্তর:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

একটি বাইনারি সার্চ ট্রি যেকোনো বস্তু সংরক্ষণ করতে ব্যবহার করা যেতে পারে। লিঙ্ক করা তালিকার পরিবর্তে একটি বাইনারি সার্চ ট্রি ব্যবহার করার সুবিধা হল যে গাছটি যুক্তিসঙ্গতভাবে ভারসাম্যপূর্ণ এবং একটি "রৈখিক" একের চেয়ে "পূর্ণ" গাছের মতো হলে, সন্নিবেশ, অনুসন্ধান এবং সমস্ত মুছে ফেলার ক্রিয়াকলাপগুলি চালানোর জন্য প্রয়োগ করা যেতে পারে। O(log N) সময়।