আমরা স্ট্যাটিক ডেটা স্ট্রাকচার লিস্ট, স্ট্যাক, কিউ ইত্যাদি দেখেছি। দেখেছি ডাইনামিক ডেটা স্ট্রাকচার যেমন লিঙ্কড লিস্ট। যা থেকে সহজেই ডাইন্যামিক্যালি কোন আইটেম এড বা রিমুভ করা যায়। এগুলো দিয়ে অনেক ধরনের সমস্যা সমাধান করা যায়। তবে এগুলোর একটা সমস্যা হচ্ছে এই ডেটা স্ট্রাকচার গুলো হচ্ছে সিকোয়েনশিয়াল ডেটা স্ট্র্যাকচার। মানে ডেটা গুলো সিরিয়ালি স্টোর করে রাখে। যেখানে কোন একটা আইটেম খুঁজে বের করতে O(n) ইন্সট্রাকশন লাগবে। তো বুঝা যাচ্ছে আমাদের আরো বেটার ডেটা স্ট্রাকচার লাগবে, যেখানে ডেটা রাখলে আরো ইফেশিয়েন্টলি ডেটা খুঁজে বের করা যাবে। তেমনি একটা ডেটা স্ট্রাকচার হচ্ছে ট্রি।
ট্রি ডেটা স্ট্রাকচার
ট্রি হচ্ছে নন লিনিয়ার ডেটা স্ট্র্যাকচার। যা মূলত নডের সমষ্টি। লিঙ্কড লিস্ট শেখার সময় আমরা নডের সাথে পরিচিত হয়েছি। ট্রি তে নড গুলো একটা আরেকটার সাথে edge দিয়ে কানেক্টেড থাকে। ট্রিতে একের অধিক নড থাকতে পারে। প্রথম বা ইনিশাল নডকে রুট / root বলা হয়।রুট নডের সাথে একের অধিক নড কানেক্টেড থাকতে পারে। যাকে বলা হয় সাব-ট্রি। নিচের ছবিটি দেখিঃ
এখানে ট্রি এর একটা উদাহরণ দেখছি আমরা। যেখানে A হচ্ছে রুট নড।
ট্রি এর টারমিনলজিঃ
নডঃ একটা ভ্যালু এবং একটা পয়েন্টারের সমষ্টি। যেখানে পয়েন্টার হিসেবে এর চাইল্ড নডের লোকেশন স্টোর করে রাখা হয়। উপরের ছবির ট্রি তে A,B,C,D… এগুলো প্রতিটা এক একটা নড। A নডের চাইল্ড নড হচ্ছে BCD। তো তাই এই নডের দুইটা প্রধান অংশ হচ্ছে নড ভ্যালু, মানে A। এবং BCD, এই তিনটে নডের লোকেশন পয়েন্টার।
রুটঃ ট্রি এর সবচেয়ে উপরের নোড। প্রথম নড বা ইনিশিয়াল নড ও বলা যায়। ট্রি ডেটা স্ট্রাকচারে একটাই রুট নড থাকে। উপরের ছবির ট্রি তে A হচ্ছে রুট নড।
Edge: দুইটা নডের মধ্যকার লিঙ্ক। এই লিঙ্ক ডিরেকটেড থাকতে পারে, আন-ডিরেকটেড থাকতে পারে। ট্রি ডেটা স্ট্রাকচারে যদি N সংখ্যক নড থাকে, তাহলে ঐ ট্রি তে মোট Edge সংখ্যা হচ্ছে N-1টি। উপরের ছবির নড গুলো যে লাইন দিয়ে কানেক্টেড, ঐ লাইনটাই হচ্ছে এজ। আমাদের ছবির ট্রি এর এজ গুলো হছে ডিরেক্টেড এজ।
Parent: কোন নডের পূর্বসূরী নড হচ্ছে প্যারেন্ট নড। উপরের ট্রিতে BCD এর প্যারেন্ট হচ্ছে A। আবার EFG এর প্যারেন্ট হচ্ছে B ইত্যাদি।
Child: কোন নডের উত্তরসূরি নড গুলো হচ্ছে চাইল্ড নড। একটা প্যারেন্ট নডের একাধিক চাইল্ড নড থাকতে পারে। ট্রি ডেটা স্ট্রাকচারে রুট নড ছাড়া বাকি সব গুলো নডই চাইল্ড নড। উপরের ছবি থেকে বলতে পারেন A এর চাইল্ড কোনটা কোনটা? ঠিক ধরেছেন। BCD হচ্ছে A এর চাইল্ড। একই ভাবে D এর চাইল্ড হচ্ছে KL। ইত্যাদি।
Siblings: যে নড গুলোর প্যারেন্ট নড একই, সেগুলো হচ্ছে Siblings। উপরের ট্রিতে BCD হচ্ছে Siblings। একই ভাবে EFG এবং KL হচ্ছে সিবলিং।
Leaf: যে নড গুলো কোন চাইল্ড নড নেই, সেগুলোই হচ্ছে Leaf নড। ট্রি এর সর্বশেষ বা টার্মিনাল নড গুলোই হচ্ছে Leaf নড। উপরের ট্রি এর C, E, F, G, H, K, L হচ্ছে লিফ নড। লিফ নডকে কেউ কেউ leaves বা এক্সট্রানলান নডও বলে।
ডিগ্রি:
- একটা নডের চিলড্রেন সংখ্যা হচ্ছে ঐ নডের ডিগ্রি। যেমন A এবং B নডের ডিগ্রি হচ্ছে 3। D নডের ডিগ্রি হচ্ছে 2। G নডের ডিগ্রি হচ্ছে 1।
- পুরো ট্রি এর নডের সর্বোচ্চ ডিগ্রিটাই হচ্ছে ট্রি এর ডিগ্রি। আমরা জেনেছি A এবং B নডের ডিগ্রি হচ্ছে 3। D নডের ডিগ্রি হচ্ছে 2। G নডের ডিগ্রি হচ্ছে 1। এখানে সর্বোচ্চ সংখ্যক ডিগ্রি হচ্ছে 3। তাই এই ট্রি এর ডিগ্রি হচ্ছে 3।
লেভেলঃ রুট নড হচ্ছে লেভেল 0। রুট নডের চাইল্ড গুলো হচ্ছে লেভেল 1। লেভেল 1 এর চাইল্ড গুলো হচ্ছে লেভেল 2 ইত্যাদি।
নিচের ছবিতে আরো পরিষ্কার বুঝা যাবেঃ
Height: লেভেলের উল্টো হচ্ছে হাইট। লীফ নডের হাইট হচ্ছে 0। লীফ নডের প্যারেন্ট নডের হাইট 1 ইত্যাদি। নিচের ছবিটি দেখিঃ
Depth: লেভেল এবং ডেফথ একই জিনিস। রুট নডের ডেফথ 0। রুট নডের চাইল্ড গুলোর ডেফথ 1 ইত্যাদি। নিচের ছবিটি দেখিঃ
Path: একটা নড থেকে আরেকটা নডে যাওয়া সময় যে নড এবং এজ গুলো পড়বে, সেগুলোর সিকোয়েন্স হচ্ছে Path। নিচের ছবিটি দেখিঃ
সাবট্রিঃ
যে কোন প্যারেন্ট নডের চাইল্ড নড গুলো ঐ প্যারেন্ট নডের সাব ট্রি। নিচের ছবিটি দেখিঃ
এখানে A এর সাব ট্রি গুলো দেখিয়েছি। একই ভাবেঃ
- B এর সাব-ট্রি গুলো হবে E, F, GH।
- C এর কোন সাব-ট্রি নেই।
- D এর সাব ট্রি গুলো হচ্ছে K, L।
- সব গুলো নডের সাব ট্রি গুলোর সমষ্টি হচ্ছে পুরো ট্রি এর সাব-ট্রি।
ফরেস্টঃ একের অধিক ট্রি এর কালেকশন হচ্ছে ফরেস্ট। নিচের ছবিটি দেখিঃ এখানে তিনটি আলাদা আলাদা ট্রি রয়েছে। এই তিনটি ট্রি এক সাথে হচ্ছে ফরেস্ট।
বুঝার সুবিধার্থে খুব সহজে ভাবে পাইথনে ট্রি এর ইমপ্লিমেন্টেশন দেওয়া হলোঃ
class Node(object):
def __init__(self, data):
self.data = data
self.children = []
def add_child(self, obj):
self.children.append(obj)
# Asigning node values
a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
e = Node("E")
f = Node("F")
g = Node("G")
h = Node("H")
k = Node("K")
l = Node("L")
# adding childs to nodes
a.add_child(b)
a.add_child(c)
a.add_child(d)
b.add_child(e)
b.add_child(f)
b.add_child(g)
g.add_child(h)
d.add_child(k)
d.add_child(l)
# printing childs of A.
for child in a.children:
print(child.data)
# printing chils of D
print("Childs of D are:")
for child in d.children:
print(child.data)
আমরা এতক্ষণ যে ট্রি নিয়ে আলোচনা করেছি, তাকে বলা হয় জেনারেল ট্রি। ট্রি এর অনেক ক্লাসিফিকেশন রয়েছে। যেমনঃ
- বাইনারি ট্রি
- বাইনারি সার্চ ট্রি
- AVL ট্রি
- B-Tree সহ আরো অনেক।
ইনশায় আল্লাহ পরবর্তী সময় বাইনারি ট্রি সহ অন্যান্য বিষয় নিয়ে লিখব। অন্যান্য লেখাঃ