ساختمان داده درخت برای نمايش داده‌های سلسله ‌مراتبی به ‌كار می ‌رود و چون شبيه درخت رسم می شود ساختار درختی نامگذاری شده است. البته ساختار درختی در مقايسه با درخت واقعی معمولا به صورت وارونه رسم می شود، يعنی ريشه درخت در بالا و برگ های آن در پائين قرار می گيرند.

به طور كلي يک درخت مجموعه ای از گره هاست که از طريق پيوندهايی با هم در رابطه هستند. هر گره دارای داده مرتبط و مجموعه ای از گره های ديگر است.

در نظريه گراف يک درخت يک گراف متصل بدون دور است.

گره

داده ها دردرخت در ساختاری به نام گره (node) قرار دارند. هر گره حاوی اطلاعات و پيوند هايی به ديگر گره های درخت است.

شاخه

خطوطی که گره ها را در درخت به هم متصل می کنند شاخه (branche) ناميده می شوند.

والد و فرزند

گره ای که بلافاصله زير يک گره قرار می گيرد فرزند (children) آن گره محسوب می شود. يک گره والد گره ديگر (parent) است اگر بلافاصله بالاتر از آن نزديک تر به ريشه قرار داشته باشد.

گره ای که کليه گره های سطوح پايين را به هم متصل می کند جد (ancestor) ناميده می شود.

ريشه

هر درخت گره خاصی به نام ريشه (root) دارد که کليه گره های ديگر درخت در پايين آن قرار دارند. گره ريشه والدی ندارد. هر درخت تنها شامل يک گره ريشه است.

گره های همزاد

گره های همزاد (Sibling) گره هایی هستند که والد يکسانی دارند. به عبارت ديگر فرزندان يك گره با هم همزاد هستند.

درجه گره

تعداد فرزندان يك گره درجه (degree) آن گره ناميده مي‌شود.

درجه درخت

درجه درخت برابر ماکزيمم درجه گره‌ها در درخت است.

برگ

گره های بدون فرزند گره های پايانی (end-nodes) يا برگ (leaf) ناميده می شوند. درجه گره های برگ صفر است.

سطح

مجموعه گره هایی طول مسير آنها تا ريشه يکسان است را سطح درخت (level) می نامند. اگر ريشه را در سطح يك فرض كنيم برحسب اينكه يك گره نسبت به ريشه در چه رديفی باشد شماره سطح می گيرد.

ارتفاع درخت

ارتفاع (height) درخت برابر با بيشترين سطح گره‌ها در درخت يا سطح دورترين برگ است. ارتفاع درختی که تنها گره ريشه را دارد صفر است.

هر درخت خواص زير را نمايش می دهند:


• دقيقا يک ريشه دارد.
• همه گره ها بجز ريشه دقيقا يک والد دارند.
• تنها يک مسير از بين هردو گره وجود دارد.
• دور وجود ندارد يعنی مسيری وجود ندارد که از يک گره شروع شود و به خود آن ختم شود.
• درختی که دارای n گره است n-1 شاخه دارد.

---

مثال. در درخت زير گره F ريشه است و گره های C، J و B فرزندان ريشه هستند. گره های A، I، K و D برگ های درخت هستند. درجه درخت 3 و ارتفاع آن 4 است.

Tree example

---

درخت دودوئی

احتمالا پرکاربردترين ترين نوع درختی، درخت دودويی (binary tree) است. درخت های دودويی يک پياده سازی خاص از يک درخت m-ary است که در آن m=2 است يا به عبارت ساده تر هر گره حداکثر دو فرزند دارد که فرزند چپ و فرزند راست (يا زيردرخت چپ و زير درخت راست) ناميده می شوند.

ترتيت قرار گرفتن گره ها در درخت دودويی کاملا اختياری نيست. درحقيقت نحوه درج گره های جديد در درخت دودويی ساختار و کاربرد آنرا تعيين می کند.

---

مثال. درخت های زير همگی دودويی هستند.

Binary tree examples

---

انواع درخت دودوئی

درخت دودوئی پر

يک درخت دودويي پر(full binary tree) درختی است که هر گره آن صفر يا دو فرزند دارد.

در درخت دودويی پر کليه برگ ها در يک سطح هستند.

يک درخت دودويي پر به ارتفاع h دارای 2h-1 گره است.

عمق يك درخت دودوئي پر با n گره log2n+1 است.

تعداد گره‌های سطح i ام يك درخت دودوئی پر 2i-1 است.

---

مثال. درخت (c) در شکل فوق يک نمونه درخت دودويی پر است.

---

درخت دودوئی کامل

يک درخت دودويی کامل (complete binary tree) درختی است که همه سطوح آن به جز احتمالا آخرين سطح حداکثر گره ها را دارند و در سطح آخر گره ها از سمت چپ ظاهر می شوند. يعنی اگر ارتفاع درخت h باشد تعداد کل گره ها تا سطح h-1 برابر با 2h-1 است و در سطح آخر اگر گره هايی وجود دارند بايد از چپ به راست اضافه شوند.

---

مثال. درخت (b) در شکل فوق يک نمونه درخت دودويی کامل است.

---

درخت دودويی ميزان

درخت دودويی ميزان (balanced binary tree) درختی است که کليه برگ ها حداکثر يک سطح با هم تفاوت دارند.

---

مثال. در شکل قبل کليه درخت ها به جز درخت (d) ميزان هستند.

---

نمايش درخت دودوئی

نمايش توسط آرايه

يك درخت دودوئی كامل با n گره را می توان در يك آرايه يك بعدی ذخيره كرد. برای اين کار گره های درخت شماره گذاری می شوند. شماره گذاری به ترتيب از بالا به پايين و از چپ به راست انجام می شود و به هر گره شماره ای تعلق می گيرد. سپس گره با شماره i در خانه i ام آرايه قرار می گيرد.

وقتی درخت دودويی در آرايه نمايش داده می شود برای هر گره با انديس i :


• اگر i ≠1 باشد،‌ والد i در i/2 است و اگر i=1 باشد i ريشه است.
• اگر 2i≤n باشد فرزند چپ i در 2i است و اگر 2i+1≤n باشد،‌ فرزند راست i در 2i+1 است.

---

مثال.

Binary tree array

---

نمايش توسط ليست پيوندی

يک درخت دودويی را می توان توسط ليست پيوندی نمايش داد. به اين صورت که برای هر گره درخت يك گره در ليست در نظر گرفته می ‌شود. هر گره يك اشاره‌گر به فرزند چپ و يك اشاره‌گر به فرزند راست دارد.

typedef struct node *TreePionter;
typedef struct node {
char Data;
Treepointer Left,Right;};

---

مثال.

Binary tree linked list

---

پيمايش درخت‌ دودوئی

اغلب می خواهيم کليه گره های درخت را بررسی کنيم. چند روش برای پيمايش وجود دارد که در آنها گره ها می توانند پردازش يا ملاقات شوند. هر روش وقتی روی يک درخت دودويی اجرا می شود ويژگی های مفيدی را در اختيار می گذارد.

سه روش معمول پيمايش درخت های دودويی روش های preorder، postorder و inorder است که در آنها هر گره و فرزندانش به طور بازگشتی ملاقات می شوند. هر سه پيمايش از ريشه درخت شروع می شوند. تفاوت آنها در ترتيب ملاقات گره و فرزندانش است. در روش preorder ابتدا گره ملاقات شود سپس فرزندانش. در روش postorder ابتدا فرزندان سپس خود گره ملاقات می شود. در روش inorder گره مابين فرزندان چپ و راست خود ملاقات می شود.

پيمايش Preorder

در روش preorder محتوای گره ريشه قبل از فرزند چپ و راست ملاقات می شود. الگوريتم بازگشتی پيمايش preorder به صورت زير است:


1. پردازش ريشه
2. پيمايش زيردرخت چپ به روش preorder
3. پيمايش زيردرخت راست به روش preorder


تابع زير با توجه به الگوريتم فوق پياده سازی شده است:

void Preorder(TreePointer T){
If (T!=NULL) {
Visit(T->Data);
Preorder(T->Left);
Preorder(T->Right);
}}


پيمايش از گره جاری T شروع می شود سپس فرزند چپ و بعد فرزند راست آن ملاقات می شود. Visit برای نمايش يا پردازش مقدار گره است و بستگی به هدف از پيمايش می تواند بسادگی دستور نمايش محتوای گره باشد. تابع با فراخوانی گره ريشه آغاز می شود.

---

مثال. ترتيب ملاقات گره ها به روش Preorder.

Preorder Traversal

---

پيمايش Inorder

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


1.پيمايش زيردرخت چپ به روش inorder
2.پردازش ريشه
3.پيمايش زيردرخت راست به روش inorder


تابع زير مشابه تابع Preorder است با اين تفاوت که ترتيب ملاقات گره تغيير کرده است:

void Inorder(TreePointer T){
If (T!=NULL) {
Inorder(T->Left);
Visit(T->Data);
Inorder(T->Right);
}}

---

مثال. ترتيب ملاقات گره ها به روش Inorder.

Inorder Traversal

---

پيمايش Postorder

پيمايش postorder ابتدا محتوای زيردرخت چپ و سپس زيردرخت راست و در نهايت گره ريشه را ملاقات می کند. الگوريتم بازگشتی پيمايش postorder به صورت زير است:


1.پيمايش زيردرخت چپ به روش Postorder
2.پيمايش زيردرخت راست به روش Postorder
3. پردازش ريشه


تابع زير با توجه به الگوريتم فوق پياده سازی شده است:

void Postorder(TreePointer T){
If (T!=NULL) {
Postorder(T->Left);
Postorder(T->Right);
Visit(T->Data);
}}

---

مثال. ترتيب ملاقات گره ها به روش Postorder.

Postorder Traversal

---

پيمايش اول سطح

پيمايش اول سطح (breadth-first order) مشابه جستجوی اول سطح در گراف است و ابتدا سعی می کند نزديک ترين گره به ريشه را ملاقات کند. پيمايش از سطح اول درخت آغاز شده، هر بار يك سطح از چپ به راست به طور كامل پيمايش می ‌شود.

---

مثال. پيمايش های فوق روی درخت زير انجام شده است:

Binary Tree Traversal

Pre Order : FCADJHIK
In Order : ACDFHIJK
Post Order : ADCIHKJF
Breadth First Order : FCJADHKI

---

درخت جستجوی دودوئی

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

يک درخت جستجوی دودويی (binary search tree) يا BST نوع خاصی از درخت دودويی است که اگر تهی نباشد خواص زير را دارا است:


• هر گره يك مقدار منحصر بفرد دارد.
• کليه مقادير فرزندان زيردرخت چپ هر گره از مقدار خود گره کوچکتر هستند.
• کليه مقادير فرزندان زيردرخت راست هر گره از مقدار خود گره بزرگتر هستند.

---

مثال. درخت های زير هر يک BST هستند.

Binary Search Tree

---

جستجو در BST

جستجوی يک مقدار در BST از گره ريشه شروع می شود. آرگومان جستجو با مقدار گره مقايسه می شود. اگر يکسان باشند داده مورد نظر پيدا شده است در غيراينصورت اگر داده از مقدار گره کوچکتر باشد جستجو از زيردرخت چپ و اگر بزرگتر باشد جستجو از زيردرخت راست گره ادامه پيدا می کند.

به طور خلاصه الگوريتم جستجوی BST به صورت زير بيان می شود. Item داده موردنظر است که در BST جستجو می شود. الگوريتم مقدار تهی يا گره ای که دنبالش هستيم را بر می گرداند.

Search ( TreePointer T, DataType Item )
Begin
If (T = null) Then return null {tree is empty}
Else If (Item = T.Data ) Then return T {item found}
Else If (Item < T. Data and T.Left !=NULL ) Then Search(T.Left, ِData)
Else If (Item > T.Data and T.Right !=NULL ) Then Search (T.Right, Data)
End If
End

---

مثال. فرض کنيد می خواهيم عدد 10 را در درخت شکل (b) مثال قبل جستجو کنيم. جستجو از ريشه شروع می شود. عدد 7 در ريشه است که کمتر از 10 است. بنابراين اگر 10 وجود داشته باشد بايد در زيردرخت راست ريشه باشد. پس جستجو را از گره 11 ادامه می دهيم. در حالت 10 از عدد 11 کمتر است بنابراين اگر 10 در درخت باشد بايد در زيردرخت چپ گره 11 باشد. به سمت چپ گره 11 حرکت می کنيم که گره 10 است و گره ای که دنبالش می گشتيم را پيدا کرديم.

ممکن است که اگر گره ای که به دنبالش هستيم در درخت موجود نباشد. برای نمونه اگر بدنبال عدد 9 هستيم ابتدا به همان طريق بالا عمل می کنيم. وقتی به گره 10 می رسيم بايد جستجو را از زيردرخت چپ ادامه دهيم ولی گره 10 فرزند چپ ندارد بنابراين 9 در درخت وجود ندارد.

---

با دقت در الگوريتم جستجو می توان مشاهده کرد که درهرمرحله تعداد گره هايی که بايد بررسی شوند نصف می شوند. بنابراين چنين زمان اجرای الگوريتم log2 n می شود. البته زمان جستجو به توپولوژی درخت بستگی دارد و در بهترين حالت O(log n) است، در بدترين حالت O(n) می شود.

اگر يک BST به روش InOrder پيمايش شود مقادير گره‌های درخت به صورت مرتب بدست می آيد. زمان اجرای پيمايش روی درخت O(n) است.

---

درج در BST

درج يک گره جديد در BST در دو مرحله انجام می گيرد. ابتدا داده جديد در BST طبق الگوريتمی که ذکر شد جستجو می شود سپس در محل خاتمه جستجو گره جديد اضافه می شود.

با فرض اينکه داده تکراری در درخت مجاز نيست، هنگام درج گره جديد دو شرط بايد مدنظر باشد:


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


اگر زيربرنامه جستجو متوجه شود که گره جديد قبلا در BST وجود دارد پايان می يابد و دوباره آنرا درج نمی کند.

گره جديد به نحوی بايد به درخت اضافه شود که BST خواص خود را حفظ کند.

گره جديد هميشه به صورت يک برگ اضافه می شود. بنابراين ترتيب درج روی توپولوژی درخت تاثير می گذارد.

زمان اجرای الگوريتم درج مشابه الگوريتم جستجو است.

---

مثال. مراحلی که بايد طی شود تا گره 62 به BST اضافه شود در شکل های زير نشان داده شده است.

Insert into BST

---

حذف از BST

حذف يک گره از BST نسبتا دشوارتر از درج است. زيرا وقتی گره ای حذف می شود که دارای فرزند است بايد گره ديگری انتخاب شود تا جايگزين گره حذف شده شود. اگر اين انتخاب درست انجام نشود خواص BST نقض می شود.

گره ای که بايد حذف شود ابتدا در BST جستجو می شود سپس به نحوی جايگزين می شود خواص درخت حفظ شود. چند حالت برای جايگزين کرده گره وجود دارد:

حالت 1. گره که بايد حذف شود برگ باشد و فرزندی نداشته باشد. در اين حالت حذف به سادگی انجام می پذيرد و کافی است اشاره گر والد برابر تهی شود. برای مثال در شکل گره 25 که حذف می شود فرزندی ندارد.

Delete from BST Case 1

حالت 2. گره ای که بايد حذف شود تنها دارای يک فرزند چپ است که می تواند جايگزين آن شود. برای مثال فرض کنيد بخواهيم گره 50 را حذف کنيم. چون 50 فرزند راستی ندارد 20 با آن جايگزين می شود.

Delete from BST Case 2

حالت 3. فرزند راست گره ای که بايد حذف شود فرزند چپی ندارد بنابراين فرزند راست گره جايگزين آن می شود. برای مثال اگر بخواهيم گره 150 را حذف کنيم چون فرزند راست آن فرزند چپی ندارد فرزند راستش يعنی 175 جايگزين می شود.

Delete from BST Case 3

حالت 4. فرزند راست گره ای که بايد حذف شود فرزند چپ دارد. در اين حالت چپ ترين فرزند راست گره جايگزين آن می شود. يعنی کوچکترين مقدار زير درخت راست گره. برای مثال اگر گره 50 را در شکل زير حذف کنيم چپ ترين فرزند آن يعنی 66 را انتخاب کرده و جايگزين می کنيم.

Delete from BST Case 4

در هر BST کوچکترين مقدار در سمت چپ ترين گره و بزرگترين مقدار در سمت راست ترين گره وجود دارد.

اولين مرحله در حذف گره پيدا کردن محل گره ای است که می خواهيم حذف کنيم که توسط الگوريتم جستجو که قبلا توضيح داده شد انجام می گيرد. بنابراين زمان حذف همان زمان O(log n) در حالت متوسط و O(n) در بدترين حالت است.

معايب BST

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

---

درخت Heap

heap يک ساختمان داده درختی که خواص ويژه ای را داراست.

heap را می توان به صورت زير تعريف کرد:


• يک max meap يك درخت دودوئي كامل است كه بزرگ هم باشد. در max heap بزرگترين مقدار هميشه در ريشه قرار می گيرد.
• يک min meap يك درخت دودوئي كامل است كه كوچك هم باشد. در min heap کوچکترين مقدار در ريشه قرار می گيرد.


يك درخت بزرگ (max tree) درختی است كه مقادير كليد هر گره بزرگتر از مقادير فرزندانش باشد. يعنی اگر B فرزند A است آنگاه key(A) key( است.

يك درخت كوچك (min tree) درختی است كه مقادير كليد هر گره كوچكتر از مقادير فرزندانش باشد. يعنی اگر B فرزند A است آنگاه key(A) key( است.

---

مثال. در شکل زير درخت (b) يک max heap است. درخت (a) يک درخت بزرگ است ولی max heap نيست چون يک درخت دودويی کامل نيست.

Heap Example

مثال. در شکل زير درخت (b) يک min heap است. درخت (a) يک درخت کوچک است ولی min heap نيست چون يک درخت دودويی کامل نيست.

Heap Example

---

درج در Heap

يک گره جديد در heap در محلی اضافه می شود که درخت دودوئی کامل باقی بماند. پس از درج درخت تنظيم می شود تا خواص heap حفظ شود. برای مثال اگر max heap باشد و اگر مقدار کليد گره جديد از والدش بيشتر باشد جای آن با والد عوض می شود. اين عمل ممکن است تا ريشه ادامه پيدا کند.

---

مثال. در درخت زير گره جديد 9 به max heap اضافه شده است. پس از درج heap تنظيم می شود و جای 9 ابتدا با گره 3 و سپس با 5 جابه جا می شود.

Insert into max heap

---

حذف از Heap

در Heap حذف هميشه از ريشه صورت می گيرد. بعد از حذف ريشه، آخرين گره درخت جایگزين ريشه می شود. سپس درخت تنظيم می شود تا خواص heap را حفظ کند.

---

مثال. در max heap شکل زير گره 15 که در ريشه قرار دارد حذف می شود. گره 1 که سمت چپ ترين گره درسطح آخر درخت است جايگزين ريشه می شود. سپس درخت تنظيم می شود تا به صورت max heap در بيايد. ابتدا گره 1 با 11 و سپس با 10 جا به جا می شود.

Delete from max heap

---

زمان اجرای عمليات حذف و درج در O(log n) heap است.

---

کاربردهای Heap

در maxh heap بزرگترين مقدار هميشه در ريشه است . در min heap کوچکترين مقدار هميشه در ريشه قرار می گيرد. به خاطر همين ويژگی heap برای پياده سازی صف‌های الويت (priority queues) بسيار مناسب است. در صف الويت هر عنصر با الويت دلخواه را مي‌توان اضافه كرد اما عنصر ماکزيمم يا مينيمم هميشه ابتدا از صف حذف می شود.

Heap ها در الگوريتم مرتب سازی heapsort هم استفاده می شوند.