বাইনারি সার্চ ট্রি পর্ব - ২

27,Jan2017

আগের পর্বে আমরা বাইনারি সার্চ ট্রি এর বেসিক জেনেছি এবং এই পর্বে আমরা বাইনারি সার্চ ট্রি এর মূল অপারেশন গুলো ইমপ্লিমেন্ট করার চেষ্টা করবো ।

প্রথমে আমরা একটি স্ট্রাকচার বানাবো যার মধ্যে একটি ইন্টিজার Value এবং দুটি স্ট্রাকচার টাইপের পয়েন্টার থাকবে । একটি Left পয়েন্টার যার মধ্যে Left Child নোডকে পয়েন্ট করার Address থাকবে এবং আরেকটি Right পয়েন্টার যার মধ্যে Right Child নোডকে পয়েন্ট করার Address থাকবে ।



BstNode* newNode দিয়ে আমরা memory তে নতুন একটি memory নিচ্ছি newNode নামে । যেহেতু এটি BstNode টাইপের স্ট্রাকচার তাই এতে তিনটি Information থাকবে । newNode এর value তে আমরা Add কৃত ডাটা রাখবো এবং left পয়েন্টারে ডাটার Left Child এর Address এবং right পয়েন্টারে Right Child এর Address রাখবো । প্রাথমিক অবস্থায় ডাটার Left এবং Right Child নেই বিধায় এই পয়েন্টার দুটি কাউকে পয়েন্ট করবে না , তাই এরা NULL ।

বাইনারি সার্চ ট্রি তে Element Add করা ঃ

প্রাথমিক অবস্থায় যখন Binary Search Tree (BST) তে কোন ডাটা (নোড) নেই তখন আমরা root কে NULL ধরে কাজ করবো । একটি নোড Add হওয়া মাত্রই একে root ধরে কাজ করবো । তারপর নতুন নোড আসলে রিকার্সিভ্লি আমরা ট্রি check করে BST তে value Add করবো ।


যেমন ঃ

    উপরের ট্রি তে আমরা 7 কে Add করতে চাই । এখানে আমাদের current root হল 8 ।  7 , 8 থেকে ছোট । এখানে current node হল 8 । তাহলে এর left child থাকলে আমরা left এ search দেবো । না থাকলে current node এর left child হিসেবে 7 কে Add করে দেবো । অর্থাৎ নতুন node এর Address থাকবে Node 8  এর left পয়েন্টারে ।
আর নতুন নোডের value যদি current নোডের value থেকে বড় হয় তাহলে current নোডের যদি right child থাকে তবে right এ search দেবো । right child না থাকলে current node এর right child হিসেবে নতুন নোডটিকে Add করে দেবো ।
7 যেহেতু 8 থেকে ছোট তাই 8 এর left sub-tree তে search দেবো । left এ আমরা 3 কে পেয়েছি । 7 , 3 থেকে বড় । তাই 3 এর right sub-tree তে search দেবো । right এ আমরা 5 কে পেয়েছি এবং 7 , 5 এর থেকে বড় ও 5 এর কোন right child নেই । তাই 7 কে আমরা 5 এর right child হিসেবে Add করে দেবো ।

ট্রি তে 7 Add হবার পর ট্রি টি এরকম হবে




বাইনারি সার্চ ট্রি তে কোন Element খোঁজা ঃ

বাইনারি সার্চ ট্রি তে কোন Element খোঁজা বাইনারি সার্চ ট্রি তে Element Add করার মতই ।




বাইনারি সার্চ ট্রি থেকে Element Delete করা ঃ

Value Delete এর ক্ষেত্রে Value টি যদি leaf হয় অর্থাৎ এর কোন child না থাকে তাহলে সরাসরি একে Delete করে দেবো । যদি এমন হয় , যাকে Delete করবো তার একটি child আছে ( left or right ) তাহলে Delete কৃত value কে যে পয়েন্ট করছে সেই value-র left (child left এ হলে ) অথবা right (child right এ হলে ) পয়েন্টার Delete কৃত value-র child কে পয়েন্ট করবে ।

উপরের ট্রি তে Leaf নোড হল 1 , 4 ও 11 কারণ এদের কোন চাইল্ড নেই । এদের কাউকে ডিলিট করতে চাইলে সরাসরি ডিলিট করে দিলেই হবে । 9 কে ডিলিট করতে চাইলে উপরের ছবির মত ডিলিট করতে হবে কারণ 9 এর একটি চাইল্ড আছে

যদি value টির দুটি child থাকে তাহলে এর left sub-tree এর সবচেয়ে বড় value টি , যে value টি Delete করবো তার জায়গায় বসিয়ে বড় value টি Delete করে দেবো । অথবা value টির right sub-tree এর সবচেয়ে ছোট value কে নিয়েও আমরা একই কাজটি করতে পারি । তাহলেই আমাদের BST Property ঠিক থাকবে ।

যদি আমরা 8 কে ডিলিট করতে চাই তাহলে এই পজিশনে এমন একটি নোড আনবো যেন BST Property ঠিক থাকে

8 কে ডিলিট করার পর ট্রি টি এমন হবে 




বাইনারি সার্চ ট্রি তে ট্রাভার্স ঃ




Pre-Order ট্রাভার্সালঃ

এই অর্ডারে BST তে ট্রাভার্সের প্রপার্টি হল --> ( Root , Left , Right )

উপরের ট্রি তে যদি আমরা এই অর্ডারে ট্রাভার্স করি তাহলে ট্রাভার্সাল সিকুয়েন্সটি এরকম হবে ঃ
8 , 3 , 1 , 5 , 4 , 9 , 12 , 11

ব্যাখ্যা ঃ
Root ( 8 ) থেকে আমরা ট্রাভার্স শুরু করবো । প্রথমে আমরা 8 কে পেয়েছি । তারপর left এ গিয়ে 3 কে পেয়েছি যা নিজেও একটি Root । তাই 8 এর পর 3 । আবার 3 যেহেতু Root তাই এর left এ যাবো । এর left এ 1 । 1 নিজেও একটি Root । তাই 8 , 3 এর পর 1 । এবার 3 এর right এ যাবো । right এ 5 কে পেয়েছি যা নিজেও একটি Root । তাই 8 , 3 , 1 এর পর 5 । এবার 5 এর left এ যাবো । এভাবে আমরা রিকার্সিভ্লি ( কোডে ) ট্রাভার্স করবো । অর্থাৎ Pre-Order ট্রাভার্সালে সবার প্রথমে প্রায়োরিটি পাবে Root , তারপর Left Child এবং সবশেষে Right Child । প্রতিটি নোডের জন্যই এই নিয়মটি প্রযোজ্য ।


In-Order ট্রাভার্সালঃ

এই অর্ডারে BST তে ট্রাভার্সের প্রপার্টি হল --> (  Left , Root , Right )

উপরের ট্রি তে যদি আমরা এই অর্ডারে ট্রাভার্স করি তাহলে ট্রাভার্সাল সিকুয়েন্সটি এরকম হবে ঃ
1 , 3 , 4 , 5 , 8 , 9 , 11 , 12


Post-Order ট্রাভার্সালঃ

এই অর্ডারে BST তে ট্রাভার্সের প্রপার্টি হল --> ( Left , Right , Root )

উপরের ট্রি তে যদি আমরা এই অর্ডারে ট্রাভার্স করি তাহলে ট্রাভার্সাল সিকুয়েন্সটি এরকম হবে ঃ
1 , 4 , 5 , 3 , 11 , 12 , 9 , 8

সম্পূর্ণ কোড ইমপ্লিমেন্টেশন ঃ



কোড কমপ্লেক্সিটি ঃ
  • ইনসার্ট ঃ O( log n ) In Average Case , O( n ) In Worst Case
  • সার্চ ঃ O( log n ) In Average Case , O( n ) In Worst Case
  • ডিলিট ঃ O( log n ) In Average Case , O( n ) In Worst Case
সমাধানের জন্য সমস্যা ঃ
রেফারেন্স ঃ
Happy Coding

0 comments: (+add yours?)