آموزش درختساختمان داده

۰۱ ورودی مرتب، بدترین حالت است

همان کد را با شش هزار عدد که از کوچک به بزرگ وارد شده‌اند پر کنید و پیدا کردن آخرین عدد ۶۰۰۰ مقایسه می‌برد. هر عدد تازه از همه بزرگ‌تر بود، پس همیشه سمت راست رفت، و درختی که ساخته شد یک زنجیره است. کارایی از بین رفت و هیچ چیزی خطا نداد؛ فقط کند شد.

این بدترین حالت دقیقا همان حالتی است که در عمل زیاد پیش می‌آید، چون داده‌ای که از یک پایگاه داده می‌آید معمولا مرتب است. راه‌حل‌ها یا درخت را خودکار متوازن می‌کنند یا ترتیب ورود را به‌هم می‌ریزند، و پایتون هیچ درخت جست‌وجوی آماده‌ای در کتابخانه استانداردش ندارد، که خودش یک واقعیت به‌دردبخور است: برای جست‌وجوی عضویت، جست‌وجو با کلید، و عضویت در زمان ثابت جواب پیش‌فرض است و درخت وقتی لازم می‌شود که ترتیب هم بخواهید.

۰۲ دو راه راه رفتن روی درخت، و کاری که هرکدام می‌کنند

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

عمق‌اول با بازگشت دو سطر می‌شود و همان‌جا هم سقف دارد: درخت خیلی عمیق با RecursionError می‌ایستد، که دقیقا موضوع تابعی که خودش را صدا می‌زند، و جای شرط پایان است. نسخه بی‌بازگشتش یک پشته دستی است و همان کار را بدون سقف انجام می‌دهد: آخرین ورودی اول، اولین ورودی اول، و جای هرکدام.

۰۳ جایی که کار گیر می‌کند، دسته‌بندی تخت در پایگاه داده است

تقریبا هر فروشگاه اینترنتی که در ایران ساخته می‌شود، دسته‌بندی کالایش را در یک جدول با ستون شناسه والد نگه می‌دارد. این ذخیره درست است و مسئله جای دیگری است: کدی که برای نمایش منو نوشته می‌شود، برای هر گره یک کوئری می‌زند و برای یک درخت صدتایی صد بار به پایگاه داده می‌رود. صد کوئری روی لپ‌تاپ برنامه‌نویس هیچ است و روی یک سرور مشترک، باز شدن صفحه اول سایت را به تعویق می‌اندازد. کاری که این را تمام می‌کند یک کوئری است که همه سطرها را می‌گیرد و درخت را یک بار در حافظه می‌سازد؛ صد گره در حافظه هیچ هزینه‌ای ندارد و صد رفت‌وبرگشت شبکه همه هزینه را دارد.

۰۴ ابزار، و سالی که این حرف درست است

در سال ۲۰۲۶ برای درخت‌های کوچک، دیکشنری تودرتو و json در کتابخانه استاندارد کافی‌اند و رایگان؛ جای نوشتن یک کلاس گره با اشاره‌گر چپ و راست را گرفته‌اند، که برای داده‌ای که فقط باید خوانده و چاپ شود کد اضافه است. وقتی ترتیب و بازه لازم است و داده در حافظه جا می‌شود، bisect در همان کتابخانه روی یک فهرست مرتب همان کار درخت جست‌وجو را می‌کند و پیاده‌سازی ندارد که خراب شود. برای درخت متوازن واقعی باید سراغ بسته بیرونی رفت، و آن انتخاب به شبکه وابسته است.

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