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

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

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

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

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

اعتبار

تصاویر را habere-et-dispertire با استفاده از PGF/TikZ اثر Till Tantau ساخته است.

دستورالعمل‌های مخصوص CoffeeScript

یک نمونه از BinarySearchTree باید ۳ ویژگی داشته باشد: data، left و right.

یک نمونه باید این متدها را داشته باشد:

• insert که یک داده‌ی تازه به درخت اضافه می‌کند. این متد یک گره‌ی «برگ» تازه جایی در درخت اضافه می‌کند.
• each که یک آرگومان «callback» می‌گیرد. یعنی تابعی که روی هر داده‌ی درخت به ترتیب فراخوانی می‌شود.

این تمرین جای خوبی برای تمرین بازگشت است.