গাছ, লাল-কালো গাছ

"হাই, অ্যামিগো!"

"হ্যালো, ঋষি!"

"আমি সেখানে আমার পুরানো নোট পেয়েছি এবং আপনার জন্য কিছু আকর্ষণীয় উপাদান প্রস্তুত করেছি। আমি মনে করি আপনি এটি শুনতে আগ্রহী হবেন।"

"চলুন শুনুন। আপনি সবসময় কিছু আকর্ষণীয় খুঁজে পান যা পরে খুব দরকারী বলে প্রমাণিত হয়।"

"ঠিক আছে। আজ আমি তোমাকে গাছ সম্পর্কে বলতে চাই , তাই আমি গ্রাফ দিয়ে শুরু করব ।"

" গ্রাফ হল বিন্দু এবং রেখাগুলির একটি সিস্টেম যা তাদের সংযুক্ত করে৷ বিন্দুগুলিকে গ্রাফের শীর্ষবিন্দু বলা হয় এবং রেখাগুলিকে গ্রাফের প্রান্ত বলা হয়৷ উদাহরণস্বরূপ:"

"একটি গ্রাফ বিভিন্ন বাস্তব-বিশ্বের প্রক্রিয়া এবং কাজের জন্য একটি গাণিতিক মডেল হিসাবে ব্যবহার করা খুব সুবিধাজনক। গ্রাফের জন্য অনেকগুলি বিভিন্ন কাজ এবং অ্যালগরিদম উদ্ভাবিত হয়েছে, তাই সেগুলি প্রায়শই ব্যবহার করা হয়।"

"উদাহরণস্বরূপ, ধরুন শীর্ষগুলি হল শহর, এবং প্রান্তগুলি হল রাস্তা৷ তারপর শহরের মধ্যে সবচেয়ে ছোট রাস্তাটি অনুসন্ধান করা হয়ে যায়: «একটি গ্রাফ দেওয়া হয়েছে, দুটি শীর্ষবিন্দুর মধ্যে সংক্ষিপ্ততম পথটি সন্ধান করুন»৷ "

"কিন্তু A থেকে B পর্যন্ত পথটি সবসময় B থেকে A যাওয়ার পথের মতো নয়। তাই, কখনও কখনও দুটি ভিন্ন লাইন থাকা পছন্দনীয়। এটি করার জন্য, লাইনগুলি (গ্রাফের প্রান্তগুলি) তীর দিয়ে প্রতিস্থাপিত হয়। অন্য কথায়, গ্রাফটিতে দুটি তীর থাকতে পারে: একটি A থেকে B, এবং আরেকটি B থেকে A।"

"যদি গ্রাফটি তীর ব্যবহার করে, তবে এটিকে একটি নির্দেশিত গ্রাফ বলা হয় ; যদি এটিতে শুধু লাইন থাকে তবে এটিকে একটি অনির্দেশিত গ্রাফ বলা হয় ।"

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

"যদি আপনি একটি গ্রাফের প্রতিটি শীর্ষবিন্দুতে পৌঁছানোর জন্য প্রান্তগুলি ব্যবহার করতে পারেন, তবে এটিকে একটি সংযুক্ত গ্রাফ বলা হয়। একটি গ্রাফ যেখানে তিনটি পৃথক শীর্ষবিন্দু রয়েছে এবং কোন প্রান্ত নেই সেটি এখনও একটি গ্রাফ, কিন্তু আমরা এটিকে একটি সংযোগ বিচ্ছিন্ন গ্রাফ বলি।"

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

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

"যদি গাছের প্রতিটি উপাদানের দুটি সন্তান থাকে, তবে একে বাইনারি গাছ বলা হয় । অন্য কথায়, 0 বা 2টি শাখা থাকতে পারে। আপনি উপরের ডানদিকে একটি বাইনারি গাছ দেখতে পাবেন ।"

" একটি গাছকে একটি সম্পূর্ণ বাইনারি গাছ বলা হয় যখন প্রতিটি শাখায় 2টি সন্তান থাকে এবং সমস্ত পাতা (শিশুবিহীন শীর্ষবিন্দু) একই সারিতে থাকে।"

"উদাহরণ স্বরূপ:"

"কেন এই গাছের প্রয়োজন?"

"ওহ, গাছগুলি অনেক জায়গায় ব্যবহার করা হয়৷ সাধারণভাবে, বাইনারি গাছগুলিকে সাজানো হয় স্ট্রাকচার্ড ডেটা৷"

"ওটা কী?"

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

"আপনি কি এর মানে কি স্পষ্ট করতে পারেন?"

"বৃক্ষের উপাদানগুলি সাধারণত যোগ করে সাজানো হয়৷ ধরুন আমাদের 7টি উপাদান আছে: 13, 5, 4, 16, 8, 11, 10"

"এখানে কীভাবে উপাদানগুলি গাছে যুক্ত করা হয়।"

"যদি আমরা এই গাছের মধ্যে 7 নম্বরটি খুঁজছি, তাহলে অনুসন্ধানটি এভাবেই চলবে"

"0) মূল থেকে শুরু করুন।"

"1a) 7 কি 13 এর সমান? না"

"1b) 7 কি 13 এর থেকে বড়? না, তাই আমরা বাম সাবট্রিতে চলে যাই।"

"2a) 7 কি 5 এর সমান? না।"

"2b) 7 কি 5 থেকে বড়? হ্যাঁ, তাই আমরা ডান সাবট্রিতে চলে যাই।"

"3a) 7 কি 8 এর সমান? না"

"3b) 7 কি 8 থেকে বড়? না, তাই আমরা বাম সাবট্রিতে চলে যাই।"

"4a) কোন বাম সাবট্রি নেই, যার মানে হল 7 নম্বর গাছে নেই।"

"আহ। অন্য কথায়, আমাদের শুধুমাত্র রুট থেকে কাঙ্খিত সংখ্যার অবস্থানে যাওয়ার পথে শীর্ষবিন্দুগুলি পরীক্ষা করতে হবে। হ্যাঁ, এটি সত্যিই দ্রুত।"

"আরও কি, যদি গাছটি ভারসাম্যপূর্ণ হয়, তবে আপনাকে এক মিলিয়ন উপাদান অনুসন্ধান করতে প্রায় 20টি শীর্ষবিন্দু দিয়ে যেতে হবে।"

"আমি একমত - এটি খুব বেশি নয়।"

"সুষম গাছ বলতে কি বোঝ?"

"একটি গাছ যা বিকৃত নয়, অর্থাৎ যার দীর্ঘ শাখা নেই৷ উদাহরণস্বরূপ, যদি আমরা গাছটি তৈরি করার সময় উপাদানগুলি আগে থেকেই সাজানো থাকে, তবে আমরা একটি শাখা নিয়ে একটি খুব দীর্ঘ গাছ তৈরি করতাম। "

"হুম। তুমি ঠিক বলেছ। তাহলে আমরা কি করব?"

"যেমন আপনি সম্ভবত ইতিমধ্যে অনুমান করেছেন, সবচেয়ে দক্ষ গাছের শাখা রয়েছে যা প্রায় একই দৈর্ঘ্যের। তারপর প্রতিটি তুলনা অবশিষ্ট সাবট্রির বৃহত্তম অংশকে বাতিল করে দেয়।"

"তাহলে, আমাদের গাছটি পুনর্নির্মাণ করা দরকার?"

"হ্যাঁ। এটিকে «ভারসাম্যপূর্ণ» হতে হবে — যতটা সম্ভব একটি সম্পূর্ণ বাইনারি গাছের কাছাকাছি করা হবে।"

"এই সমস্যাটি সমাধান করার জন্য, স্ব-ভারসাম্য রক্ষাকারী গাছের উদ্ভাবন করা হয়েছিল।  যদি একটি উপাদান যোগ করার পরে গাছটি বিকৃত হয়ে যায়, তাহলে এটি উপাদানগুলিকে সামান্য পুনর্বিন্যাস করে যাতে সবকিছু ঠিক থাকে।  এখানে ভারসাম্য রক্ষার একটি উদাহরণ দেওয়া হল:"

"এর মধ্যে কিছু গাছ লাল -কালো গাছ নামে পরিচিত ।"

"কেন তাদের লাল-কালো বলা হয়?"

"তাদের উদ্ভাবক দুটি রঙ ব্যবহার করে সমস্ত শীর্ষবিন্দু আঁকেন। একটি রঙ ছিল লাল, এবং অন্যটি কালো। বিভিন্ন শীর্ষবিন্দু বিভিন্ন নিয়ম মেনে চলে। এটি ভারসাম্য প্রক্রিয়ার সম্পূর্ণ ভিত্তি তৈরি করে।"

"উদাহরণ স্বরূপ:"

"তাহলে এই নিয়মগুলি কি?"

"1) একটি লাল শীর্ষবিন্দু একটি লাল শীর্ষবিন্দুর সন্তান হতে পারে না।"

"2) প্রতিটি পাতার কালো গভীরতা একই (কালো গভীরতা মূল থেকে পথের কালো শীর্ষবিন্দুর সংখ্যাকে বোঝায়)।"

"৩) গাছের গোড়া কালো।"

"এটি কীভাবে কাজ করে তা আমি ব্যাখ্যা করব না - আপনার মাথা সম্ভবত ইতিমধ্যেই বিস্ফোরিত হয়েছে।"

"হ্যাঁ। আমার প্রসেসর একটু ধোঁয়া দিচ্ছে।"

"এখানে আপনার জন্য একটি লিঙ্ক। আপনি যদি চান, আপনি এখানে এটি সম্পর্কে আরও পড়তে পারেন।"

অতিরিক্ত উপাদান লিঙ্ক

"এবং এখন, একটু বিরতি নিন।"