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

از ویکیپدیا، دانشنامه آزاد
پرش به ناوبری پرش به جستجو
این درخت مرتب نشده دارای مقادیر غیر منحصر به فرد و غیر باینری است، زیرا تعداد فرزندان از یک (مثلا گره 9) تا سه (گره 7) متفاوت است. گره ریشه، در بالا، والد ندارد.

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

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

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

درختانی که در محاسبات استفاده می شوند مشابه هستند اما می توانند با ساختارهای ریاضی درختان در نظریه گراف , درختان در نظریه مجموعه ها و درختان در نظریه مجموعه های توصیفی متفاوت باشند .

برنامه های کاربردی

درختان معمولاً برای نمایش یا دستکاری داده های سلسله مراتبی در برنامه هایی مانند:

درختان را می توان برای نمایش و دستکاری ساختارهای مختلف ریاضی استفاده کرد، مانند:

ساختارهای درختی اغلب برای ترسیم روابط بین چیزها استفاده می شود، مانند:

اسناد JSON و YAML را می توان به عنوان درخت در نظر گرفت، اما معمولاً با لیست ها و فرهنگ لغت های تودرتو نشان داده می شوند .

اصطلاحات

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

گره داخلی ( همچنین به عنوان گره داخلی ، به اختصار inode یا گره شاخه نیز شناخته می شود ) هر گره درختی است که دارای گره های فرزند باشد. به طور مشابه، یک گره خارجی (همچنین به عنوان گره بیرونی ، گره برگ ، یا گره پایانی نیز شناخته می شود ) هر گره ای است که گره فرزند ندارد.

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

هر گره غیر ریشه ای را می توان به عنوان گره ریشه زیردرخت خود در نظر گرفت که شامل آن گره و تمام فرزندان آن است. [a] [1]

سایر اصطلاحات مورد استفاده برای درختان:

همسایه
والدین یا فرزند.
جد
گره ای که با حرکت مکرر از فرزند به والدین قابل دسترسی است.
نسل
گره ای که با حرکت مکرر از والدین به فرزند قابل دسترسی است. همچنین به عنوان فرزند فرعی شناخته می شود .
درجه
برای یک گره معین، تعداد فرزندان آن. یک برگ لزوماً درجه صفر دارد.
درجه درخت
درجه یک درخت حداکثر درجه یک گره در درخت است.
فاصله
تعداد یال ها در امتداد کوتاه ترین مسیر بین دو گره.
مرحله
سطح یک گره تعداد لبه های موجود در مسیر منحصر به فرد بین آن و گره ریشه است. [2]
هنگام استفاده از شمارش بر اساس صفر، این همان عمق است.
عرض
تعداد گره ها در یک سطح.
عرض
تعداد برگ ها.
جنگل
مجموعه ای از یک یا چند درخت جدا از هم.
درخت سفارش داده شده
درختی ریشه دار که در آن ترتیبی برای فرزندان هر رأس مشخص شده است. کتاب هنر برنامه نویسی کامپیوتر از اصطلاح درخت oriented استفاده می کند . [3]
اندازه یک درخت
تعداد گره ها در درخت

نمونه هایی از درختان و غیر درختان

درخت نیست : دو قسمت غیر متصل A→B و C→D→E. بیش از یک ریشه وجود دارد.
درخت نیست : چرخه بدون جهت 1-2-4-3. 4 بیش از یک والد دارد (لبه ورودی).
درخت نیست : چرخه B→C→E→D→B. B بیش از یک والد (لبه ورودی) دارد.
درخت نیست : چرخه A→A. A ریشه است اما یک والد نیز دارد.
هر فهرست خطی یک درخت است

عملیات رایج

  • شمارش تمامی موارد
  • برشمردن قسمتی از درخت
  • جستجو برای یک آیتم
  • افزودن یک آیتم جدید در یک موقعیت خاص روی درخت
  • حذف یک مورد
  • هرس : حذف یک بخش کامل از درخت
  • پیوند زدن : افزودن یک بخش کامل به درخت
  • پیدا کردن ریشه برای هر گره
  • یافتن کمترین جد مشترک دو گره

روش های پیمایش و جستجو

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

نمایندگی ها

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

گره‌ها همچنین می‌توانند به‌عنوان آیتم‌هایی در یک آرایه ذخیره شوند ، با روابط بین آنها که با موقعیت‌هایشان در آرایه تعیین می‌شود (مانند یک پشته باینری ).

یک درخت دودویی را می توان به عنوان لیستی از لیست ها پیاده سازی کرد: سر یک لیست (مقدار اولین عبارت) فرزند سمت چپ (درخت فرعی) است، در حالی که دم (فهرست عبارت های دوم و بعدی) فرزند سمت راست است ( درخت فرعی). این را می توان برای اجازه دادن به مقادیر نیز تغییر داد، همانطور که در Lisp S-expressions ، که در آن سر (مقدار عبارت اول) مقدار گره است، سر دم (مقدار ترم دوم) فرزند سمت چپ است، و دم دم (لیست ترم های سوم و بعدی) فرزند مناسب است.

درختان مرتب شده را می توان به طور طبیعی با دنباله های محدود، به عنوان مثال با اعداد طبیعی، کدگذاری کرد. [4]

نظریه نوع

به عنوان یک نوع داده انتزاعی ، نوع درخت انتزاعی T با مقادیری از نوع E با استفاده از نوع جنگل انتزاعی F (فهرست درختان)، توسط توابع تعریف می شود:

مقدار: TE
کودکان: TF
صفر: () → F
گره: E × FT

با بدیهیات:

مقدار(گره( e ، f )) = e
کودکان (گره ( e ، f )) = f

از نظر تئوری نوع ، درخت یک نوع استقرایی است که توسط سازنده های nil (جنگل خالی) و گره (درختی با گره ریشه با مقدار داده شده و فرزندان) تعریف می شود.

اصطلاحات ریاضی

به عنوان یک کل، یک ساختار داده درختی یک درخت مرتب است که به طور کلی مقادیری به هر گره متصل است. به طور مشخص، (در صورت نیاز به غیر خالی بودن):

  • درختی ریشه دار با جهت "دور از ریشه" (اصطلاح باریک تر " درختی " است)، به این معنی:
    • یک نمودار جهت دار ،
    • که گراف بدون جهت زیرین آن یک درخت است (هر دو رأس دقیقاً توسط یک مسیر ساده به هم متصل می شوند)
    • با یک ریشه مشخص (یک راس به عنوان ریشه تعیین می شود)
    • که جهت لبه‌ها را مشخص می‌کند (فلش‌ها از ریشه دور هستند؛ با توجه به یک یال، گره‌ای که لبه از آن نشان می‌دهد والد و گرهی که لبه به آن اشاره می‌کند فرزند نامیده می‌شود )، همراه با:
  • یک ترتیب در گره های فرزند یک گره داده شده، و
  • یک مقدار (از نوع داده) در هر گره.

اغلب درختان دارای یک فاکتور انشعاب ثابت (به طور صحیح تر، محدود) هستند ( درجه خارج )، به ویژه همیشه دارای دو گره فرزند (احتمالاً خالی، بنابراین حداکثر دو گره فرزند غیرخالی )، بنابراین یک "درخت دودویی".

اجازه دادن به درختان خالی، برخی از تعاریف را ساده‌تر و برخی را پیچیده‌تر می‌کند: یک درخت ریشه‌دار باید خالی نباشد، بنابراین اگر درخت‌های خالی مجاز باشند، تعریف فوق به «درخت خالی یا درخت ریشه‌دار به‌طوری که ...» تبدیل می‌شود. از سوی دیگر، درخت‌های خالی تعریف عامل انشعاب ثابت را ساده می‌کنند: با درخت‌های خالی مجاز، درخت دودویی درختی است به طوری که هر گره دقیقاً دو فرزند دارد که هر کدام یک درخت است (احتمالاً خالی). مجموعه کامل عملیات روی درخت باید شامل عملیات چنگال باشد. [ توضیح لازم است ]

همچنین ببینید

یادداشت ها

  1. ^ این با تعریف رسمی زیردرختی که در نظریه گراف استفاده می‌شود، متفاوت است، که زیرگرافی است که یک درخت را تشکیل می‌دهد – لازم نیست همه فرزندان را شامل شود. به عنوان مثال، گره ریشه به خودی خود یک زیردرخت در مفهوم نظریه گراف است، اما نه در مفهوم ساختار داده (مگر اینکه هیچ نسلی وجود نداشته باشد).

منابع

  1. وایستاین، اریک دبلیو. "زیردرخت" . دنیای ریاضی .
  2. سوزانا اس. اپ (اوت 2010). ریاضیات گسسته با برنامه های کاربردی Pacific Grove، CA: Brooks/Cole Publishing Co. p. 694. شابک 978-0-495-39132-6.
  3. دونالد کنوت (۱۹۹۷). "بخش 2.3.4.2: درختان جهت دار". هنر برنامه نویسی کامپیوتر . جلد 1: الگوریتم های بنیادی (ویرایش سوم). ادیسون-وسلی. پ. 373.
  4. ^ L. Afanasiev; پی بلکبرن; I. Dimitriou; ب. گایف; E. Goris; ام. مارکس; M. de Rijke (2005). "PDL برای درختان سفارش داده شده" (PDF) . مجله منطق های کاربردی غیر کلاسیک . 15 (2): 115-135. doi : 10.3166/jancl.15.115-135 . S2CID 1979330 .  

ادامه مطلب

پیوندهای خارجی