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

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

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

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

فرض کنید آرایه‌ی [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