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

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

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

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

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

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

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

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

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

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

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

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

در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما این دو از نظر مقدار حافظه بسیار متفاوت هستند. در درخت هر عضو B بچه دارد و در نتیجه هر راس حافظه‌ای از مرتبه B دارد. اما در فرکتال هر عضو دارای ${\displaystyle {\sqrt {B}}}$ فرزند و ${\displaystyle {\sqrt {B}}}$ مقدار است و در نتیجه مرتبه حافظه مورد نیاز هر راس ${\displaystyle {\sqrt {B}}}$ است. از طرفی اگر N مقدار را در درخت و فرکتال ذخیره کنیم، درخت دارای N راس و فرکتال دارای ${\displaystyle {\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.

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