درخت جست‌وجوی دودویی

دستورالعمل‌ها

اعداد را در یک درخت دودویی درج و جست‌وجو کنید.

وقتی می‌خواهیم داده‌های مرتب را نمایش دهیم، آرایه ساختار داده‌ی مناسبی نیست.

فرض کنید آرایه‌ی [1, 3, 4, 5] را داریم و ۲ را به آن اضافه می‌کنیم تا به [1, 3, 4, 5, 2] تبدیل شود؛ حالا باید کل آرایه را دوباره مرتب کنیم! می‌توانیم این وضعیت را بهتر کنیم اگر توجه کنیم که فقط باید برای عنصر جدید [1, nil, 3, 4, 5] جا باز کنیم و بعد آن عنصر را در همان جای خالی قرار دهیم. اما این کار همچنان ما را ملزم می‌کند که بسیاری از عناصر را یک خانه به پایین جابه‌جا کنیم.

اما درخت‌های جست‌وجوی دودویی می‌توانند روی داده‌های مرتب بسیار کارآمدتر عمل کنند.

درخت جست‌وجوی دودویی از مجموعه‌ای از گره‌های به‌هم‌متصل تشکیل شده است. هر گره یک تکه داده (مثلاً عدد ۳)، یک متغیر به اسم left و یک متغیر به اسم right را در خود نگه می‌دارد. متغیرهای left و right به nil یا به گره‌های دیگر اشاره می‌کنند. از آنجا که این گره‌های دیگر خودشان گره‌های دیگری زیرشان دارند، می‌گوییم متغیرهای left و right به زیردرخت‌ها اشاره می‌کنند. همه‌ی داده‌های زیردرخت چپ کوچک‌تر یا مساوی داده‌های گره‌ی جاری است و همه‌ی داده‌های زیردرخت راست بزرگ‌تر از داده‌های گره‌ی جاری است.

برای مثال، اگر گره‌ای داشتیم که داده‌ی ۴ را در خود داشت و داده‌ی ۲ را اضافه می‌کردیم، درخت ما به این شکل می‌شد:

  4
 /
2

اگر بعد از آن ۶ را اضافه می‌کردیم، به این شکل می‌شد:

  4
 / \
2   6

اگر بعد از آن ۳ را اضافه می‌کردیم، به این شکل می‌شد

   4
 /   \
2     6
 \
  3

و اگر بعد از آن ۱، ۵ و ۷ را اضافه می‌کردیم، به این شکل می‌شد

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

راهنمایی‌ها

برای کامل کردن این تمرین باید یک «نوع داده» به اسم BST بسازید که نمونه‌های Eq و Show داشته باشد و توابع زیر را پیاده‌سازی کنید:

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

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