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

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

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

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

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

پیاده‌سازی

پیاده‌سازی یک ساختار درختی کارآمد و قابل‌تغییر در Cairo (یا هر زبان کاملاً تابعی با حافظه‌ی تغییرناپذیر) چالش‌برانگیز است، چون این زبان‌ها طوری طراحی شده‌اند که از تغییر داده‌ها پس از ساخته‌شدنشان پرهیز کنند. این تغییرناپذیری یعنی به‌جای به‌روزرسانی مستقیم یک گره از درخت، هر بار که آن را تغییر می‌دهید باید نسخه‌ی تازه‌ای از درخت ساخته شود.

برای اینکه ببینید چرا این‌طور است، یک ساختار درختی دودویی ساده را در نظر بگیرید که هر گره آن یک فرزند چپ و یک فرزند راست دارد. فرض کنید با درخت کوچکی مانند این شروع می‌کنیم:

       1
      / \
     2   3

حالا فرض کنید می‌خواهیم گره‌ی تازه‌ای مانند 4 را به عنوان فرزند چپ گره‌ی 2 اضافه کنیم. در یک زبان کاملاً تابعی (مثل Cairo یا Haskell)، حافظه تغییرناپذیر است، پس نمی‌توانیم گره‌ی 4 را به‌سادگی مستقیماً به 2 اضافه کنیم. در عوض، باید برای هر گره در مسیر از ریشه تا گره‌ی تغییریافته نسخه‌ی تازه‌ای بسازیم، چون هر گره در این مسیر اکنون به یک زیردرخت تازه یا تغییریافته اشاره می‌کند.

روند کار چنین خواهد بود:

1. افزودن گره‌ی ۴ به گره‌ی ۲:

   • یک نسخه‌ی تازه از گره‌ی 2 بسازید که اکنون 4 را به عنوان فرزند چپ خود دارد.

       2'
      / 
     4   
   

2. به‌روزرسانی گره‌ی ریشه:

   • چون گره‌ی 1 در ابتدا به 2 قدیمی اشاره می‌کرد، نسخه‌ی تازه‌ای از گره‌ی ریشه یعنی 1' می‌سازیم که اکنون در سمت چپ به گره‌ی به‌روزشده‌ی 2' اشاره می‌کند و گره‌ی 3 را در سمت راست نگه می‌دارد.

       1'
      / \
     2'  3
   

بنابراین، درخت حاصل چنین می‌شود:

       1'
      / \
     2'  3
    /
   4

این درخت تازه (1') هنوز شبیه درخت اصلی است، اما با مسیری به‌روزشده. نکته‌ی کلیدی این است که برای حفظ تغییرناپذیری باید هر گره در مسیر (1 تا 2) را از نو می‌ساختیم، چون گره‌های موجود را نمی‌توان در جای خودشان تغییر داد. درخت اصلی هنوز وجود دارد (مثلاً برای همه‌ی ارجاع‌هایی که به ریشه‌ی اصلی آن یعنی 1 دارند)، در حالی که این درخت تازه وضعیت تغییریافته را نشان می‌دهد.

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