درخت در ساختمان داده ها

درخت در ساختمان داده ها

اسلاید 1: آشنايي با درختدرخت هاي دودوييپيمايش درختانهرمجنگلفصل پنجم : درختاهداف1

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

اسلاید 3: مفهوم درختدرخت مجموعه محدودي از يک يا چند گره به صورت زير مي باشد : داراي گره خاصي به نام ريشه باشد. بقيه گره ها به n ≥ 0 مجموعه مجزا تقسيم شده که هر يک از اين مجموعه ها خود يک درخت هستند. زير درختان ريشه ناميده مي شوند.3

اسلاید 4: به عنصر حاوي اطلاعات و انشعابات به ديگر عناصر، گره اطلاق مي شود.تعداد زير درختهاي يك گره، درجه آن ناميده ميشودگره اي كه درجه آن صفر باشد، برگ يا گره پاياني ناميده ميشود و در مقابل بقيه گره‌ها گره هاي غيرپاياني ناميده ميشوند.گره ريشه را در هر زير درخت گره پدر(والد) و به گره‌هاي متصل شده به آن گره فرزند ميگويندفرزنداني كه پدر يكسان دارند برادر (يا همزاد) ناميده ميشوندتعريف4

اسلاید 5: مثالي از يک درختA والد B ، C، D است . B ، C، D همزادند.ACGDBEHIJMFريشه درختLKهمزاددرجه A = 3شکل1-55

اسلاید 6: اجداد گره : اجداد يک گره ، گره هايي هستند که در مسير طي شده از ريشه تا آن گره وجود دارند.سطح گره : سطح يک گره بدين صورت تعريف مي شود که ريشه در سطح يک قرار مي گيرد. براي تمامي گره هاي بعدي ، سطح گره برابر است با سطح والد به اضافه يک .ارتفاع درخت : ارتفاع يا عمق يک درخت به بيشترين سطح گره هاي آن درخت گفته مي شود.اصطلاحات درخت ها6

اسلاید 7: نمايش ليستيک راه نمايش درخت ، استفاده از ليست است .شکل 1-5 را مي توان به صورت زير نشان داد : (A(B(E(K ،L)،F)،C(G)،D(H(M)،I،J)))ACGDBEHIJMFLK7

اسلاید 8: اگر بخواهيم براي نگهداري يك درخت ساختمان داده اي مانند نمايش معمول (هر گره آدرس گره هاي فرزند خود را داشته باشد) تعريف كنيم مشكل زير بوجود مي‌آيد:درجه تمام درختها يكي نميباشد لذا مجبور خواهيم شد براي هر گره تعداد متغيري از اشاره گرها داشته باشيم. با اين وجود، نوشتن الگوريتم براي گره‌هايي كه طول متغير دارند دشوار خواهد شدبراي حل مشكل بايد از گره هايي با طول ثابت استفاده كنيم.8

اسلاید 9: استفاده از گره با طول ثابتاگر بيشترين درجه درخت k باشد بنابراين هر گره بايد توانايي نگهداري k اشاره گر را داشته باشد و ساختمان داده اي به شكل زير بايد تعريف كنيم.9

اسلاید 10: اگر T درختي از درجه k با n گره باشد و هر گره آن مانند شكل قبل طول ثابتي داشته باشد آنگاه n(k-1)+1 از nk فيلد بچه آن (اشاره گرهاي به فرزند) برابر 0‌ (NULL) است.اثبات:از آنجا كه هر فيلد بچه غير صفر به يك گره اشاره ميكند و براي هر گره غير از ريشه يك اشاره گر وجود دارد از اينرو تعداد فيلدهاي بچه غيرصفر براي درختي با n گره دقيقاً برابر n-1 است. تعداد كل فيلدهاي بچه براي درختي با n گره از درجه k برابر nk ميباشد. لذا:تعداد اشاره گرهاي بچه NULL : nk-(n-1)=n(k-1)+1 قضيه10

اسلاید 11: براي درختان دو نمايش خاص كه از گره‌هايي با طول ثابت استفاده ميكند ارائه ميكنيم.الف) نمايش درخت بصورت بچه چپ-همزاد راستب) نمايش درخت بصورت يك درخت درجه 2.11

اسلاید 12: براي نمايش درختان دودويي ، دقيقا نياز به دو اتصال يا اشاره گر به ازاي هر گره است.نمايش دودويي يک درختDataDataright siblingleft child

اسلاید 13: بصورت بچه چپ-همزاد راستACGDBEHIJMFLKA0BCD0EF00K0L00G00HI0J00M0013

اسلاید 14: بصورت درخت درجه 2ACGDBEHIJMFLKA0BCD0EF00K0L00G00HI0J00M0014

اسلاید 15: 152-5 درخت هاي دودويي مشخصه اصلي يک درخت دودويي بدين شکل است که هر گره آن حداکثر دو انشعاب دارد يعني گره هايي که درجه اي بيشتر از دو نداشته باشند. براي درخت هاي دودويي زير درخت سمت چپ و راست با يکديگر متمايز است.يک درخت دودويي يا تهي است يا حاوي مجموعه اي محدود از گره ها شامل يک ريشه و دو زير درخت دودويي است. اين درخت ها زير درخت هاي چپ و راست ناميده مي شوند.تعريف :

اسلاید 16: 2-5 ساختار درخت دودوييstructure Binary_tree (abbreviated BinTree ) is objects : a finite set of nodes either empty or consisting of a root node ، left Binary_tree ، and right Binary_tree. functions :for all bt ، bt1 ، bt2 BinTree ، item elementBinTree Create()Boolean IsEmpty (bt)BinTree MakeBT(bt1 ، item ، bt 2)BinTree Lchild(bt)element Data(bt)BinTree Rchild(bt)16

اسلاید 17: در هيچ درخت عادي صفر گره وجود ندارد ، اما درخت دودويي تهي وجود دارد.در يک درخت دودويي ترتيب فرزندان داراي اهميت بوده در حالي که در درخت عادي به اين صورت نيست.2-5 تفاوت درخت عادي با درخت دودويي17

اسلاید 18: 2-5 خواص درختان دودويي حداکثر تعداد گره ها در سطح i ام يک درخت دودويي 2i-1 است. حداکثر تعداد گره ها در يک درخت دودويي به عمق k ، 2k-1 است.حداکثر تعداد گره ها18

اسلاید 19: 2-5 خواص درختان دودوييبراي هر درخت دودويي غير تهي مانند T ، اگر تعدادگره هاي پاياني و تعداد گره هاي درجه 2 باشد ، آنگاه خواهيم داشت :رابطه بين تعداد گره هاي برگ و گره هاي درجه 219

اسلاید 20: 2-5 خواص درختان دودويييک درخت دودويي پر به عمق k ، يک درخت دودويي پر است مشروط به اينكه 2k-1 گره داشته باشد.يک درخت دودويي با n گره و عمق k کامل است ، اگر و تنها اگر گره هايش مطابق با گره هاي شماره گذاري شده در يک درخت دودويي پر به عمق k باشد.ارتفاع يك درخت دودويي كامل با n گره برابر است

اسلاید 21: 2-5 نمايش درخت دودويينمايش درخت دودويي به دو صورت است :نمايش آرايهنمايش ليست پيوندي21

اسلاید 22: شيوه شماره گذاري ارايه شده در شکل زير ، اولين نمايش يک درخت دودويي در حافظه را مطرح و پيشنهاد مي کند . از آنجايي که گره ها از 1 تا n شماره گذاري شده اند ، يک آرايه يک بعدي مي تواند براي ذخيره سازي گره ها استفاده شود .2-5 نمايش آرايه

اسلاید 23: 2-5 نمايش آرايهACBDFGEIH-0A1B2C3D4E5F6G7H8نمايش آرايه اي درخت دودويي23

اسلاید 24: 2-5 نمايش آرايهاگر يک درخت دودويي کامل با n گره ( يعني عمق ) به ترتيب بالا تعريف شده باشد ، آنگاه براي هر گره با انديس i و ≤ n i 1≤ ، داريم:(1) اگر i≠1 ، آنگاه پدر i در [i/2] است . اگر i=1 ، i ريشه است و پدري نخواهد داشت.(2) اگر2i≤n ، آنگاه فرزند چپ i در 2i است. اگر 2i>n ، آنگاه i فرزند چپ ندارد.(3) اگر 2i+1≤n ، آنگاه فرزند راست i در 2i+1 است. اگر 2i+1>n ، آنگاه i فرزند راست ندارد

اسلاید 25: در بدترين حالت ، يک درخت مورب به عمق k ، به محل و موقعيت نياز دارد که از اين مقدار، فقط k محل اشغال مي شود. 2-5 نمايش آرايه25

اسلاید 26: اگرچه نمايش ترتيبي (آرايه اي) براي درختان دودويي کامل مناسب به نظر مي رسد ، ما براي بسياري از درختان ديگر باعث اتلاف حافظه ميشود به علاوه ، اين روش از نارسايي هاي موجود در نمايش ترتيبي نيز برخوردار است. درج يا حذف گره هاي يک درخت ، مستلزم جابه جايي گره هاست که خود باعث تغيير شماره سطح گره ها مي شود. اين مسايل مي تواند با به کارگيري نمايش پيوندي به آساني حل شود.2- 5 نمايش ليست پيوندي26

اسلاید 27: 2-5 نمايش ليست پيونديبا اين روش هر گره سه فيلد خواهد داشت :left_child ، data ، right_child که در زبان C به شرح زير تعريف مي شوند :typedef struct node *tree_pointer ;typedef struct node {int data ;tree_pointer left_child ، right_child ;};27

اسلاید 28: اعضاي كلاس Expressionclass Tree;class TreeNode{friend class Tree;private:char data; TreeNode *LeftChild; TreeNode *RightChild;};class Tree{public: Tree(); Tree(const Tree& t);private: TreeNode *root;};28

اسلاید 29: 2-5 نمايش ليست پيونديleft_childdataright_childنمايش يک گره درخت دودويي

اسلاید 30: 3-5 پيمايش درخت دودوييبه هنگام پيمايش يک درخت دودويي ، با هر گره و زيردرختانش به طرز مشابهي رفتار کنيم. اگر R ، V ، L به ترتيب حرکت به چپ ، ملاقات کردن يک گره ( براي مثال ، چاپ فيلد داده آن گره) و حرکت به راست باشد، آنگاه شش ترکيب ممکن براي پيمايش يک درخت خواهيم داشت : RLV ، RVL ، VRL ، VLR ، LRV ، LVR 30

اسلاید 31: 3-5 پيمايش درخت دودويياگر تنها حالتي را انتخاب کنيم که ابتدا به سمت چپ و بعد به سمت راست برود ، تنها سه ترکيب VLR ، LRV ، LVR خواهيم داشت. اين سه حالت را با توجه به موقعيت V نسبت به L و R به ترتيب preordcr ، postorder ، inorder مي ناميم.مثال31

اسلاید 32: 3-5 پيمايش درخت دودويي در پيمايش postorder ، يک گره موقعي ملاقات و چاپ مي شود که زيردرختان چپ و راست آن قبلا ملاقات شده باشند. در پيمايش preorder ، يک گره قبل از پيمايش زيردرختان چپ و راست ، ملاقات مي گردد.32

اسلاید 33: 3-5 پيمايش درخت دودوييدرخت زير حاوي يک عبارت رياضي است : A/B*C*D*+E+E**DC/AB12345679108111417191816151312درخت دودويي براي يک عبارت محاسباتي33

اسلاید 34: 3-5 پيمايش Inorderهنگامي که اين پيمايش انتخاب مي شود ، حرکت به سمت پايين به طرف چپ انجام مي شود و اين عمل تا آخرين گره صورت مي گيرد سپس مي توان گره را بازيابي کرد و بعد به سمت راست رفته و به همين ترتيب کار ادامه پيدا مي کند.اين متناظر با شکل infix يک عبارت است.34

اسلاید 35: void inorder (tree_pointer ptr )/* inorder tree traversal */{if (ptr) {inorder ( ptr -> left_child );printf (“ % d” ، ptr -> data );inorder (ptr -> right_child);}}3-5 پيمايش Inorderيک درخت دودويي35

اسلاید 36: 3-5 پيمايش Preorderتابع preorder حاوي دستورات لازم براي شکل دوم پيمايش است.بر اساس اين پيمايش ، گره را ابتدا بازيابي و ملاقات نموده و سپس انشعابات چپ را دنبال و تمام گره ها را بازيابي مي کنيم. اين فرآيند ادامه پيدا مي کند تا به يک گره تهي برسيم. در اين نقطه ، به نزديکترين جدي که داراي يک فرزند راست باشد مراجعه و با اين گره شروع خواهيم نمود.36

اسلاید 37: 3-5 پيمايش Preorder+E**DC/AB12345679108111417191816151312با پيمايش preorder گره هاي درخت زير خروجي به شکل زير خواهند داشت :خروجي+ * * / A B C D Eاين به شکل يک عبارت prefix است.37

اسلاید 38: Vide preorder (tree_pointer ptr )/* preorder tree traversal */{if (ptr) {printf (“ % d” ، ptr -> data );preorder ( ptr -> left_child );preorder (ptr -> right_child);}}3-5 پيمايش Preorder يک درخت دودويي38

اسلاید 39: 3-5 پيمايش postorderاين پيمايش دو فرزند يک گره را قبل از بازيابي آن گره ملاقات و چاپ مي کند. اين مساله بدين مفهوم است که فرزندان يک گره قبل از خود آن گره بازيابي مي گردد.39

اسلاید 40: 3-5 پيمايش postorderخروجي حاصل از پيمايش postorder شکل زير به صورت زير است :+E**DC/AB12345679108111417191816151312خروجيA B/ C* D* E +اين خروجي مانند يک عبارت postfix است.40

اسلاید 41: 3-5 پيمايش inorder غيربازگشتيVoid iter_pointer (tree_pointer node ){int top = -1 ; /* initialize stack */tree_pointer stack [MAX_STACK_SIZE] ;for ( ; ; ) {for (; node ; node = ->left_child)add ( &top ، node ); /* add to stack */node = delete (&top); /*delete from stack */if (! Node) break ; /* empty stack*/printf (“ % d”، node-> data ) ;node = node -> right_child;}}41

اسلاید 42: 3-5 پيمايش inorder غيربازگشتيتحليل inorder2 : فرض کنيد تعداد گره هاي درخت n باشد ، اگر عمل iter_inorder را در نظر بگيريم ، مشاهده مي شود که هر گره درخت فقط يک بار در پشته قرار گرفته و يا از آن خارج مي شود. بنابراين اگر تعداد گره هاي درخت n باشد ، پيچيدگي زمان تابع برابر با O(n) مي باشد. حافظه مورد نياز برابر با عمق درخت است که مساوي با O(n) مي باشد.42

اسلاید 43: 3-5 پيمايش ترتيب سطحيپيمايش هاي inorder ، preorder ، postorder چه به صورت بازگشت پذيري نوشته يا به صورت غيربازگشتي ، همگي نيازمند پشته مي باشند.اين پيمايش ، ترتيب سطحي ، ابتدا ريشه را بازيابي ، سپس فرزند چپ ريشه و به دنبال آن فرزند راست ريشه بازيابي مي گردد. اين شيوه با بازيابي از گره منتهي اليه سمت چپ به سمت راست هر سطح جديد تکرار مي گردد. اين پيمايش از صف استفاده مي کند.43

اسلاید 44: 3-5 پيمايش ترتيب سطحيپيمايش ترتيب سطحي درخت زير به صورت زير است : +E**DC/AB12345679108111417191816151312+ *E *D / C A B44

اسلاید 45: 4-5 اعمال مفيد بر روي درختان دودويي1- کپي کردن درختان دودويي2- تعيين برابري و تساوي دو درخت3- مساله Satisfiability45

اسلاید 46: 5-5 درختان نخي دودوييتعداد اتصالات تهي در يک درخت دودويي بيشتر از تعداد اشاره گرهاي غيرتهي است.در يک درخت دودويي تعداد n + 1 اتصال از کل اتصالات آن يعني ، 2n تهي است. يک راه براي به کارگيري اين اتصالات توسط پرلين و تورنتن پيشنهاد شد. راه حل اين بود که از اتصالات تهي براي ارتباط با ديگر گره هاي يک درخت استفاده شود که در اين صورت درخت را درخت نخي مي نامند.46

اسلاید 47: 5-5 درختان نخي دودوييبراي ايجاد اتصالات نخي از قوانين زير استفاده مي شود : اگر ptr-> left_child تهي باشد ، آن را طوري تغيير مي دهيم که به گره اي که در پيمايش inorder قبل از ptr قرار دارد ، اشاره کند. اگر ptr-> right_child تهي باشد ، آن را طوري تغيير مي دهيم که به گره اي که در پيمايش inorder بعد از ptr قرار دارد ، اشاره کند.47

اسلاید 48: 5-5 درختان نخي دودوييهنگامي که درختي را در حافظه نمايش مي دهيم ، بايستي بتوانيم بين اتصالات نخي و واقعي تفاوتي قايل شويم. اين کار را با افزودن دو فيلد اضافي به هر گره انجام مي دهيم که آنها را right_thread ، left_thread مي ناميم.48

اسلاید 49: 5-5 درختان نخي دودوييACBDFGEIHدرخت نخي متناظرACBDFGEIHاتصالات نخي49

اسلاید 50: 5-5 پيمايش inorder يک درخت نخي دودوييبراي هر گره مانند ptr ، در يک درخت دودويي ، چنانچه ptr->right_thread = TRUE باشد ، طبق تعريف گره بعدي ptr در پيمايش inorder ، ptr->right_child مي باشد . در غير اين صورت گره بعدي ptr، با پايين رفتن روي مسير فرزندان چپ ptr از طرف فرزند سمت راست ptr تا وقتي که به گره اي با وضعيت left_thread = TRUE برسيم ، تعيين مي شود .50

اسلاید 51: تابع insucc بدون استفاده از پشته ، گره بعدي در پيمايش inorder را در يک درخت نخي دودويي پيدا مي کند.براي پيمايش inorder مي توانيم با فراخواني مکرر insucc تمام گره ها را بازيابي کنيم .5-5 پيمايش inorder يک درخت نخي دودويي51

اسلاید 52: 5-5 پيمايش inorder يک درخت نخي دودوييthreaded_pointer insucc (threaded_pointer tree){/* find the inorder sucassor of tree in a threaded binary tree */threaded_pointer temp ;temp = tree -> right_child ;if (! Tree -> right_thread)while (! temp -> left_thread)temp = temp -> left_child ;return temp ;}تابع insucc :پيدا نمودن گره بعد ، يک گره خاص در پيمايش inorder52

اسلاید 53: 5-5 پيمايش inorder يک درخت نخي دودوييVoid tinorder (threaded_pointer tree){/* traverse the threaded binary tree inorder */threaded_pointer temp = tree ;for ( ; ; ) {temp = insucc (temp) ;if (temp = tree ) break ;printf (“ % 3c” ، temp -> data ) ;}}53

اسلاید 54: نحوه اضافه كردن يك گره جديد به درخت نخ كشي شده را بررسي نماييد.براي ارائه روش از نرم افزار power point براي انيميشن دادن به كار استفاده نماييد.بايد الگوريتم كار با دقت آورده شده و ميتوانيد از شبه كد نيز استفاده كنيد.تمرين54

اسلاید 55: 6-5 نوع داده مجرد ( (ADTهرمmax tree درختي است که مقدار کليد هر گره آن کمتر از مقادير کليدهاي فرزندانش نباشد.max heap يک درخت دودويي کامل است که يک max tree نيز مي باشد.min tree درختي است که مقدار کليد هر گره آن بيشتر از مقادير کليدهاي فرزندانش نباشد.min heap يک درخت دودويي کامل است که در واقع يک min tree مي باشد.55

اسلاید 56: 6-5 مثال از max heap و min heap14712108[1][2][4] [5][3]6[6]247108[1][2][4] [5][3]6[6]9365[1][2][4][3]10832050[1][2][4][3]مثال از max heapمثال از min heap56

اسلاید 57: ايجاد يک هرم(heap) تهيجايگذاري عنصر جديد به هرم (heap) حذف بزرگترين عنصر از هرم (heap) 6-5 اعمال اساسي بر روي heap57

اسلاید 58: 6-5 صف اولويتغالبا هرم ها براي پياده سازي صف اولويت ها استفاده مي شوند. در صف اولويت ها عنصري که داراي بالاترين ( يا پايين ترين ) اولويت هست ، حذف مي شود. آرايه ساده ترين نمايش براي يک صف اولويت مي باشد.58

اسلاید 59: 6-5 نمايش هاي صف اولويتDeletionInsertionRepresentationΘ(n)Θ(1)Unordered arrayΘ(nΘ(1)Unordered linked listΘ(1)O(n)Stored arrayΘ(1)O(n)Stored linked listMax heap59

اسلاید 60: 6-5 درج عناصر به داخل يک Max Heap2021514[1][2][4][3]10[5]الف - درخت heap قبل از درجب - محل اوليه گره جديددرج عنصر جديداضافه کردن گره جديد در هر موقعيت ديگري ،تعريف heap را نقض مي کند زيرا نتيجه يک درخت دودويي کامل نخواهد بود.2021514[1][2][4][3]10[5]60

اسلاید 61: 6-5 درج عنصر به يک Max heap61

اسلاید 62: از آنجا که heap يک درخت کامل با n عنصر مي باشد ، داراي ارتفاع log2(n) مي باشد. اين بدين معني مي باشد که حلقه while به ميزان log2(n) تکرار شود. بنابراين پيچيدگي تابع درج برابر log2(n) مي باشد.6-5 تحليل تابع insert_max_heap62

اسلاید 63: 6-5 حذف عنصري از Max Heap2021514[1][2][4][3]10[5]هنگامي که عنصري از max heap حذف مي شود ، آن را از ريشه درخت heap مي گيريم.21514[1][2][4][3][5]20 removedحذف يک عنصر از max heap63

اسلاید 64: 6-5 حذف عنصري از Max Heap64

اسلاید 65: پيچيدگي حذف برابرمي باشد.زمان حذف يک عنصر دلخواه از درخت heap با n عنصر ، برابر O(n) مي باشد. 6-5 تحليل تابع delete_max_heap65

اسلاید 66: 7-5 درختان جستجوي دودويييک درخت جستجوي يک درخت دودويي است که ممکن است تهي باشد. اگر درخت تهي نباشد خصوصيات زير را برآورده مي کند : هر عنصر داراي يک کليد است و دو عنصر نبايد داراي کليد يکسان باشند ، در واقع کليدها منحصر به فردند. کليدهاي واقع در زيردرخت غيرتهي چپ بايد کمتر از مقدار کليد واقع در ريشه زيردرخت راست باشد. کليدهاي واقع در زيردرخت غيرتهي راست بايد بزرگتر از مقدار کليد واقع در ريشه زيردرخت چپ باشد.زيردرختان چپ و راست نيز خود درختان جستجوي دودويي ميباشند.66

اسلاید 67: 7-5 درختان جستجوي دودويي304052مثال67

اسلاید 68: class BSTNode{friend class BST;private:BSTNode *left;int key;BSTNode *right;public:int GetKey();};class BST{public:BST();bool Insert(int key);BSTNode* Search(int key);void DeleteNode(BSTNode* pNode,bool bRight);private:BSTNode *root;};در كلاس نوشته شده فرض شده كه هر گره تنها يك مقدار كليد دارد ولي در طراحي پيشرفته تر ميتوان از قالبها استفاده نمود. 68

اسلاید 69: 7-5 جستجوي يک درخت دودوييفرض کنيد خواسته باشيم دنبال عنصري با کليد key بگرديم. ابتدا از ريشه (root) شروع مي کنيم ، اگر ريشه تهي باشد ، درخت جستجو فاقد هر عنصري بوده و جستجو ناموفق خواهد بود. در غير اين صورت keyرا با با مقدار کليد ريشه مقايسه کرده : اگر key کمتر از مقدار کليد ريشه باشد ، هيچ عنصري در زيردرخت راست وجود ندارد که داراي کليدي برابر key باشد ، بنابراين زيردرخت چپ ريشه را جستجو مي کنيم. اگر key بزرگتر از مقدار کليد ريشه باشد ، زيردرخت راست را جستجو مي کنيم.69

اسلاید 70: 7-5 تحليل searchاگر h ارتفاع يا عمق يک درخت جستجوي دودويي باشد ، عمل جستجو را در مدت O(h) انجام مي شود.70

اسلاید 71: BSTNode* BST::Search(int key){ return Search(root , key);}BSTNode* BST::Search(BSTNode* p, int key){if (!p)return 0; if(key ==p→key)return p;if(key <p→key)return Search(p→left , key);elsereturn Search(p→right , key);}الگوريتم جستجو در BST بصورت بازگشتي71

اسلاید 72: BSTNode* BST::Search(int key){BSTNode *p=root;while(p!=NULL){if(key < p→key)p = p→left;else if(key > p→key)p = p→right;else return p;}return 0;}الگوريتم جستجو در BST بصورت غير بازگشتي72

اسلاید 73: 7-5 درج عنصري به داخل درخت جستجوي دودوييبراي درج عنصر جديدي به نام key ، ابتدا بايد مشخص نمود که آيا کليد با عناصر موجود متفاوت است يا خير. براي انجام اين کار بايد درخت را جستجو کرد، اگرجستجو ناموفق باشد ، عنصر را در محلي که جستجو خاتمه پيدا نموده است ، درج مي کنيم.73

اسلاید 74: 7-5 درج عنصري به داخل درخت جتجوي دودويي304052304052803040523580جايگذاري 80جايگذاري 35مثال74

اسلاید 75: 7-5 تحليل insert_nodeزمان لازم براي جستجوي num در يک درخت برابر O(h) مي باشد به نحوي که h برابر با عمق يا ارتفاع درخت است. بقيه الگوريتم نياز به زمان Θ(1) دارد. بنابراين زمان کل مورد نياز insert_node برابر با Θ(h) مي باشد. 75

اسلاید 76: bool BST::Insert(int key){BSTNode *p=root;BSTNode *q;while(p!=NULL){q = p;if(key < p→key)p = p→left;else if(key > p→key)p = p→right;else return false; //Error for duplicate key}p = new BSTNode (key);if (!root){root = p;return true;}if(key < q→key)q→left = p;elseq→right = p;return true;}76

اسلاید 77: 7-5 حذف عنصري از درخت جستجوي دودوييبراي حذف 35 از درخت زير بايد فيلد فرزند چپ والد اين گروه را برابر NULL قرار داده و گره را آزاد نمود :304052358077

اسلاید 78: زماني که يک گره برگ با دو فرزند حذف مي شوند ، گره را با بزرگترين عنصر در زير درخت چپ و يا کوچکترين عنصر در زيردرخت راست آن گره جايگزين و تعويض کرد.عمل حذف در زمان O(h) انجام مي گيرد ، به نحوي که h عمق درخت مي باشد.7-5 حذف عنصري از درخت جستجوي دودويي78

اسلاید 79: void DeleteNode (BSTNode* pNode,bool bRight){ BSTNode *CurNode = pNode→left; if (bRight) CurNode = pNode→right; if( !CurNode→right && !CurNode→ left) { delete CurNode; return; } if(CurNode→right && !CurNode→ left) { if (bRight) pNode→right = CurNode→right; else pNode→left = CurNode→right; delete CurNode; return; } if(!CurNode→right && CurNode→ left) { if (bRight) pNode→right = CurNode→left; else pNode→left = CurNode→left; delete CurNode; return; } if(CurNode→right && CurNode→ left) { BSTNode *tmp = CurNode→left; pNode = CurNode; bRight = false; while (tmp→right) {pNode = tmp; bRight = true;tmp = tmp→right; } CurNode→key = tmp→key; DeleteNode(pNode , bRight); }}79

اسلاید 80: 7-5 درختان جستجوي متعادلدرختان جستجو با بيشترين عمق، درختان جستجوي متعادل ناميده مي شوند.درختان جستجوي متعادلي وجود دارند که عمل جستجو ، درج و حذف را در زمان O(h) ممکن مي سازند از جمله درختان red_black ، 2-3 ، AVL 80

اسلاید 81: 8-5 درختان انتخابيفرض کنيد داراي k مجموعه و رشته مرتب شده اي از عناصر هستيم که بايد در يک رشته واحد ادغام شوند. هر دنباله يا ترتيب شامل تعدادي رکورد به ترتيب غيرنزولي و فيلد مشخصي به نام key مي باشد. يک دنباله مرتب اجرا (run) ناميده مي شود. فرض کنيد که n، تعداد رکوردها در k اجرا باشد، عمل ادغام مي تواند با تکرار رکورد با کوچکترين کليد انجام شود. 81

اسلاید 82: 8-5 درختان انتخابي کوچکترين کليد بايد ازبين k امکان موجود پيدا شود و مي تواند رکوردي قبل از هر k اجرا (k-runs) باشد. بهترين روش براي ادغام k اجرا (k-runs) ، نيازمند k-1 مقايسه براي تعيين و انتقال رکورد بعدي به خروجي مي باشد. به ازاي k>2 ، مي توانيم با استفاده از ايده درخت انتخابي ، تعداد مقايسه هاي لازم جهت تعيين کوچکترين عنصر را کاهش دهيم.82

اسلاید 83: 8-5 درختان انتخابييک درخت انتخابي ، يک درخت دودويي است که هر گره آن کوچکتر از دو فرزند خود مي باشد بنابراين ، گره ريشه نشان دهنده کوچکترين گره در درخت مي باشد.83

اسلاید 84: 68698176910620981790[1][2][4][3][5][12][11][10][9][8][6][14][13][15][7]8-5 درختان انتخابيمثال203820301525155011161001101820run1run 2run 3run 4run 5run 8run 7run 6

اسلاید 85: زمان تجديد ساختار درخت برابر مي باشد.زمان لازم براي ادغام تمام n رکورد برابر مي باشد.زمان کل لازم جهت ادغام k اجرا (run) برابر مي باشد.858-5 درختان انتخابي

اسلاید 86: جنگل مجموعه n ≥ 0 درخت مجزا مي باشد.اگر ريشه درخت را حذف کنيم ، آنگاه داراي يک جنگل خواهيم بود.9-5 جنگل ها86

اسلاید 87: براي تبديل اين جنگل به يک درخت دودويي واحد :ابتدا نمايش دودويي هر يک از درختان جنگل را به دست مي آوريمسپس تمام درختان دودويي را از طريق فيلد همزاد گره ريشه به يکديگر متصل مي کنيم.9-5 تبديل جنگل به يک درخت دودويي87

اسلاید 88: 9-5 تبديل جنگل به يک درخت دودوييADBCEFGIHAEBFGIHCDتبديل به درخت دودويي88

اسلاید 89: اگرجنگلي از درختان باشد ، آنگاه درخت دودويي متناظر با اين جنگل يعني B:اگر n=0 باشد ، تهي خواهد بود. داراي ريشه اي برابر با ريشه مي باشد ، داراي زيردرخت چپي برابر با مي باشد، و در نهايت داراي زيردرخت راست مي باشد. 9-5 تبديل جنگل به يک درخت دودويي89

اسلاید 90: 9-5 پيمايش جنگلپيمايش هاي postorder ، inorder ، preorder متناظر درخت دودويي T يک جنگل F داراي يک تناظر طبيعي با پيمايش هاي F مي باشند.90

اسلاید 91: پيمايش preorder مربوط به T معادل با بازيابي گره هاي F در درخت preorder مي باشد:اگر F تهي باشد ، برگرديد. ريشه درخت اول F را بازيابي کنيد. زيردرخت ، درخت اول را به صورت preorder پيمايش کنيد. ساير درختان F را به صورت preorder پيمايش کنيد.9-5 پيمايش جنگل91

اسلاید 92: 9-5 پيمايش جنگلپيمايش inorder مربوط به T معادل گره هاي F در درخت inorder است که به صورت زير تعريف مي شود : اگر F تهي باشد ، برگرديد. ريشه درخت ، درخت اول را به صورت inorder پيمايش کنيد. ريشه درخت اول را بازيابي کنيد. ساير درختان را به صورت inorder پيمايش کنيد. 92

اسلاید 93: 9-5 پيمايش جنگلهيچ گونه معادل طبيعي براي براي پيمايش postorder درخت دودويي متناظر يک جنگل وجود ندارد . پيمايش postorder يک جنگل F را به صورت زير بيان ي کنيم :1) اگر F تهي باشد ، برگرديد.2) زيردرخت ، اولين درخت F را به صورت postorder پيمايش کنيد.3) ساير درختان باقي ماندهF را به صورت postorder پيمايش کنيد. 4) ريشه اولين درختF را بازيابي کنيد93

اسلاید 94: 10-5 نمايش مجموعهده عضو از 0 تا 9 که به سه مجموعه مجزا از هم تفکيک شده باشند ، مي توانند بدين صورت باشند :0867491253مثال94

اسلاید 95: در هر مجموعه بر خلاف معمول که اشاره گرها به از والد به فرزندان در نظر گرفته مي شدند، در اينجا اشاره گرها از فرزندان به والد تنظيم مي شوند و يا در حقيقت گره ها با رابطه پدري اتصال يافته اند.10-5 نمايش مجموعه95

اسلاید 96: 10-5 اعمال روي مجموعه هاحداقل اعمالي که بر روي مجموعه انجام مي شود ، به شرح زير است :اجتماع مجموعه مجزا (union) : اگر دو مجموعه مجزا باشند ، انگاه اجتماع آنها به صورت زير تعريف مي شود :{ همه اعضا به صورت x که x يا عضوباشد يا عضو }2) find(i)( پيداکردن i ) : مجموعه اي که i عضو آن است را پيدا کنيد96

اسلاید 97: 10-5 اعمال روي مجموعه هامثال086749197

اسلاید 98: 10-5 قانون Weighting برايUnion(i, j ) قانون Weighting برايUnion(i,j ) : اگر تعدا گره ها در درخت i کمتر از تعداد گره ها در درخت j باشد ، j را والد i ، در غير اين صورت i را والد j قرار مي دهيم.تعريف98

اسلاید 99: 10-5 پياده سازي قانون Weighting براي پياده سازي قانون Weighting بايد بدانيم که در هر درخت چند گره وجود دارد. اين کار را بدين ترتيب انجام مي دهيم که در ريشه هر درخت يک فيلد count قرار مي دهيم. اگر i يک گره ريشه باشد ، آنگاه در count[i] تعداد گره هاي آن درخت خواهد بود. Count به صورت يک عدد منفي در فيلد parent گذاشته مي شود. زماني که قانون Weightingرا بيان مي کنيم ، عمل اجتماع به اين صورت را union2 مي ناميم.99

اسلاید 100: 10-5 مجموعه هااصل موضوعي : فرض کنيد T يک درخت با n گره باشد که توسط union2 ايجاد شده باشد ، در اين صورت هيچ گرهي در T ، سطحي بيشتر از نخواهد داشت. اگر در يک درخت n عضو وجود داشته باشد ، بيشترين زمان براي يافتن يک عضو به صورت خواهد بود.اگر ترکيبي از n-1 عمل union و m عملfind داشته باشيم ، در بدترين حالت ممکن ، زمان به صورت درمي آيد. تعريف ( قانون تخريب ) : اگر j گرهي روي مسير از i تا ريشه خود باشد ، آنگاه j را فرزند ريشه قرار دهيد.100

اسلاید 101: 11-5 شمارش درختان دودوييتعداد درختان دودويي مجزا :تعداد درختان دودويي با n گره ، تعداد جايگشت هاي از 1 تا n با استفاده از يک پشته و بالاخره تعداد راههاي ضرب n+1 ماتريس ، باهم مساوي اند.101

اسلاید 102: 11-5 تعداد درختان دودويي مجزابراي به دست آوردن تعداد درختان مجزا با n گره از تابع زير استفاده مي کنيم :تابع فوق توليدکننده تعداد درختان دودويي است.کهبرابر است با : در نتيجه داريم :102