২২-২ঃ Complete Binary Tree এর Array Representation

এই মডিউলে আমরা দেখবো , কীভাবে একটি Complete Binary Tree কে Array তে Represent করা যায় যার সাহায্যে আমরা একটি Complete Binary Tree তে represent করে ঐ Tree এর যাবতীয় কাজ Array এর মাধ্যমে করতে পারি।

প্রথমত , আমরা এইক্ষেত্রে আগে দেখি , একটা Tree কে hypothetically Array এর সাথে কম্পেয়ার করা যায় কিনা। এরজন্য আমরা একটি Tree নিয়ে সেটিকে Level Order এর মাধ্যমে নাম্বারিং করবো ।

এখানে Level Order এ নাম্বারিং বলতে বুঝানো হয়েছে , Level Order এ প্রিন্ট করার সময় যে সিরিয়ালে আসে , সে সিরিয়ালে নাম্বার গুলো দেয়া হয়েছে । ।।

আমরা একটি Array নিয়ে নিতে পারি । যেহেতু Tree এ Node সংখ্যা ৭ , তাই ৭ সাইজের একটি Array নিবো । নাম্বার অনুসারে যে Node এর নাম্বার যা , Array এর ঐ নাম্বার Index এ সেই Node এর ভ্যালুটি রাখা হবে। নিচে সেই Array টি দেয়া হলো

Array বিল্ড করার পর এখন আমাদের কাজ হলো , কীভাবে এই array টি একটি Complete Binary Tree হিসেবে কাজ করবে তা বুঝতে পারা।

-> একটি Node এর Left child এবং Right Child যদি থাকে তবে তা আমরা কীভাবে বের করতে পারবো ।

• কোনো একটি Node এর Left child পেতে হলে আমাদের একটি সিম্পল সুত্রের সাহায্য নিতে হবে । তা হলো = ( Array তে Node এর Index) *2 +1 . এর সাহায্যে আমরা ঐ Node এর left child পাবো । যেমনঃ B নোড টি আছে , Array এর 1 নাম্বার ইন্ডেক্সে , এখন (1*2)+1 = 3. Array এর 3 নাম্বার ইন্ডেক্স এ আছে D. চিত্র দেখলে আমরা দেখতে পাবো , B এর left child হলো D.

• কোনো একটি Node এর Right child পেতে হলে আগের সুত্রটি মডিফাই করে সাহায্য নিতে হবে । তা হলো = ( Array তে Node এর Index) *2 +2 . এর সাহায্যে আমরা ঐ Node এর right child পাবো । যেমনঃ B নোড টি আছে , Array এর 1 নাম্বার ইন্ডেক্সে , এখন (1*2)+2 = 4. Array এর 4 নাম্বার ইন্ডেক্স এ আছে E. চিত্র দেখলে আমরা দেখতে পাবো , B এর left child হলো E.

• যদি উক্ত Index নাম্বার টি ঐ Array এর মধ্যে উপস্থিত না থাকে তবে সেক্ষেত্রে বুঝে নিতে হবে , ঐ Node এর উক্ত child ( Left/ Right) নেই . যেমনঃ E নোডটি আছে 4 নাম্বার Index এ । আমরা যদি এর left child বের করতে চাই তবে তার left child টি থাকবে (4*2)+1 = 9 নাম্বার ইন্ডেক্সে। যেহেতু উক্ত Array টির 9 নাম্বার ইনডেক্স নেই , তার মানে হলো , E এর কোনো Left child নেই

আমরা আরেকটি কাজ করতে পারবো এই Complete Binary Tree এর Array এর মাধ্যমে, আর তা হলো কোনো একটি Node এর Parent বের করে আনতে পারবো ।

এর জন্য আমাদের একটি সিম্পল সুত্র জানতে হবে । তা হলো , Parent = ( Node index in array -1) /2 .

• একটি জোড় ইনডেক্স নেয়া যাক। G নোড এর Index হলো 6 , সুতারাং G Node এর Parent = (6-1)/2 = 5/2 = 2 . 2 নাম্বার ইন্ডেক্সে C নোড আছে যা G নোড এর Parent

• এবার একটি বিজোড় ইনডেক্স নেয়া যাক। D নোড এর Index হলো 3 , সুতারাং D Node এর Parent = (3-1)/2 =2/2 = 1 . 1 নাম্বার ইন্ডেক্সে B নোড আছে যা D নোড এর Parent

• খেয়াল রাখতে হবে 0 নাম্বার ইন্ডেক্সে যে আছে , তা হলো Root সুতারাং এর কোনো Parent থাকবে না।