বি-ট্রি এবং বাইনারি গাছের মধ্যে পার্থক্য
কন্টেন্ট
বি-ট্রি এবং বাইনারি ট্রি নন-লিনিয়ার ডেটা স্ট্রাকচারের ধরণ। যদিও পদগুলি সমান বলে মনে হচ্ছে তবে সমস্ত দিক থেকে এটি আলাদা। রেকের অ্যাক্সেসের গতি ডিস্কের চেয়ে অনেক বেশি হওয়ায় ডিস্কের পরিবর্তে রেকর্ড বা ডেটা র্যামে সংরক্ষণ করা হয় বাইনারি ট্রি ব্যবহার করা হয়। অন্যদিকে, বি-ট্রি ব্যবহার করা হয় যখন ডেটা ডিস্কে সংরক্ষণ করা হয় এটি গাছের উচ্চতা হ্রাস করে এবং নোডে শাখা বাড়িয়ে অ্যাক্সেসের সময়কে হ্রাস করে।
বি-ট্রি এবং বাইনারি গাছের মধ্যে আরেকটি পার্থক্য হ'ল বি-গাছের অবশ্যই তার সমস্ত সন্তানের নোড একই স্তরে থাকতে হবে যেখানে বাইনারি গাছের তেমন সীমাবদ্ধতা নেই। একটি বাইনারি গাছে সর্বাধিক ২ টি সাবট্রি বা নোড থাকতে পারে তবে বি-ট্রিতে এম সাবট্রি বা নোডের এম নম্বর থাকতে পারে যেখানে এম বি-গাছের ক্রম হয়।
- তুলনা রেখাচিত্র
- সংজ্ঞা
- মূল পার্থক্য
- উপসংহার
তুলনা রেখাচিত্র
| তুলনার জন্য ভিত্তি | বি-গাছ | বাইনারি ট্রি |
|---|---|---|
| অপরিহার্য সীমাবদ্ধতা | একটি নোডে সর্বোচ্চ এম সংখ্যক শিশু নোড থাকতে পারে (যেখানে এম গাছের ক্রম)। | একটি নোডে সাবট্রির সর্বোচ্চ 2 নম্বর থাকতে পারে। |
| ব্যবহৃত | এটি যখন ডিস্কে ডেটা সংরক্ষণ করা হয় তখন ব্যবহৃত হয়। | রেকর্ড এবং ডেটা র্যামে সংরক্ষণ করা হয় তখন এটি ব্যবহৃত হয়। |
| গাছের উচ্চতা | লগএম এন (যেখানে এম এম-ওয়ে গাছের ক্রম) | লগ2 এন |
| আবেদন | অনেক ডিবিএমএসে কোড ইনডেক্সিং ডেটা স্ট্রাকচার। | কোড অপ্টিমাইজেশন, হাফম্যান কোডিং ইত্যাদি |
বি-ট্রি সংজ্ঞা
একটি বি-গাছ হ'ল ভারসাম্যযুক্ত এম-ওয়ে গাছ এবং এটি ভারসাম্যপূর্ণ সাজান গাছ হিসাবেও পরিচিত। এটি বাইনারি অনুসন্ধান গাছের মতো যেখানে নোডগুলি ইনর্ডার ট্র্যাভারসালের ভিত্তিতে সংগঠিত হয়। বি-গাছের স্পেস জটিলতা হ'ল ও (এন)। সন্নিবেশ এবং মুছে ফেলার সময় জটিলতা হ'ল ও (লগ এন)।
কিছু শর্ত রয়েছে যা একটি বি-গাছের জন্য সত্য হতে হবে:
- গাছের উচ্চতা যতটা সম্ভব ন্যূনতম থাকতে হবে।
- গাছের পাতার উপরে, কোনও খালি সাবট্রিজ থাকা উচিত নয়।
- গাছের পাতাগুলি একই স্তরে আসতে হবে।
- সমস্ত নোডের ছুটির নোড বাদে কমপক্ষে বাচ্চাদের সংখ্যা থাকতে হবে।
বি-ট্রি অর্ডার বৈশিষ্ট্য এম
- প্রতিটি নোডে সর্বাধিক এম সংখ্যক শিশু এবং সর্বনিম্ন এম / 2 বাচ্চাদের সংখ্যা বা 2 থেকে সর্বোচ্চ পর্যন্ত কোনও সংখ্যা থাকতে পারে।
- প্রতিটি নোডের সর্বাধিক এম -1 কী বাচ্চাদের চেয়ে কম থাকে।
- কীগুলির বিন্যাসটি নোডগুলির মধ্যে কিছু নির্দিষ্ট ক্রমে। কীটির বামে উপস্থিত সাবট্রির সমস্ত কীগুলি কীটির পূর্বসূরীরা এবং কীটির ডানদিকে উপস্থিত উপস্থিতিকে উত্তরসূরি বলা হয়।
- একটি পূর্ণ নোড inোকানোর সময়, গাছটি দুটি ভাগে বিভক্ত হয়, এবং মধ্যমানের মান সহ কীটি প্যারেন্ট নোডে .োকানো হয়।
- নোডগুলি মোছার পরে মার্জিং অপারেশন হয়।
বাইনারি ট্রি সংজ্ঞা
বাইনারি ট্রি একটি গাছের কাঠামো যা এর শিশু নোডের জন্য সর্বাধিক দুটি পয়েন্টার থাকতে পারে। এর অর্থ হ'ল নোডের সর্বোচ্চ ডিগ্রি 2 এবং সেখানে শূন্য বা এক-ডিগ্রি নোডও থাকতে পারে।
বাইনারি গাছের কিছু নির্দিষ্ট রূপ রয়েছে যেমন কঠোরভাবে বাইনারি ট্রি, সম্পূর্ণ বাইনারি ট্রি, প্রসারিত বাইনারি ট্রি ইত্যাদি
- কঠোরভাবে বাইনারি ট্রি এমন একটি গাছ যেখানে প্রতিটি নন-টার্মিনাল নোড অবশ্যই বাম সাবট্রি এবং ডান সাবট্রি থাকতে হবে।
- একটি গাছকে সম্পূর্ণ বাইনারি গাছ বলা হয় যখন এটি 2 থাকার শর্তটি পূরণ করে আমি প্রতিটি স্তরের নোড যেখানে আমি স্তর।
- থ্রেডেড বাইনারি হ'ল একটি বাইনারি ট্রি যা 0 টি নোড বা 2 নোডের সমন্বয়ে গঠিত।
ট্র্যাভারসাল কৌশল
বৃক্ষ ট্র্যাভারসাল হ'ল ট্রি ডেটা কাঠামোর উপর সঞ্চালিত সবচেয়ে ঘন ঘন অপারেশন যা প্রতিটি নোড নিয়মিত পদ্ধতিতে একবারে পরিদর্শন করেছিল।
- আন্ডারর্ডার- এই গাছের আবর্তনে বাম সাবট্রিটি পুনরাবৃত্তভাবে পরিদর্শন করা হয় তারপরে রুট নোডটি পরিদর্শন করা হয় এবং শেষের ডানদিকে সাবট্রি পরিদর্শন করা হয়।
- প্রাক-পূর্ববর্তী- এই গাছের আবর্তনে মূল নোডটি প্রথমে তারপরে বাম সাবট্রিতে এবং শেষের দিকে ডান উপশ্রে পরিদর্শন করা হয়।
- পোস্টর্ডার- এই কৌশলটি বাম সাবট্রি এবং তারপরে ডান সাবট্রি এবং শেষের মূল নোডে পরিদর্শন করে।
- বি-ট্রিতে, নন-টার্মিনাল নোডে সর্বাধিক সংখ্যক শিশু নোড থাকতে পারে এম যেখানে বি-গাছের ক্রম হয়। অন্যদিকে, একটি বাইনারি গাছে সর্বাধিক দুটি সাবট্রি বা শিশু নোড থাকতে পারে।
- ডেটা ডিস্কে সঞ্চিত থাকাকালীন বি-ট্রি ব্যবহার করা হয় যখন বাইনারি ট্রি ব্যবহার করা হয় যখন র্যামের মতো দ্রুত মেমরিতে ডেটা সংরক্ষণ করা হয়।
- বি-গাছের জন্য আবেদনের আরেকটি ক্ষেত্র হ'ল ডিবিএমএসে কোড ইনডেক্সিং ডেটা স্ট্রাকচার, বিপরীতে, বাইনারি ট্রি কোড অপ্টিমাইজেশন, হাফম্যান কোডিং ইত্যাদিতে নিযুক্ত হয় is
- একটি বি-গাছের সর্বোচ্চ উচ্চতা লগএমএন (এম গাছের ক্রম)। বিপরীতে, বাইনারি গাছ সর্বাধিক উচ্চতা লগ2এন (এন নোডের সংখ্যা এবং বেস 2 কারণ এটি বাইনারি হয়)।
উপসংহার
বি-ট্রিটি বাইনারি এবং বাইনারি অনুসন্ধান বৃক্ষের উপরে ব্যবহৃত হয় এর পিছনে মূল কারণ মেমরির হায়ারার্কি যেখানে সিপিইউ উচ্চ ব্যান্ডউইথ চ্যানেলগুলির সাথে ক্যাশে সংযুক্ত থাকে এবং সিপিইউ লো ব্যান্ডউইথ চ্যানেলের মাধ্যমে ডিস্কের সাথে সংযুক্ত থাকে। রেকর্ডগুলি র্যামে সংরক্ষণ করা হয় (ছোট এবং দ্রুত) এবং বি-ট্রি ব্যবহার করা হয় যখন রেকর্ডগুলি ডিস্কে সংরক্ষণ করা হয় (বড় এবং ধীর) A সুতরাং, বাইনারি গাছের পরিবর্তে বি-গাছের ব্যবহার উচ্চ শাখার কারণ এবং গাছের উচ্চতা হ্রাস করার কারণে অ্যাক্সেসের সময়কে উল্লেখযোগ্যভাবে হ্রাস করে।
