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

برای دیگر کاربردها، درخت (ابهام‌زدایی) را ببینید.

برای دیگر معانی درخت به درخت (ابهام‌زدایی) نگاه کنید.

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

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

گره‌ها

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

گره‌های ریشه

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

گره‌های برگ

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

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

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

زیر درخت ها

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

مرتبهٔ درخت

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

منابع

• 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.

پانویس

در ویکی‌انبار پرونده‌هایی دربارهٔ درخت (ساختار داده) موجود است.