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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

درخت(ساختار داده)[ویرایش]

Binary tree.svg

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

گره‌ها[ویرایش]

هر گره در درخت تعدادی( صفر یا بیشتر ) گره فرزند دارد، که در زیر آن در درخت قرار دارند( به طور قراردادی، درخت به سمت پایین رشد می‌کند، برخلاف آنچه در طبیعت می بینیم ). یک گره که فرزند دارد گره پدر آن فرزند گفته می‌شود. یک گره حداکثر 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.

پانویس[ویرایش]

  1. Root nodes
  2. heaps
  3. Leaf nodes
  4. Internal nodes
  5. Subtrees
  6. Proper tree
  7. Tree ordering
  8. Recursive tree
  9. Unordered tree
جستجو در ویکی‌انبار در ویکی‌انبار پرونده‌هایی دربارهٔ درخت (ساختار داده) موجود است.