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

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

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

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

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

اعتبار

تصاویر با استفاده از PGF/TikZ که Till Tantau ساخته است، توسط habere-et-dispertire ساخته شده‌اند.