ساختمان های داده در روبی (Ruby) – درخت های دودویی

درخت، ساختمان داده‌ای است که امکان نمایش شکل‌های مختلفی از داده‌های سلسله مراتبی را به ما می‌دهد. DOM در صفحه‌های HTML، فایل‌ها و پوشه‌های روی دیسک و بازنمایی درونی برنامه‌های روبی، همگی شکل‌های مختلفی از این جنس داده هستند که به وسیله درخت می‌توان آن‌ها را به نمایش گذاشت. در این نوشته ما روی مفهوم درخت‌های دودویی در زبان برنامه نویسی روبی متمرکز خواهیم شد.

روشی که ما معمولاً برای طبقه‌بندی درخت‌ها استفاده می‌کنیم به وسیله ضریب انشعاب (branching factor) است. ضریب انشعاب نشان می‌دهد که وقتی سطوح بیشتری به یک درخت اضافه می‌کنیم، گره‌ها چگونه تکثیر می‌شوند. جای شگفتی نیست که ضریب انشعاب درخت‌های دودویی برابر با عدد ثابت 2 است.

ظاهر یک درخت دودویی به صورت زیر است:

          13
         /  \
        /    \
       /      \
      8        17
     / \      /  \
    1   11   15   25
   /\   /\   /\   /\
  x  x x  x x  x x  x

دقت کنید که ما یک گره در سطح ریشه داریم و سپس دو گره در سطح زیر آن و سپس چهار گره در سطح دوم و همین طور تا آخر.

بازنمایی فوق را یک درخت دودویی متوازن نیز می‌نامند. زمانی که می‌خواهیم جستجوی دودویی انجام دهیم، به تعریف دقیق درخت متعادل نیاز خواهیم داشت؛ اما فعلاً فرض می‌کنیم که درخت دودویی متوازن درختی است که گره‌های آن به ترتیبی چیده شده باشند که درخت تا حد امکان کوتاه باشد.

از آنجا که اغلب الگوریتم‌های جستجو به ارتفاع درخت وابسته هستند، کوتاه نگه داشتن آن‌ها برای بهبود عملکرد بسیار مهم است.

عناصر مختلف درخت به صورت گره‌هایی نمایش می‌یابند. در مورد مثال ما، گره‌ها چهار خصوصیت دارند:

هر گره یک والد و دو فرزند دارد. تنها استثنا برای این قاعده گره اول است که گره ریشه (root) نامیده می‌شود و هیچ والدی ندارد.

همانند ساختارهای داده سلسله مراتبی دیگر، روش‌های مختلفی برای پیمایش درخت‌ها وجود دارد. روش‌های عمق-اول و سطح-اول، متداول‌ترین روش‌ها محسوب می‌شوند:

رابط درخت‌های دودویی

رابط درخت دودویی ارتباط تنگاتنگی با روش استفاده از آن دارد. برای نمونه یک درخت AVL (جستجوی دودویی) متدهایی برای چرخش و متوازن‌سازی دارد؛ در حالی که درخت دودویی معمولی چنین متدهایی ندارد.

فیلم آموزش درخت جستجوی دودویی (AVL) در ساختمان داده ها (رایگان) در فرادرس

کلیک کنید

در این مقاله قصد داریم یک درخت دودویی چندمنظوره بسازیم که می‌توان از آن برای ذخیره‌سازی بازنمایی‌های درون حافظه‌ای از عبارت‌های دودویی مانند 1 + 2 × 3 و a=b استفاده کرد.

این عبارت‌ها به شکل درخت به صورت زیر در می‌آید:

      +          =
     / \        / \
    1   *      a   b
        /\
       2  3

در ابتدا متدها و خصوصیت‌های درخت دودویی را بررسی می‌کنیم:

خصوصیت‌ها

متدها

جزئیات پیاده‌سازی

در این بخش جزییات پیاده‌سازی متدهای فوق را توضیح می‌دهیم.

Initialize

این سازنده کلاس است و گره ریشه درخت را تعیین کرده و اندازه آن را مقداردهی اولیه می‌کند:

def initialize root
   self.root = root
   self.size = 1
end

Insert Left

این متد یک گره جدید در فرزند چپ گره مذکور درج می‌کند. پیچیدگی این متد برابر با (O(1 است.

شاید متوجه شده باشید که کد این متد کمی در هم است، زیرا ما بررسی‌هایی به آن اضافه کرده‌ایم تا از تغییرهای ناخواسته اجتناب کنیم. با این که این متد در سطح اپلیکیشن است؛ اما به طور کلی زمانی که یک گره را تغییر می‌دهید باید برخی بازآرایی‌ها در ساختار درخت ایجاد کنید. این موضوع خارج از حیطه این مقاله است و برای مطالعه بیشتر می‌توانید از مطالب آتی ما در این زمینه استفاده کنید.

def insert_left(node, data)
   return unless node
   raise "Can't override nodes: (" if node.left
   self.size += 1
   node.left = Node.new node, data
end

Insert Right

این متد عملکردی مانند insert_left دارد؛ اما از فرزند راست استفاده می‌کند. پیچیدگی این روش  (O(1 است.

def insert_right(node, data)
   return unless node
   raise "Can't override nodes: (" if node.right
   
   self.size += 1
   node.right = Node.new node, data
end

Remove Left

این متد زیردرختی که ریشه در فرزند چپ گره مفروض دارد را حذف می‌کند.

دقت کنید که برخلاف زبان‌هایی مانند C؛ در روبی تنها چیزی که لازم است برای حذف زیردرخت انجام شود، این است که مقدار آن برابر تهی تعیین شود. از این پس وظیفه garbage collector است که گره‌های تخصیص یافته را در حافظه آزاد کند.

پیچیدگی این متد  (O(n است که برابر با تعداد گره‌های زیردرخت است.

def remove_left(node)
   if node&.left
       remove_left(node.left)
       remove_right(node.left)
       node.left = nil
       self.size -= 1
   end
end

Remove Right

این متد زیردرختی که ریشه در فرزند چپ گره مفروض دارد را حذف می‌کند.

همچنان که در مورد remove_left گفته شد، پیچیدگی این متد برابر با (O(n است.

def remove_right(node)
   if node&.right
       remove_left node.right
       remove_right node.right
       node.right = nil
       self.size -= 1
    end
end

Merge

Merge یک متد کلاس است که یک درخت دودویی جدید را از طریق ادغام دو درخت موجود ایجاد می‌کند.

می‌توان در این متد یک مقدار برای گره ریشه درخت ادغام شده تعیین کرد. مراحل ادغام دو درخت به صورت زیر است:

• ایجاد یک گره ریشه برای درخت ادغام یافته
• ایجاد یک درخت خالی برای نگهداری ادغام
• اشاره کردن فرزند چپ گره ریشه درخت ادغام شونده به گره ریشه درخت چپ
• اشاره کردن فرزند راست گره ریشه درخت ادغام شونده به گره ریشه درخت راست
• تغییر اندازه درخت ادغام شونده

def self.merge left_tree, right_tree, data = nil
   raise "Can't merge nil trees." unless left_tree && right_tree
   root = Node.new(nil, data);
   res = BTree.new root
   res.root.left = left_tree.root
   res.root.right = right_tree.root
   res.size = left_tree.size + right_tree.size
   res
end

Print

این متد محتوای درخت کنونی را به صورت بازگشتی با اعمال قالب «pretty»، یعنی ایجاد تورفتگی نمایش می‌دهد.

def print
   print_rec self.root
end
private
def print_rec node, indent=0
   print_node node, indent
   print_rec node.lhs, indent + 1 if node&.lhs
   print_rec node.rhs, indent + 1 if node&.rhs
end
def print_node node, indent
   data = node&.data&.to_s || "nil"
   puts data.rjust indent * 4, " "
end

چه زمان از درخت‌ها باید استفاده کرد؟

درخت‌ها یکی از پرکاربردترین ساختمان‌های داده در علوم رایانه به حساب می‌آیند. درخت‌ها را می‌توان در همه جا در سیستم‌های پایگاه داده، رابط کاربری، الگوریتم‌های مقایسه داده، تجزیه‌کننده‌ها، ابزارهای زمان‌بندی و موارد بسیار دیگر یافت و می‌توان گفت که تقریباً همه جا حضور دارند.

بنابراین می‌توان گفت که ساختمان داده درخت دودویی کاربردهای کاملاً چندگانه‌ای دارد. کد منبع این مقاله را می‌توانید در این ریپو (+) مشاهده کنید.

اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های برنامه‌نویسی
• مجموعه آموزش‌های پایگاه داده و سیستم های مدیریت اطلاعات
• درخت جستجوی دودویی (BST) — ساختار داده و الگوریتم ها
• داده های ساختگی (Dummy data) در روبی، پرل و پایتون — راهنمایی از صفر تا صد
• آموزش درخت جستجوی دودویی (AVL) در ساختمان داده ها

==