درخت (ساختار داده)

درخت (به انگلیسی: tree) در علوم کامپیوتر، ساختار دادهٔ پر استفاده است که شبیه به یک ساختار درختی با مجموعه‌ای از گره‌های متصل به هم است. درخت یک گراف همبند بدون دور است. اکثر نویسندگان این قید را نیز اضافه می‌کنند که گراف باید بدون جهت باشد. به علاوه بعضی قید بدون وزن بودن یال‌ها را نیز اضافه می‌کنند.

گره‌ها

1. هر گره در درخت تعدادی (صفر یا بیشتر) گره فرزند دارد، که در زیر آن در درخت قرار دارند (به‌طور قراردادی، درخت به سمت پایین رشد می‌کند، برخلاف آنچه در طبیعت می‌بینیم). یک گره که فرزند دارد گره پدر آن فرزند گفته می‌شود. یک گره حداکثر ۱ پدر دارد. ارتفاع یک گره طول طولانی‌ترین مسیر پایین رو از آن گره به یک برگ است. طول ریشه طول درخت نامیده می‌شود. مسیری که از گره به ریشه وصل می‌شود مسیر ریشه نام دارد و طول این مسیر عمق آن گره است.

گره‌های ریشه

بالاترین گره درخت گره ریشه نام دارد. پس گره ریشه پدر ندارد. این گره، گرهی است که عملیات روی درخت معمولاً از آن شروع می‌شود. (هر چند بعضی الگوریتم‌ها از برگ شروع شده و به ریشه ختم می‌شوند). بقیهٔ گره‌ها با دنبال کردن یال‌ها از گره ریشه قابل دسترسی اند. در نمودار درخت عموماً گره ریشه در بالا رسم می‌شود. در بعضی درخت‌ها، مثل پشته ها، گره ریشه ویژگی‌های خاصی دارند. هر گره در یک درخت را می‌توان ریشهٔ یک زیر درخت در نظر گرفت. که این زیر درخت درختی است ریشه دار که آن گره ریشهٔ آن است

و کسی پس از خواندن این متن از خود نپرسید که چطور این کسی که به این قشنگی درخت رو از خود درخت واقعی که بنده افتخار کاشت و برداشت و حتی افتخار خوردن میوه آن نصیبم شده را در جان‌هایی که حال از تمدن و پیشرفت رو به زوال از پوچی که همان سوراخ بزرگی است که مبنا میخوانندش و روح پوچی رو در ظاهر هم نتوانسته شبیه بقیه کپی‌های دیگر حفظ کند و حتی زورش به نگه داشتنش شکل ظاهری خود نرسیده توانسته کلی از راه‌های دانش را که جستجوی همه کارهای عالم و اثبات‌ها را همین دانشمندان به ظاهر دانا به آن گره می‌زنند درخود نگه دارد. پس دراینجا کسی به اشتباه آن اصلی را که دانشمندان که تا حالا به هستِ اصلی دانِ آن که تبدیل شده به دام آن نگاهی نکرده‌اند تمام چرخ‌های نیلوفری را در حیرت فرو برده که آیا اصلاً این درخت او که دانش است اصلاً دربارهٔ علم صحبت می‌کند؟

یعنی بی زبان ترین‌ها هم می‌فهمند اشتباه را چرا که کل هستی از یک پیوند یکتا و تودر تو که الان جهت بیت کوین رو گرفته و شده ارزشی که همه ارزشها را برای بزرگ کردن آن فدا می‌کنند و نمی‌دانند که هستی از همان اول به همین پایداری ظاهری بیت کوین است که هیچ ورود غیر محترمی را راه ندارد ولی در عین حال براس ورودهای محترم حتی در هر لحظه هدایای ارزشمندی دارد که حال انسان متمدن امروز آن را صلاح کار خود کرده و اصل آن را سپرده دست افسانه‌ها

باشد که این جهت درست، دری به سمت درهای بسیار دم دستی تر و قابل فهم تر و حتی جهان کوچکتر ولی ۱۰۰ درصدی و برپایه ارزش‌های واقعی نهادن

گره‌های برگ

پایین‌ترین گره‌های یک درخت گره‌های برگ نام دارند. چون این گره‌ها زیرترین گره هستند هیچ فرزندی ندارند.

گره‌های داخلی

یک گره داخلی هر گرهی است که فرزند داشته باشد پس برگها گره داخلی نیستند.

زیر درخت ها

زیر درخت بخشی از درخت است که خود یک درخت کامل را تشکیل می‌دهد. هر گره در درخت T با تمام گره‌های زیر آن زیر درخت درخت T را تشکیل می‌دهد. زیر درخت متناظر با گره ریشه درخت اصلی است. زیر درخت متناظر با بقیهٔ رئوس زیر درخت سره گفته می‌شود.

مرتبهٔ درخت

درخت‌ها دو نوع اصلی هستند. درخت بازگشتی یا درخت نامرتب درختی است که فرزندان هر رأس ترتیب خاصی ندارند و درخت مرتب درختی است که در آن ترتیب خاصی اعمال می‌شود. برای مثال می‌توان به هر رأس عددی طبیعی مربوط کرد.

محتویات اعضا

هر عضو در درخت دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه‌شدن آن‌ها به درخت دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید های$a_{1}<a_{2}<a_{3}<...<a_{n}$ باشد. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ‌ترین فرزند آن مقدار کمتر مساوی با $a_{1}$ و فرزند دوم آن مقدار کمتر مساوی با $a_{2}$ و بیشتر از $a_{1}$ دارد و به همین ترتیب فرزند i-ام مقداری بزرگتر از $a_{i-1}$ و کمتر مساوی با $a_{i}$ دارد.

حال در اینجا با استفاده از زبان برنامه‌نویسی پایتون یک کلاس برای اعضا می‌نویسیم.

class Node:
    def __init__(self, max_cache, key):
        self.max_child = max_child
        self.child = []
        self.key = key
    def isfull(self):
        if len(self.cache) == self.max_cache:
            return True
        else:
            return False

درج عناصر

اضافه کردن یک عضو جدید شبیه به درخت دودویی است. فرض کنید می‌خواهید مقدار c را به درخت اضافه کنید. ابتدا ریشه را در نظر می‌گیریم. بعد با مقایسه کردن مقدار c با کلیدها زیر درختی که این مقدار باید به ان اضافه شود را پیدا می‌کنیم. این روند را ادامه می‌دهیم تا به یک راس ایجاد نشده برسیم سپس با اضافه‌کردن ان مقدار c را به درخت اضافه می‌کنیم.

حذف عناصر

حذف یک عنصر هم دقیقاً شبیه درخت دودویی است. ابتدا باید راسی را که می‌خواهیم حذف کنیم پیدا کنیم که این کار همانند زمانی است که می‌خواستیم هنگام درج راس خالی مناسب را پیدا کنیم. بعد از پیدا کردن راس مناسب کافی است مانند درخت دودویی، بزرگ‌ترین راس در زیردرخت ان را در ان جایگزین کنیم و ان راس را حذف کنیم. اگر فرض کنیم درخت متوازن است در نتیجه هزینه درج و حذف هم برابر است با پیدا کردن راس مناسب که برابر با ارتفاع درخت که $log_{B}(N)$ است می‌باشد.

مقایسه فرکتال با درخت

در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما این دو از نظر مقدار حافظه بسیار متفاوت هستند. در درخت هر عضو B بچه دارد و در نتیجه هر راس حافظه‌ای از مرتبه B دارد. اما در فرکتال هر عضو دارای ${\sqrt {B}}$ فرزند و ${\sqrt {B}}$ مقدار است و در نتیجه مرتبه حافظه مورد نیاز هر راس ${\sqrt {B}}$ است. از طرفی اگر N مقدار را در درخت و فرکتال ذخیره کنیم، درخت دارای N راس و فرکتال دارای ${\frac {N}{\sqrt {B}}}$ راس است. در نتیجه حافظه مورد نیاز درخت B برابر فرکتال است.

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

منابع

• Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3: Trees, pp.308–423.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.253–320.