درختان

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

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

صفحه 3:
مفهوم درخت درخت مجموعه محدودی از یک یا چند گره به صورت زیر می باشد : = دارای گره خاصی به نام ريشه باشد. . بقیه گره هابه 0 < 1 مجموعه مجز#-1,۰۰ تقسیم شده که يقي ِ ؟ ۳ 7 هر یک از اين مجموعه ها خود یک درخت هشتندی1 زير درختان ريشه نامیده می شوند. د ص2 

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

صفحه 5:
دالا ۰6,0 3لست ۰0۰2 33 همزادند 

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

صفحه 7:
یک راه نمایش درخت , استفاده از لیست است . شکل ۵-۱ را می توان به صورت زیر نشان داد : (AGEKK L)F).C(G)D(HA™) Zy))) 

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

صفحه 9:
استفاده از گره با طول ثابت " اگر بیشترین درجه درخت ) باشد بنابراین هر گره باید توانایی نگهداری ‏ اشاره گر را داشته باشد و ساختمان داده ای به شکل زير بايد تعريف كنيم. data link 1 link 2 5 Link k د _ 

صفحه 10:
* اگر ۲ درختی از درجه ‏ با ۷۱ گره باشد و هر گره آن مانند شکل قبل طول ثابتی داشته باشد آنگاه 1 +(۱)۲-1 از ۲۱۸ فیلد بچه آن (اشاره گرهای به فرزند) برابر » (االالا) است. * اثبات: * از آنجا که هر فیلد بجه غير صفر به یک گره اشاره میکند و برای هر گره غیر از ريشه یک اشاره گر وجود دارد از اینرو تعداد فیلدهای بچه غیرصفر برای درختی با ] گره دقیقاً برابر 0-1 است. تعداد کل فیلدهای بچه برای درختی با ۱" گره از درجه ‏ برابر میباشد. لذا: "* تعداد اشاره گرهای بچه ‎NULL : NK-(N-1)=N(k-1)+1‏ 

صفحه 11:
*برای درختان دو نمایش خاص که از گره‌هایی با طول ثابت استفاده میکند ارائه ميكنيم. * الف) نمايش درخت بصورت بجه جب-همزاد راست *ب) نمايش درخت بصورت يك درخت درجه 7. د ص2 

صفحه 12:
نمایش دودویی یک درخت * برای نمایش درختان دودویی . دقیقانیاز به دو اتصال یا اشاره گر به ازای هر گره است. Data left child right sibling 

صفحه 13:
بصورت بچه چپ -همزاد راست 

صفحه 14:
بصورت درخت درجه ۲ 

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

صفحه 16:
۵-۲ ساختار درخت دودوبی 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 : 8 2 for all ‏2غط , 1غط .غم‎ 6/7766 , ۱6۲ element BinTree Create() Boolean \sEmpty (bt) BinTree MakeBT(bt1 . item. bt 2) BinTree Lchild(bt) element Data(bt) BinTree Rchild(bt) 

صفحه 17:
۵-۳ تفاوت درخت عادی با درخت دودوبی در هیچ درخت عادی صفر گره وجود ندارد , اما درخت دودویی تهی وجود دارد. 8 در یک درخت دودویی ترتیب فرزندان دارای اهمیت بوده در حالی که در درخت عادی به این صورت نیست. ۱ د ص2 

صفحه 18:
۵-۳ خواص درختان دودویی حداکثر تعداد گره ها " حداکثر تعداد گره ها در سطح ام یک درخت دودویی 211 است. " حداکثر تعداد گره ها در یک درخت دودویی به عمق ۰2۳-1 ‎k‏ است. ۱ د ص2 

صفحه 19:
۵-۳ خواص درختان دودویی رابطه بين تعداد گره های برگ و گره های درجه ۲ برای هر درخت دودویی غیر تهی مانند 1 اگرن تعداد گره های پایانی و42 تعداد گره های درجه ۲ باشد . آنگاه خواهیم داشت : Th =1,+1 . د _ 

صفحه 20:
۵-۳ خواص درختان دودویی 8 یک درخت دودویی پر به عمق . یک درخت دودویی پر است مشروط به اینکه 2-1 گره داشته باشد. 8 یک درخت دودویی با ۲۱ گره و عمق ‏ کامل است . اگر و تنها اگر گره هایش مطابق با گره های شماره گذاری شده در یک درخت دودویی پر به عمق > باشد. © ارتفاع يك درخت دودويى كامل با (! كره برابر است ((1 +ص) رو10] 

صفحه 21:
۵-۳ نمایش درخت دودوپی نمایش آرایه نمایش درخت دودویی به دو صورت است : نمایش لیست پیوندی ۱ د ص2 

صفحه 22:
۵-۲ نمایش آرایه *شیوه شماره گذاری ارایه شده در شکل زیر . اولین نمایش یک. درخت دودویی در حافظه را مطرح و پیشنهاد می کند . از آنجایی که گره ها از ۱ تا ۱] شماره گذاری شده اند . یک آرایه یک بعدی می تواند برای ذخیره سازی گره ها استفاده شود . د ص2 

صفحه 23:
w ‏ه| وا ه‎ |«< w m 

صفحه 24:
۵-۲ نمایش آرایه اگر یک درخت دودویی کامل با 0 گره ( یعنی 1+1 ,100]- عمق ) به تر تیب بالا تعریف شده باشد . آنگاه برای هر گره با انديس / و < 1 ‎١‏ 11<, داریم: (۱) اگر 11 آنگاه پدر أ در [1/2] است .اگر ‎Cowl dit I=L ci‏ و پدری نخواهد داشت. (۲) اگر 211 . آنگاه فرزند چپ در 21 است. اگر 21<1 , آنكاه أ فرزند چپ ندارد. (۳) اگر 10 +21 , آنگاه فرزند راست در 1 +21 است. اگر 1<0 +21 , آنگاه | فرزند راست ندارد د ص2 

صفحه 25:
1 در بدترين حالت . یک درخت مورب به عمق > به 2-1 محل و موقعیت نیاز دارد که از اين مقدار. فقط 1 محل اشغال می شود. . د ص2 

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

صفحه 27:
۵-۲ نما بيش ليست ييوندى با این روش هر گره سه فیلد خواهد داشت : ‎left_child .data .right_child‏ که در زبان ) به شرح زیر ‎po‏ شوند : ‎typedef struct node *tree_pointer ;‏ ‎typedef struct node {‏ ‎int data;‏ tree_pointer left_child .right_child ; 1: ۱ د ص2 

صفحه 28:
اع class Tree; class TreeNode { friend class Tree; private: char data; TreeNode *LeftChild; TreeNode *RightChild; i class Tree { public: Tree(); Tree(const Tree& t); private: TreeNode *root; 1 

صفحه 29:
۵-۲ نمایش لیست پیوندی left_chil right_chil d 1 ۱ نمایش یک گره درخت دودویی 

صفحه 30:
۵-۳ پیمایش درخت دودویی به هنگام پیمایش یک درخت دودویی , با هر گره و زیردرختانش به طرز مشابهی رفتار کنیم. اگر ب. ۰۷ *1 به ترتیب حرکت به چپ . ملاقات کردن یک گره ( برای مثال . چاپ فیلد داده آن گره) و حرکت به راست باشد. آنگاه شش تر کیب ممکن برای پیمایش یک درخت خواهیم داشت : RLV .RVL .VRL .VLR .LRV .LVR د _ 

صفحه 31:
۵-۳ پیمایش درخت دودویی oe اگر تنها حالتی را انتخاب کنیم که ابتدا به سمت چپ و بعد به سمت راست برود . تنها سه ترکیب ۰1:۷1 ۰1:۴۷ ‎VER‏ ‏خواهیم داشت. این سه حللت را با توجه به موقعیت ۷ نسبت به بآ و ‎preordcr . postorder .inorder u3,5 uR‏ می نامیم. د ص2 

صفحه 32:
۵-۳ پیما 3 ييمايش درخت دودويى © در ييمايش :177051010161 . يى كره موقعى ملاقات و جاب مى شود كه زيردرختان جب و راست آن قبلا ملاقات شده باشند. © در ‎tub.‏ 7607061( . یک گره قبل از پیمایش زیردرختان چپ و راست . ملاقات می گردد. 

صفحه 33:
۵-۳ پیمایش درخت دودویی درخت زیر حاوی یک عبارت ریاضی است : ‎ey A/B*C*D*+E‏ درخت دودویی برای یک عبارت محاسباتی ‎j‏ 

صفحه 34:
۵-۳ پیمایش ۱0۲۵06۲ هنگامی که این پیمایش انتخاب می شود . حركت به سمت پایین به طرف چپ انجام می شود و اين عمل تا آخرین گره صورت می گیرد سپس می توان گره را بازیابی کرد و بعد به سمت راست رفته و به همین ترتیب کار ادامه پیدا می کند. : د ص2 

صفحه 35:
۵-۳ پیمایش ۲۱0۲۵6۲ ایک درخت دودویی void inorder (tree_pointer ptr ) /* inorder tree traversal */ { if (ptr) { inorder ( ptr -> left_child ); printf (*% d" .ptr -> data ); inorder (ptr -> right_child); 

صفحه 36:
۵-۳ پیمایش ۲۵0۵۲۵6۲ تابع 101601061 حاوی دستورات لازم برای شکل دوم پیمایش است. بر اساس این پیمایش . گره را ابتدا بازیابی و ملاقات نموده و سپس انشعابات چپ را دنبال و تمام گره ها را بازیابی می کنیم. اين فرآیند ادامه پیدا می کند تا به یک گره تهی برسیم. در اين نقطه . به نزدیکترین جدی که دارای یک فرزند راست باشد مراجعه و با اين گره شروع خواهیم نمود. د ص2 

صفحه 37:
۵-۳ پیمایش ۴۲۵۵۲06۲ با يبمايش ۳160۲06۲ گره های درخت زیر خروجی به شکل زیر خواهند داشت : + * * / ‏ف‎ 5 0 DE اين به شكل یک عبارت 01618 است. : د ص2 

صفحه 38:
۵-۳ پیمایش ۲۵۵۲۵6۲ یک درخت دودویی Vide preorder (tree_pointer ptr ) /* preorder tree traversal */ { if (ptr) { printf (“% d” .ptr -> data ); preorder ( ptr -> left_child ); preorder (ptr -> right_child); ۱ د _ 

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

صفحه 40:
خروجی حاصل از پیمایش ۳05010617 شکل زیر به صورت زیر است : aE) AB cD E+ این خروجی مانند یک عبارت ۳051632 است. د ص2 

صفحه 41:
۵-۳ پیمایش 00۲06۲ غیرباز گشتم Void iter_pointer (tree_pointer node ) { int top =-1; /* initialize stack */ ‏ب رع یدیع‎ stack for(;;) 4 >left ‏زونه‎ G node ; node < - stack */ add ( &top .node ); /* add _ to stack¥pde = delete (&top); /*delete from stack*/ if (! Node) break ; /* empty printf (“% d’. node-> data ) ; node = node -> right_child; 

صفحه 42:
۳-۵ پیمایش 11201۳016۲ غیرباز گشتی تحلیل 1120101672 : فرض کنید تعداد گره های درخت 7 باشد . اگر عمل 1101706۲ 61و را در نظر بگیریم . مشاهده می شود که هر گره درخت فقط یک بار در پشته قرار گرفته و یا از آن خارج می شود. بنابراین اگر تعداد گره های درخت ۰ باشد , پیچیدگی زمان تابع برابر با (62610 می باشد. حافظه مورد نیاز برابر با عمق درخت است که مساوی با (0)۳ د ص2 مى باشد. 

صفحه 43:
۵-۳ پیمایش ترتیب سطحی پیمایش های ۰۳0510۲06۲ ‎inorder . preorder‏ 4 به صورت باز گشت پذیری نوشته یابه صورت غیرباز گشتی . همگی نیازمند پشته می باشند. این پیمایش . ترتیب سطحی . ابتدا ريشه را بازیابی . سپس فرزند چپ ريشه و به دنبال آن فرزند راست ريشه بازیابی می گردد. این شیوه با بازیابی از گره منتهی الیه سمت چپ به سمت راست هر سطح جدید تکرار می گردد. اين پیمایش از صف استفاده می کند. : د ص2 

صفحه 44:
۳-۵ پیمایش ترتیب سطحی پیمایش ترتیب سطحی درخت زیر به صورت زیر است : => + *E*D/C AB 

صفحه 45:
۵-۴ اعمال مفید بر روی درختان دودویی 

صفحه 46:
۵-۵ درختان نخی دودویی تعداد اتصالات تهی در یک درخت دودویی بیشتر از تعداد اشاره گرهای غیرتهی است. در یک درخت دودویی تعداد 1 + اتصال از کل اتصالات آن یعنی ۰ 210 تهی است. یک راه برای به کار گیری این اتصالات توسط پرلین و تورنتن پیشنهاد شد. راه حل این بود که از اتصالات تهی برای ارتباط با دیگر گره ‎Sa GL‏ درخت استفاده شود که در اين صورت درخت را درخت نخی می نامند. د ص2 

صفحه 47:
۵-۵ درختان نخی دودویی برای ایجاد اتصالات نخی از قوانین زیر استفاده می شود : 0 اگر 16]1_0۳110 <-011 تهی باشد . تن را طوری تغییر می دهیم که به گره ای که در پیمایش 1101087 قبل از 17 قرار دارد . اشاره کند. ‎right_child 51 «‏ <-۳17 تهی باشد . تن را طوری تغییر می دهیم که به گره ای که در پیمایش 1120170807 بعد از 17 قرار دارد , اشاره کند. ‏: د ص2 

صفحه 48:
۵-۵ درختان نخی دودویی هنگامی که درختی را در حافظه نمایش می دهیم . بایستی بتوانیم بین اتصالات نخی و واقعی تفاوتی قایل شویم. این کار را با افزودن دو فیلد اضافی به هر گره انجام می دهیم که آنها را ‎.oYight_thread .left_thread‏ نامیم. ۱ د _ 

صفحه 49:
۵-۵ درختان نخی دودویی 

صفحه 50:
۵-۵ پیمایش ۱۱0۲06۲ یک درخت نخی دودوبی برای هر گره مانند 01۲ . در یک درخت دودویی . چنانچه ‎TRUE‏ - ۲۳۲6۵0 _11001<-۳ا0 باشد . طبق تعریف گره بعدی 01۲ در ‎inorder . ptr- (toby‏ ‎child‏ _۲3010< می باشد . در غیر این صورت گره بعدی ۲ با پایین رفتن روی مسیر فرزندان چپ 017 از طرف فرزند سمت راست ۳۲ تا وقتی که به گره ای با وضعیت ‎se Ont «pew» left_thread = TRUE‏ 395 = د _ 

صفحه 51:
۵-۵ پیمایش 100۲06۲ یک درخت نخی دودویی 

صفحه 52:
۵-۵ پیمایش ۱۱0۲06۲ یک درخت نخی دودوبی . : 11051106 ‏تابع‎ ‎ded 5 é threaded Pointer. tree) *sue { ‎of tree In‏ یی جوا ل ‎threaded_pointer temp ; temp = tree -> right_child ; 1] (! Tree -> right_thread) while (! temp -> left_thread) ‎left_child ; temp = temp ‏جد‎ ‎return temp ; ‏پیدا نمودن گره بعد . یک گره خاص در پیمایش 07065 } 

صفحه 53:
۵-۵ پیمایش ۱۱0۲06۲ یک درخت نخی دودوبی Void tinorder (threaded_pointer tree) { 71 i dk verge the threaded binary tree threaded_pointer temp = tree ; for(;;) 1 temp = insucc (temp) ; if (temp = tree ) break ; printf (‘ % 3c” .temp -> data ) ; 1 1 : د ص2 

صفحه 54:
7 نحوه اضافه کردن یک گره جدید به درخت نخ کشی شده را بررسی * برای ارائه روش از نرم افزار 00۳ 00۷۷6۲ برای انیمیشن دادن به کار استفاده نمایید. * بايد الگوریتم کار با دقت آورده شده و میتوانید از شبه کد نیز استفاده ۱ د ص2 

صفحه 55:
۵-۶ نوع ‎(ADT) 3,20 ols‏ هرم 6 :11087 درختی‌لستکه مقدار کلید هر گره آن‌ک‌متر از مقادیر کلیدهاوف رزندانشنباشد. 0 :110187 ی کدرختدودوییک املاستکه ی 171875 60 نیز میب‌اشد ‎tree‏ 10011 درختولستکه مقدار کلید هر گرد آنب-یشتر از مقادیر کسلیدهایف_رزرندانش: با شد ‏2 110117 ی کدرختدودوییک امللستکه در ولقع یک ‏6۵ 1011 میب‌اشد 

صفحه 56:
min heap »max heap ‏مثال از‎ ۵-۶ 

صفحه 57:
۵-۶ اعمال اساسی بر روی ۱620 8 ایجاد یک هرم(0630) تهی 8 جایگذاری عنصر جدید به هرم (0630) حذف بزرگترین عنصر از هرم (0630) د ص2 

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

صفحه 59:
۵-۶ نمایش های صف اولوبت Deletion Of) 96۰ eq”) eq”) og, ») Insertion ©6)1 6)1 00 00 Clog, n) Representation Unordered array Unordered linked list Stored array Stored linked list Max heap 

صفحه 60:
۵-۶ درج عناصر به داخل یک ‎Max Heap‏ ب - محل اولیه گره جدید الف - درخت 968۳ قبل از درج اضافه کردن گره جدید در هر موقعیت دیگری ,تعریف 680 را نقض می کند زیرا نتیجه یک درخت دودویی کامل نخواهد بود. 1 د ص2 

صفحه 61:
۵-۶ درج عنصر به یک ۱620 ۷/3 

صفحه 62:
۵-۶ تحلیل تابع 56۲۲-۲02-620] *از آنجا که ۱620 یک درخت کامل با ۱] عنصر می باشد . دارای ارتفاع ‎1092(N)‏ 2 باشد. این بدین معنی می باشد که حلقه 6 به میزان (۱092)0 تکرار شود. بنابراین پیچیدگی تابع درج برابر (۱092)0 می باشد. : د ص2 

صفحه 63:
Max Heap jl ‏حذف عنصری‎ ۵-۶ هنگامی که عنصری از 2680 1۳082 حذف می شود . آن را از ريشه درخت 1268۳0 می گیریم. moved ¥- 

صفحه 64:
۵-۶ حذف عنصری از ۳۱6۵0 ‎Max‏ 

صفحه 65:
‎delete_max_heap ali Jou ۵-۶‏ * پیچیدگی حذف برابر(7 مع جات ‏* زمان حذف یک عنصر دلخواه از درخت 26۵0 با ۱] عنصر . برابر (0)۳) می باشد. ‏۱ د ص2 

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

صفحه 67:
۵-۷ درختان جستجوی دودویی 

صفحه 68:
class BSTNode { friend class BST; در کلاس نوشته شده فرض شده ‎private:‏ ‏وت فرض ‎BSTNode *left;‏ که هر گره تنها یک مقدار کلید ‎int key;‏ دارد ولی در طراحی پیث فته تر ‎BSTNode *right;‏ _ public: 2 J 1 ae int GetKey(; ‏میتوان از قالبها استفاده نمود.‎ class BST { public: BSTO; bool Insert(int key); BSTNode* Search(int key); void DeleteNode(BSTNode* pNode,bool bRight); private: BSTNode *root; 

صفحه 69:
۵-۷ جستجوی یک درخت دودویی فرض کنید خواسته باشیم دنبال عنصری با کلید 61[ بگردیم. ابتدا از ريشه (۲00) شروع می کنیم . اگر ريشه تهی ‎MEL‏ درخت جستجو فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر اين صورت 663را با با مقدار کلید ريشه مقایسه کرده : * اگر 1607 کمتر از مقدار کلید ريشه باشد . هیچ عنصری در زیردرخت راست وجود ندارد که دارای کلیدی برابر 1667 باشد . بنابراین زیردرخت چپ ريشه را جستجو می کنیم. * اكر 17©ع1 بز ركتر از مقدار كليد ريشه باشد . زيردرخت راست را 

صفحه 70:
۵-۷ تحلیل 562۲6۳ اگر ۲ ارتفاع یا عمق یک درخت جستجوی دودویی باشد , عمل جستجو را در مدت ‎ge pls! OC)‏ شود. د ص2 

صفحه 71:
الگوریتم جستجو در ‎8٩۲‏ بصورت باز گشت BSTNode* BST::Search(int key) { return Search(root , key); 1 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); else return Search(p—right , key); 

صفحه 72:
الگوریتم جستجو در 851 بصورت غير باز كشد BSTNode* BST::Search(int key) { BSTNode *p=root; while(p!=NULL) if(key < p>key) p = p-left; else if(key > pkey) p = poright; else return p; return 0; 

صفحه 73:
۵-۷ درج عنصری به داخل درخت جستجوی دودوبی 

صفحه 74:
۵-۷ درج عنصری به داخل درخت جتجوی دودویی 

صفحه 75:
۵-۷ تحلیل 56۲۲-۲006 زمان لازم برای جستجوی 11110 در یک درخت برابر (0012 مى باشد به نحوى كه « برابر با عمق يا ارتفاع درخت است. بقیه الگوریتم نیاز به زمان (0)1 دارد. بنابراین زمان کل مورد نیاز 1156112006 برابر با (12) © مى باشد. د ص2 

صفحه 76:
bool BST::Insert(int key) 1 BSTNode *p=root; BSTNode *q; while(p!=NULL) { q=P if(key < p>key) p = poleft; else if(key > pkey) P = p-right; else return false; //Error for duplicate ke 1 p = new BSTNode (key); if (!root) root = p; return true; } if(key < q-key) ‏عم‎ = p; else qoright = p; return true; 

صفحه 77:
۵-۷ حذف عنصری از درخت جستجوی دودویی برای حذف ۳۵ از درخت زیر باید فیلد فرزند چپ وللد اين گروه را برایر بأ.1[] لا قرار داده و گره را آزاد نمود : 

صفحه 78:
۵-۷ حذف عنصری از درخت جستجوی دودویی زمانی که یک گره برگ با دو فرزند حذف می شوند . گره را با بزرگترین عنصر در زیر درخت چپ و یا کوچکترین عنصر در زیردرخت راست آن گره جایگزین و تعویض کرد. عمل حذف در زمان (0)13 انجام مى كيرد . به نحوى كه ط عمق درخت مى باشد. : د ص2 

صفحه 79:
if(CurNode-right && CurNode- left) { BSTNode *tmp = CurNode-left; pNode = CurNode; bRight = false; while (tmp-righi) pNode = tmp; bRight = true; tmp = tmp-right; CurNode—key = tmp—key; DeleteNode(pNode , bRight); 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; 1 

صفحه 80:
۵-۷ درختان جستجوی متعادل درختان جستجو با بیشترین عمق (2 (106ور)ختان جستجوی متعادل نامیده می شوند. درختان جستجوی متعادلی وجود دارند که عمل جستجو . درج و حذف را در زمان (606 ممکن می سازند از جمله درختان ‎red_black .2-3 .AVL‏ د _ 

صفحه 81:
۵-۸ درختان انتخابی فرض كنيد داراى 1 مجموعه و رشته مرتب شده ای از عناصر هستیم كه بايد در یک رشته واحد ادغام شوند. هر دنباله یا ترتییب شامل تعدادی رکورد به ترتیب غیرنزولی و فیلد مشخصی به نام 1661 می باشد. > یک دنباله مرتب اجرا (71211) نامیده می شود. فرض كنيد كه 2 تعداد رکوردها در 6 اجرا باشد. عمل ادغام می تواند با تکرار رکورد با کوچکترین کلید انجام شود. د ص2 

صفحه 82:
۵-۸ درختان انتخابی کوچکترین کلید باید ازبین 6 امکان موجود پیدا شود و می تواند رکوردی قبل از هر 6 اجرا (16-11115) باشد. * بهترین روش برای ادغام ۲ اجرا (16-111105) . نیازمند 1-1 مقایسه برای تعیین و انتقال رکورد بعدی به خروجی می باشد. * به ازای 16<2. می توانیم با استفاده از ایده درخت انتخابی . تعداد مقایسه های لازم جهت تعیین کوچکترین عنصر را کاهش دهیم. : د ص2 

صفحه 83:
۵-۸ درختان انتخابی یک درخت انتخابی . یک درخت دودویی است که هر گره آن کوچکتر از دو فرزند خود می باشد بنابراین . گره ريشه نشان دهنده کوچکترین گره در درخت می باشد. : د ص2 

صفحه 84:
5-8 درختان انتخابي 1۵۲ . ۲ mo Tm ۳ 8 7m ‏ف‎ ‎| |r vf fae} foe} fn ۱ ‏ما‎ ‎۶] fre ۳ ‏ع ۵ هب‎ : م امه لت كم امه م اح 

صفحه 85:
۵-۸ درختان انتخابی * زمان تجدید ساختار درخت برایر )4 ‎Glog,‏ باشد. * زمان لازم براى ادغام تمام ‎1١‏ رکورد برابر 20 :0108 )باشد. * زمان کل لازم جهت ادغام ‏ اجرا (۲۱۱۲) برابر 40 1[990/كد. . د ص2 

صفحه 86:
‎۵-9٩‏ جنگل ها ‏جنگل مجموعه 0 < ۲ درخت مجزا می باشد. اگر ربشه درخت را حذف کنیم . آنگاه دارای یک جنگل خواهیم بود. ‏۱ د ص2 

صفحه 87:
‎۵-٩‏ تبدیل جنگل به یک درخت دودوبی ‏جنگل به یک درخت دودویی واحد : ‏ای تبدیل این جنگل به ب دودویی. ِ ‎ie‏ نمایش دودویی هر یک از درختان جنگل را به دست می ‎eal‏ ق ف ; يشه به ‏سيس تلام درختان دودویی را از طریق فیلد همزاد گره ريشه ب یکدیگر متصل می کنیم. ‏د ص2 

صفحه 88:
‎۵-٩‏ تبدیل جنگل به یک درخت دودوبی ‎ooo ‎ 

صفحه 89:
‎۵-٩‏ تبدیل جنگل به یک درخت دودویی ‏ار 77" 'لكُنكلى از درختان باشد , آنكاه درخت دودویی متناظر با اين ‎B pie de‏ را ‏() اگر ۲20 باشد . تهی خواهد بود. ‏)« دارای ريشه ای برابر با ريشه ‎Z)‏ باشد ء دارای زیردرخت چپی برابر با می باشله در نهایت دارای زیردرخت راست مى باشد(,2)1:,....1 ‏. د ص2 

صفحه 90:
‎۵-٩‏ پیمايش جنگل ‎ 

صفحه 91:
‎۵-٩‏ پیمایش جنگل ‎sul.‏ 016010167[ مربوط به 1 معادل با بازیابی گره های "ادر درخت ‎eo preorder‏ باشد: ‎٠‏ اكر 1 تهى باشد , بر كرديد. * ريشه درخت اول را بازیابی کنید. ‏زیردرخت . درخت اول را به صورت 1076017067 پیمایش ‏ساير درختان را به صورت ۳160۲061 پیمایش کنید. ‏1 د ص2 

صفحه 92:
‎۵-٩‏ پیمایش جنگل ‏پیمایش 112016167 مربوط به 1 معادل گره های ۲ در درخت ۲ است که به صورت زیر تعریف می شود : ‏۰ اگر 1 تهى باشدء بر كرديد. ‎٠‏ ريشه درخت . درخت اول را به صورت 112017067 پیمایش کنید. ‏ريشه درخت اول را بازیابی کنید. ساير درختان را به صورت 112017067 پیمایش کنید. ‏د ص2 

صفحه 93:
‎۵-٩‏ پیمایش جنگل ‏هیچ گونه معادل طبیعی برای برای پیمایش ۳0510108۲ درخت دودویی متناظر یک جنگل وجود ندارد . پیمایش ۳05107061 یک جنگل را به صورت زیر بیان ی کنیم : ‏۱) اگر 7 تهی باشد . بر گردید. ‏۲ زیردرخت . اولین درخت ۳ را به صورت 1۳051070617 ۳)_ سایر درختان باقی مانده را به صورت ۳0510۲06۲ ۴ ريشه اولین درخت ۳ را بازيابى كنيد ‏: د ص2 

صفحه 94:
۵-۰ نمایش مجموعه ده عضو از ۰ تا ‎٩‏ که به سه مجموعه مجزا از هم تفکیک شده باشند » می توانند بدین صورت باشند : (0,6,7,۵)< ک, (4,9< رک, ( 235)< رک د ص2 

صفحه 95:
۰ نمایش مجموعه در هر مجموعه بر خلاف معمول که اشاره گرها به از والد به فرزندان در نظر گرفته می شدند. در اینجا اشاره گرها از فرزندان به والد تنظیم می شوند و یا در حقیقت گره ها با رابطه پدری اتصال یافته اند. . د ص2 

صفحه 96:
۰ ۵-۱ اعمال روی مجموعه ها حداقل اعمالی که بر روی مجموعه انجام می شود ء به شرح زیر است : ) اجتماع مجموعه مجزا (طمتصا) : اكثر وت دو مجموعه مجزا باشند . انگاه اجتماع آنها به صورت زیر تعریف می شود : ( همه اعضا به صورت : که «یا عضوباشوا عضو ‎SUS = Sf )‏ ۲ (170)1]( پیداکردن :) : مجموعه ای که 1 عضو آن است را يبدا كنيد ۱ د ص2 

صفحه 97:
۰ ۵-۱ اعمال روی مجموعه ها کم ۲ oy SUS, د _ 

صفحه 98:
۰ ۵-۱ قانون ۷۷6109]1۳009 برای( ز ,)08۱0۴ = J ‎Union(i,j ) s Weighting oi‏ :51 تعدا گره ها در درخت ز کمتر از تعداد گره ها در درخت زباشد . زرا والد زء در غیر اين صورت زرا والد زقرار می دهیم. ‏د ص2 

صفحه 99:
۰ ۵-۱ پیاده سازی قانون ۷۷۵۱0۳۲1۳9 برای پیاده سازی قانون ۷۷6101011100 باید بدانیم که در هر درخت چند گره وجود دارد. اين کار را بدین ترتیب انجام می دهیم که در ريشه هر درخت یک فیلد 0011۳ قرار می دهیم. اگر زیک گره ريشه باشد . آنگاه در [601101]1 تعداد گره های آن درخت خواهد بود. 01110 به صورت یک عدد منفی در فیلد ‎Parent‏ ‏گذاشته می شود. زمانی که قانون ۵10111710 ۷۷را بیان مى کنیم . عمل اجتماع به این صورت را 111110112 می نامیم. د ص2 

صفحه 100:
۵-۰ مجموعه ها 3 اصل موضوعی : فرض کنید 1 یک درخت با « گره باشد که توسط 2 ایجاد شده باشد , در اين صورت هیچ گرهی در 1. سطحی بیشتر از 7+1 109انخواهد داشت. اگر در یک درخت « عضو وجود داشته باشد . بیشترین زمان برای یافتن یک عضو به صورت ‎Masia‏ ‏اگر ترکیبی از 12-1 عمل 11101012 و 2< عمل 112201 داشته باشیم ؛ در بدترین حللت ممکن . زمان به صور(لت,17108 +71)) درمی آید. تعریف ( قانون تخریب ) : اگر [ گرهی روی مسیر از تا ريشه خود باشد . آنگاه را فرزند ريشه قرار دهید.