درخت در ساختمان داده — کاربرد و انواع همراه با مثال

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

مقدمه‌ای بر ساختمان داده

ساختمان داده «Data Structure» روشی برای سازماندهی، مدیریت و ذخیره‌سازی داده‌ها در حافظه کامپیوتر است تا به‌صورت مؤثرتری به آن‌ها دسترسی داشته باشیم و بتوانیم عملیات مختلف را روی آن‌ها انجام دهیم. ساختمان‌های داده به برنامه‌نویسان و مهندسان کمک می‌کنند تا داده‌ها را به شکلی مرتب و قابل استفاده برای حل مسائل پیچیده‌تر در برنامه‌نویسی و الگوریتم‌ها ذخیره کنند.

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

تعریف درخت

درخت «Tree» در ساختمان داده یک روش برای سازماندهی و ذخیره‌سازی اطلاعات است که داده‌ها را به شکل سلسله‌مراتبی مرتب می‌کند. این ساختار از چندین «گره» یا «نود» تشکیل شده که هر کدام می‌تواند به گره‌های دیگر متصل باشد. اولین گره که «ریشه» نام دارد، نقطه شروع درخت است. هر گره می‌تواند فرزندانی داشته باشد که داده‌های مرتبط با آن را نگه می‌دارند و ارتباط بین گره‌ها به کمک یال‌ها برقرار می‌شود.

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

چرا درخت یک ساختار داده غیر خطی است؟

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

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

پیشنهاد برای شما: پاورپوینت الگوریتم شاخه و کران

کلیک کنید

اهمیت درخت در کامپیوتر

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

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

• پایگاه‌داده‌ها (Database)، جستجوی و بازیابی سریع داده‌ها
• فایل‌های سیستم عامل (File System) و برای نمایش و مدیریت سلسله‌مراتب پوشه‌ها
• الگوریتم‌های فشرده‌سازی داده
• پردازش زبان طبیعی
• مدل‌های تصمیم‌گیری و یادگیری ماشین
• شبکه‌های رایانه‌ای و مسیریابی
• و …

فیلم آموزشی درس ساختمان داده (رایگان)

کلیک کنید

اصطلاحات رایج درخت در ساختمان داده

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

• گره (Node): هر گره یک عنصر از درخت است که حاوی داده و ارجاعاتی به گره‌های دیگر (فرزندان) می‌باشد. گره‌ها می‌توانند حاوی یک یا چند داده باشند و درخت از طریق این گره‌ها تشکیل می‌شود.
• ریشه (Root): گره ریشه بالاترین گره در درخت است که هیچ گره والد ندارد. درخت از این گره شروع می‌شود و به سایر گره‌ها تقسیم می‌شود. درخت‌ها می‌توانند تنها یک ریشه داشته باشند.
• گره‌های فرزند (Child Nodes): هر گره‌ای که به یک گره والد متصل است، گره فرزند نامیده می‌شود. هر گره می‌تواند چندین فرزند داشته باشد و این ارتباط بین گره‌ها را برقرار می‌کند.
• گره‌های والد (Parent Nodes): هر گره‌ای که به گره‌های فرزند اشاره می‌کند، گره والد نامیده می‌شود. ریشه درخت والد ندارد، در حالی که هر گره دیگر می‌تواند دارای یک والد باشد.
• گره‌های برگ (Leaf Nodes): گره‌هایی هستند که هیچ گره فرزندی ندارند و در انتهای درخت قرار دارند. این گره‌ها به عنوان نقطه‌های پایانی در درخت شناخته می‌شوند.

پیشنهاد برای شما: پاورپوینت در مورد درخت پوشای کمینه

کلیک کنید

• سطح (Level): سطح یک گره نشان‌دهنده عمق آن در درخت است. سطح ریشه برابر با ۰ است و به ازای هر گام به سمت پایین در درخت، سطح یک واحد افزایش می‌یابد.
• عمق (Depth): عمق یک گره، تعداد لبه‌ها از گره ریشه تا آن گره خاص را نشان می‌دهد. به عبارت دیگر، عمق نشان‌دهنده فاصله یک گره از ریشه است.
• ارتفاع (Height): ارتفاع یک درخت به طولانی‌ترین مسیر از ریشه تا دورترین گره برگ اشاره دارد. ارتفاع نشان‌دهنده حداکثر عمق درخت است. به عبارت دیگر، ارتفاع درخت برابر با حداکثر عمق گره‌های آن است.
• یال (Edge): یال، ارتباط بین دو گره را نشان می‌دهد. هر گره می‌تواند به گره‌های فرزند خود از طریق یال متصل باشد.
• زیر درخت (Subtree): هر گره به همراه تمامی گره‌های فرزند آن، یک زیر درخت را تشکیل می‌دهند. به عبارت دیگر، زیر درخت‌ها ساختارهای کوچکی هستند که خودشان می‌توانند درخت‌های مستقل باشند.

مثال برای درخت در ساختمان داده

درختی که در تصویر مشاهده می‌کنید، شامل گره‌های مختلفی است که هر یک نقش خاصی دارند. در ادامه، گره‌های این درخت را به ترتیب توضیح می‌دهیم:

• گره ریشه (Root Node): گره شماره ۱، گره ریشه درخت است و بالاترین گره محسوب می‌شود. این گره والد اصلی همه گره‌های دیگر است و هیچ والد دیگری ندارد.
• گره‌های داخلی (Internal Nodes): این گره‌ها گره‌هایی هستند که هم دارای فرزند بوده و هم خودشان از گره‌ای دیگر منشعب شده‌اند. در این درخت، گره‌های ۲، ۳، ۴، ۵، ۶، و ۷ به عنوان گره‌های داخلی در نظر گرفته می‌شوند.
• گره‌های برگ (Leaf Nodes): این گره‌ها گره‌هایی هستند که فرزندی ندارند و در پایین‌ترین سطح درخت قرار دارند. گره‌های ۸، ۹، ۱۰، و ۱۱ گره‌های برگ در این درخت هستند.
• سطح (Level):
  • سطح ۰: گره ۱ (ریشه)
  • سطح ۱: گره‌های ۲ و ۳
  • سطح ۲: گره‌های ۴، ۵، ۶، و ۷
  • سطح ۳: گره‌های ۸، ۹، ۱۰، و ۱۱
• عمق (Depth): عمق یک گره، فاصله آن تا ریشه است، که با تعداد یال‌های بین آن‌ها اندازه‌گیری می‌شود. سطح هر گره، نشان‌دهنده فاصله‌اش از ریشه است و مشابه عمق آن است، اما به صورت سطح‌های مختلف مشخص می‌شود. در این مثال سطح با عمق برابر است.
• ارتفاع (Height): ارتفاع یک گره، بیشترین فاصله آن گره تا یک گره برگ است. به عبارت دیگر، تعداد یال‌هایی که باید طی شود تا از آن گره به دورترین برگ برسیم. ارتفاع کل درخت (ارتفاع گره ریشه) برابر با ارتفاع بزرگترین گره برگ است.
  • ارتفاع ۰: گره‌های ۸، ۹، ۱۰ و ۱۱ (چون خودشان برگ هستند)
  • ارتفاع ۱: گره‌های ۴، ۵، ۶ و ۷
  • ارتفاع ۲: گره‌های ۲ و ۳
  • ارتفاع ۳: گره ۱ (ریشه درخت)

پیشنهاد برای شما: پاورپوینت درباره الگوریتم فلوید وارشال

کلیک کنید

انواع درخت ها

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

انواع درخت ها بر اساس تعداد فرزندان

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

درخت دودویی (Binary Tree)

درخت دودویی به این معنی است که هر گره می‌تواند حداکثر دو فرزند داشته باشد. این درخت‌ها پایه‌ای برای انواع دیگر درخت‌های دودویی هستند. در واقع، نام “دودویی” خود نشان می‌دهد که هر گره می‌تواند صفر، یک یا دو فرزند داشته باشد.

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

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

• مثال:

فرض کنیم بخواهیم یک درخت دودویی با مقادیر [۱، ۲، ۳، ۴، ۵، ۶، ۷] بسازیم. می‌توانیم این درخت را به شکل زیر سازماندهی کنیم:

• سطح ۰: ۱ را به عنوان ریشه درخت در نظر می‌گیریم.
• سطح ۱: گره‌های ۲ و ۳ را به ترتیب به عنوان فرزندان چپ و راست ریشه قرار می‌دهیم.
• سطح ۲: گره‌های ۴ و ۵ را به ترتیب به عنوان فرزندان چپ و راست گره ۲ اضافه می‌کنیم.
• سطح ۳: گره‌های ۶ و ۷ را به ترتیب به عنوان فرزندان چپ و راست گره ۳ اضافه می‌کنیم.

درخت سه‌تایی (Ternary Tree)

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

• مثال:

فرض کنیم بخواهیم یک درخت سه‌تایی با مقادیر [۱۵، ۲۵، ۳۵، ۴۵، ۵۵، ۶۵ ،۷۵، ۸۵ ،۹۵، ۱۰۵] بسازیم. درخت سه‌تایی به صورت زیر خواهد بود:

• سطح ۰: گره ریشه ۱۵ است.
• سطح ۱: گره‌های ۲۵، ۳۵ و ۴۵ به ترتیب به عنوان فرزندان چپ، میانی، و راست گره ریشه (یعنی ۱۵) قرار می‌گیرند.
• سطح ۲: گره‌های ۵۵، ۶۵، و ۷۵ به ترتیب به عنوان فرزندان چپ، میانی، و راست گره ۲۵ اضافه می‌شوند. گره‌های ۸۵، ۹۵، و ۱۰۵ به ترتیب به عنوان فرزندان چپ، میانی، و راست گره ۳۵ اضافه می‌شوند.
• توجه: گره ۴۵ در این مثال فرزندی ندارد.

درخت عمومی (Generic Tree)

درخت عمومی یا درخت N-تایی (N-ary Tree یا Generic Tree) ساختار داده‌ای است که در آن هر گره می‌تواند تعداد متغیری از فرزندها داشته باشد. برای ساخت یک درخت عمومی ابتدا باید تصمیم بگیریم که در این درخت هر گره می‌تواند حداکثر چند فرزند داشته باشد. درخت عمومی برای نمایش ساختارهای پیچیده و سلسله‌مراتبی که به تعداد زیادی زیرمجموعه نیاز دارند مناسب است.

• مثال:

فرض کنیم مقادیر [۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰] داریم و می‌خواهیم یک درخت عمومی از این مقادیر بسازیم:

• سطح ۰: مقدار ۱ به عنوان ریشه درخت انتخاب می‌شود.
• سطح ۱: گره ۱ می‌تواند حداکثر ۵ فرزند داشته باشد، بنابراین مقادیر بعدی یعنی ۲، ۳، ۴، ۵ و ۶ به عنوان فرزندان گره ۱ اضافه می‌شوند.
• سطح ۲: اکنون، هر یک از گره‌های سطح ۱ نیز می‌توانند تا ۵ فرزند داشته باشند. برای مثال می‌توان به ترتیب مقابل، فرزندان هر گره را اضافه کنیم؛ گره ۲ دارای فرزندان ۷ و ۸ است؛ گره ۳ فرزند ندارد؛ گره ۴ دارای فرزند ۹ است؛ گره ۵ فرزند ندارد؛ گره ۶ دارای فرزند ۱۰ است و به فرزند دیگری نیاز ندارد چون به انتهای مقادیر رسیدیم.

انواع درخت ها بر اساس مقدار گره

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

درخت جستجوی دودویی (Binary Search Tree)

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

• مثال:

برای ساخت یک درخت جستجوی دودویی با مقادیر [۸، ۳، ۱۰، ۱، ۶، ۹، ۱۴] مقادیر را به گونه‌ای قرار می‌دهیم که هر گره مقدار کمتری از خود را به سمت چپ و مقدار بیشتری از خود را به سمت راست داشته باشد. به این ترتیب، ساختار به شکل زیر خواهد بود:

• سطح ۰: ابتدا، ۸ را به عنوان ریشه قرار می‌دهیم.
• سطح ۱: عدد ۳ کمتر از ۸ است، بنابراین آن را به عنوان فرزند چپ ۸ قرار می‌دهیم. عدد ۱۰ بزرگتر از ۸ است، بنابراین آن را به عنوان فرزند راست ۸ قرار می‌دهیم.
• سطح ۲: عدد ۱ کمتر از ۸ و همچنین کمتر از ۳ است، بنابراین آن را به عنوان فرزند چپ ۳ قرار می‌دهیم. عدد ۶ کمتر از ۸ ولی بیشتر از ۳ است، بنابراین آن را به عنوان فرزند راست ۳ قرار می‌دهیم. عدد ۹ کمتر از ۱۰ ولی بیشتر از ۸ است، بنابراین آن را به عنوان فرزند چپ ۱۰ قرار می‌دهیم. عدد ۱۴ بزرگتر از ۱۰ است، بنابراین آن را به عنوان فرزند راست ۱۰ قرار می‌دهیم.
• توجه: درصورتی گه ارقام آرایه از ابتدا مرتب باشند یک درخت متوازن خواهیم داشت.

درخت AVL

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

• مثال:

برای ساخت یک درخت جستجوی دودویی با مقادیر [۱۲، ۸، ۱۸، ۵، ۱۱، ۱۷، ۴] مقادیر را به صورت زیر قرار می‌دهیم:

• سطح ۰: درخت خالی است، بنابراین ۱۲ به‌عنوان ریشه قرار می‌گیرد.
• سطح ۱: ۸ < 12 است، پس به عنوان فرزند چپ ۱۲ قرار می‌گیرد. ۱۸ > 12 است، پس به عنوان فرزند راست ۱۲ قرار می‌گیرد. درخت متوازن باقی می‌ماند.
• سطح ۲: ۵ < 12 و ۵ < 8، پس ۵ به عنوان فرزند چپ ۸ قرار می‌گیرد. ۱۱ < 12 و ۱۱ > 8، پس ۱۱ به عنوان فرزند راست ۸ قرار می‌گیرد. ۱۷ < 18 و ۱۷ > 12، پس ۱۷ به عنوان فرزند چپ ۱۸ قرار می‌گیرد. توازن حفظ شده است.
• سطح ۳: ۴ < 12، ۴ < 8، و ۴ < 5، بنابراین ۴ به عنوان فرزند چپ ۵ قرار می‌گیرد. درخت هنوز متوازن است.

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

درخت‌های قرمز-سیاه (Red-Black Trees)

درخت قرمز-سیاه (Red-Black Tree) نوعی درخت جستجوی دودویی است که به منظور حفظ توازن و بهبود کارایی در جستجو، درج و حذف داده‌ها طراحی شده است. هر گره در این درخت می‌تواند یکی از دو رنگ قرمز یا سیاه باشد.

درخت‌های قرمز-سیاه در پیاده‌سازی بسیاری از ساختارهای داده پرکاربرد مانند مجموعه‌ها (Set) و نقشه‌ها (Map) استفاده می‌شوند. همچنین، سیستم‌های مدیریت فایل، پایگاه‌های داده و حافظه پنهان (Cache) از این نوع درخت استفاده می‌کنند تا عملکرد بهینه‌تری داشته باشند.

• مثال:

می‌خواهیم با مقادیر [۷، ۳، ۱۸، ۱۰، ۲۲، ۸، ۱۱، ۲۶] یک درخت قرمز-سیاه بسازیم. در هر مرحله، قوانین رنگ‌آمیزی و چرخش‌ها را رعایت می‌کنیم:

سطح ۰: چون درخت خالی است، مقدار ۷ به عنوان ریشه درخت قرار می‌گیرد و سیاه رنگ می‌شود (طبق قانون، ریشه باید سیاه باشد).

سطح ۱: مقدار ۳ از ۷ کوچکتر است، پس به عنوان فرزند چپ ۷ قرار می‌گیرد و آن را قرمز رنگ می‌کنیم. مقدار ۱۸ از ۷ بزرگتر است، بنابراین به عنوان فرزند راست ۷ قرار می‌گیرد و آن را قرمز رنگ می‌کنیم. درخت همچنان متوازن است و هیچ دو گره قرمز پشت سر هم نداریم.

سطح ۲: مقدار ۱۰ از ۷ بزرگتر و از ۱۸ کوچکتر است، بنابراین به عنوان فرزند چپ ۱۸ قرار می‌گیرد و آن را قرمز رنگ می‌کنیم. اکنون دو گره قرمز پشت سر هم داریم (۱۸ و ۱۰)، که قوانین درخت قرمز-سیاه را نقض می‌کند. برای حل این مشکل، گره‌های پدر (۱۸) و عموی آن (۳) را سیاه و ریشه (۷) را قرمز می‌کنیم.

در ادامه میخواهیم مقدار ۲۲ را قرار دهیم. مقدار ۲۲ از ۷ و ۱۸ بزرگتر است، بنابراین به عنوان فرزند راست ۱۸ قرار می‌گیرد و آن را قرمز رنگ می‌کنیم.

سطح ۳: مقدار ۸ از ۷ بزرگتر و از ۱۰ کوچکتر است، بنابراین به عنوان فرزند چپ ۱۰ قرار می‌گیرد و آن را قرمز رنگ می‌کنیم. حالا دو گره قرمز پشت سر هم داریم (۱۰ و ۸). برای حل این مشکل، گره پدر (۱۰) و عمو (۲۲) را سیاه و گره والدین آن‌ها یعنی ۱۸ را قرمز می‌کنیم.

مقدار ۱۱ از ۷ و ۱۰ بزرگتر است، پس به عنوان فرزند راست ۱۰ قرار می‌گیرد و قرمز رنگ می‌شود. مقدار ۲۶ از همه مقادیر بزرگ‌تر است، بنابراین به عنوان فرزند راست ۲۲ قرار می‌گیرد و قرمز رنگ می‌شود. در نهایت درخت همچنان متوازن است و تمام قوانین درخت قرمز-سیاه رعایت شده‌اند.

درخت Segment

درخت‌های segment یا Segment Tree یک ساختار داده‌ای بسیار کارآمد هستند که به منظور پردازش و ذخیره‌سازی بازه‌ها (segments) از داده‌ها طراحی شده‌اند. این ساختار به ویژه در مشکلاتی که نیاز به انجام عملیات روی بازه‌های متوالی از یک آرایه (مانند جمع، حداقل، حداکثر، یا سایر محاسبات) دارند، بسیار مفید است. کاربردهای این درخت عبارتند از:

ساختار درختی: درخت‌های segment به صورت یک درخت دودویی سازمان‌دهی می‌شوند. هر گره در این درخت نمایانگر یک بازه (segment) از داده‌ها است. گره ریشه نمایانگر کل آرایه است و هر گره داخلی نمایانگر یک زیرمجموعه (sub-segment) از آن آرایه است.

عملیات کارآمد: درخت‌های segment به ما این امکان را می‌دهند که عملیات‌هایی مانند جمع، حداقل و حداکثر را روی بازه‌های مختلف آرایه با پیچیدگی زمانی 𝑂(log⁡𝑛) انجام دهیم. این در حالی است که اگر بخواهیم به طور مستقیم از آرایه استفاده کنیم، این عملیات‌ها ممکن است زمان بیشتری بگیرند.

به‌روزرسانی‌های سریع: همچنین، در صورت تغییر در مقادیر یک یا چند عنصر از آرایه، به‌روزرسانی درخت segment با پیچیدگی زمانی 𝑂(log⁡𝑛) انجام می‌شود. این امر به ما این امکان را می‌دهد که به راحتی و به سرعت به تغییرات پاسخ دهیم.

• مثال:

فرض کنید این آرایه [۱, ۳, ۵, ۷, ۹, ۱۱] از اعداد داریم و می‌خواهیم یک درخت segment برای آن بسازیم:

ساخت درخت: از گره ریشه شروع می‌کنیم و بازه کلی آرایه را در آن ذخیره می‌کنیم. سپس آرایه را به دو زیرمجموعه تقسیم می‌کنیم و در هر گره، نتیجه عملیات مورد نظر (مانند جمع یا حداقل) را ذخیره می‌کنیم.

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

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

پیشنهاد برای شما: ارائه درباره الگوریتم دایجسترا

کلیک کنید

پیمایش درخت در ساختمان داده

پیمایش درخت به روش‌های مختلفی انجام می‌شود که هر یک از آن‌ها هدف خاصی دارند و در موقعیت‌های متفاوتی به کار می‌روند. سه نوع اصلی از این روش‌ها عبارتند از: «پیمایش به‌ترتیب» (In-Order Traversal)، «پیمایش پیش‌ترتیب» (Pre-Order Traversal) و «پیمایش پس‌ترتیب» (Post-Order Traversal).

پیمایش به‌ترتیب (In-Order Traversal)

در این نوع پیمایش، ابتدا گره فرزند چپ بازدید می‌شود، سپس گره والد و در نهایت گره فرزند راست. فرایند به این صورت است که ابتدا به سمت چپ درخت می‌رویم و به گره‌های پایینی می‌رسیم، سپس به گره والد بازمی‌گردیم و در نهایت به سمت راست می‌رویم. این نوع پیمایش به‌ویژه در درخت‌های جستجوی دودویی (Binary Search Trees) کاربرد دارد، زیرا گره‌ها را به ترتیب صعودی نمایش می‌دهد. به عنوان مثال، اگر درختی داشته باشیم که شامل گره‌های A، B، C، D و E باشد، پیمایش به‌ترتیب آن‌ها را به ترتیب D، B، E، A و C نمایش خواهد داد.

پیمایش پیش‌ترتیب (Pre-Order Traversal)

در این نوع پیمایش، ابتدا گره والد بازدید می‌شود و سپس به ترتیب گره‌های فرزند چپ و راست بازدید می‌شوند. فرایند این پیمایش شامل سه مرحله است: ابتدا از گره والد بازدید می‌کنیم، سپس به سمت چپ می‌رویم و بعد به سمت راست. این نوع پیمایش به ویژه برای ساختارهایی مفید است که نیاز به ذخیره‌سازی یا کپی‌سازی درخت به ترتیب والد-فرزند دارند. به عنوان مثال، اگر درختی شامل گره‌های A، B، C، D و E داشته باشیم، پیمایش پیش‌ترتیب آن‌ها را به ترتیب A، B، D، E و C نمایش می‌دهد.

پیمایش پس‌ترتیب (Post-Order Traversal)

در این نوع پیمایش، ابتدا گره‌های فرزند چپ و راست بازدید می‌شوند و سپس گره والد بازدید می‌شود. فرایند این پیمایش به این صورت است که ابتدا به سمت چپ می‌رویم، سپس به سمت راست و در نهایت گره والد را بازدید می‌کنیم. این نوع پیمایش معمولاً در مواقعی که نیاز به انجام عملیاتی بر روی فرزندان قبل از والد داریم، مانند حذف گره‌ها یا آزادسازی منابع، به کار می‌رود. به عنوان مثال، اگر درختی شامل گره‌های A، B، C، D و E باشد، پیمایش پس‌ترتیب آن‌ها را به ترتیب D، E، B، C و A نمایش می‌دهد.

هر یک از این روش‌های پیمایش درخت، ویژگی‌ها و کاربردهای خاص خود را دارند و بسته به نیاز برنامه‌نویسی یا تحلیل داده‌ها، انتخاب می‌شوند.

پاورپوینت پیمایش درخت در ساختمان داده

کلیک کنید

نتیجه گیری

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

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

پاورپوینت های آماده ساختمان داده

پاورپوینت های آماده ساختمان داده

کلیک کنید