ساختمان داده ها و الگوریتم

ساختمان داده ها و الگوریتم

اسلاید 1: ساختمان داده‌ها و الگوريتمرشته علوم کامپيوترناصر آيت

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

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

اسلاید 4: PerequisitesC++ پیچیدگی Big oh , theta and omega notation

اسلاید 5: Sortingترتیب زیر را در نظر بگیرید: a[0],a[1],…, a[n-1] پس از مرتب سازی صعودی داریم: a[0] <=a[1] <= ….<=a[n-1] example:8,6,9,4,3 => 3,4,6,8,9

اسلاید 6: Sort metodsInsertion sort Bubble sortSelection sort Count sort Shaker sort Shell sort Heap sort Merge sort Quick sort

اسلاید 7: اضافه کردن یکinsert an element لیست ترتیبی زیر را در نظر بگیرید: input: 3, 6, 9, 14عنصر 5 را به لیست فوق اضافه کنید. output: 3, 5, 6, 9, 14

اسلاید 8: Insert An Element3, 6, 9, 14 insert 5 عدد 5 را با آخرین عنصر لیست مقایسه کنید .Shift 14 right to get 3, 6, 9, , 14Shift 9 right to get 3, 6, , 9, 14 Shift 6 right to get 3, , 6, 9, 14با اضافه کردن 5 خروجی:Output: 3, 5, 6, 9, 14

اسلاید 9: Insert An Element// insert into a[0:i-1]Int j;For (j=i-1 ; j>=0 && t <a[ j] ;j--)A[ j+1] = a[ j]A[ j+1] = t ;

اسلاید 10: Insertion sort لیستی با سایز1 در نظر بگیرید.”اولین عنصر را داخل لیست قرار دهید.“عمل insertion را تکرار کنید بطوریکه ترتیب داده ها حفظ شود

اسلاید 11: Insertion sortSort 7, 3, 5, 6, 1Start with 7 and insert 3=> 3,7 Insert 5=>3, 5, 7Insert 6=>3, 5, 6, 7Insert 1=>1, 3, 5, 6, 7

اسلاید 12: Insertion sortFor (i=1 ; i<a.length ; i++){// insert a[i] into a[0:i-1] //code to insert comes here}

اسلاید 13: Insertion sort For (i=1 ; i<a.length ; i++){// insert a[i] into a[0:i-1] //code to insert comes hereint t =a[ j]int j;For ( j=i-1 ; j>=0 && t <a[ j] ; j--)A[ j+1] = a[ j]A[ j+1] = t ;}

اسلاید 14: Complexityیا پیچیدگیپیچیدگی مکانی /حافظه ایپیچیدگی زمانی شمارش یک عملگر خاصشمارش تعداد مراحل پیچیدگی Asymptotic

اسلاید 15: Compration count شمارش مقایسه ای For (i=1 ; i<a.length ; i++){// insert a[i] into a[0:i-1] //code to insert comes hereint t =a[ j]int j;For ( j=i-1 ; j>=0 && t <a[ j] ; j--)A[ j+1] = a[ j]A[ j+1] = t ;}

اسلاید 16: Compration countیک نمونه کاراکتری از n را در نظر بگیرید، که در آن n طول لیستی باشد که می خواهیم روی آن Insertion sort را انجام دهیم.و تعداد توابع این نمونه کاراکتری را بشمارید.؟؟؟؟Determine count as a function of this instance characteristic.???

اسلاید 17: Compration countFor (j=i-1 ; j>=0 && t <a[ j] ;j--)A[ j+1] = a[ j];چند مقایسه انجام شده است ؟

اسلاید 18: Compration countFor (j=i-1 ; j>=0 && t <a[ j] ;j--)A[ j+1] = a[ j];شمارش تعداد مقایسات وابسته به a[] وt با توجه به i

اسلاید 19: Compration countWorst-case count=maximum countBest –case count=minimum count Avarage count

اسلاید 20: Worst-case Compration countFor (j=i-1 ; j>=0 && t <a[ j] ;j--)A[ j+1] = a[ j];A=[1,2,3,4] and t=0 =>4 comparesA=[1,2,3,..,i] and t=0 =>i compares

اسلاید 21: Worst-case Compration countfor(int i=1; i< n ; i++)For (j=i-1 ; j>=0 && t <a[ j] ;j--)A[ j+1] = a[ j];تعداد کل مقایسات :Total comprase =1+2+3+…+(n-1) =(n-1)n/2

اسلاید 22: Step countیک مرحله از محاسبات وابسته است به مقادیر n برای مثال :10 add , 100 subtracts,1000 multipliesفقط یک step محسوب میشود .وبه این مفهوم نمی باشد که با افزایش n یک مرحله نیز به تعداد step اضافه شود.

اسلاید 23: Step count s/eFor (i=1 ; i<a.length ; i++) 1{// insert a[i] into a[0:i-1] 0 //code to insert comes here 1 int t =a[ j] 0 int j; 1 For ( j=i-1 ; j>=0 && t <a[ j] ; j--) 1 A[ j+1] = a[ j] 1 A[ j+1] = t ; 0}

اسلاید 24: Step counts/e همیشه 0 یا یک نمی باشدX=mymath.sum(a,n)Where n is the instance characteristic has a s/e count of n

اسلاید 25: Step count s/e stepFor (i=1 ; i<a.length ; i++) 1{// insert a[i] into a[0:i-1] 0 //code to insert comes here 1 int t =a[ j] 0 int j; 1 i+1For ( j=i-1 ; j>=0 && t <a[ j] ; j--) 1 iA[ j+1] = a[ j] 1 A[ j+1] = t ; 0}

اسلاید 26: Step countFor (int i=1;; i<a.length; i++){2i+3}Step count for For (int i=1; i<a.length;; i++)Is n Step count for body of for loop is 2(1+2+3+…+n-1)+3(n-1)=(n-1)n +3(n-1)=(n-1)(n+3)

اسلاید 27: محاسبه پیچیدگی در مرتب سازی درجی O(n2)به چه معنی می باشد؟

اسلاید 28: محاسبه پیچیدگی در مرتب سازی درجیبدترین حالت:Ө(n2)بهترین حالت: Ө(n)بنابراین انتظار میرود بدترین حالت زمانی است که n دوبل میشود(تکرار میشود).

اسلاید 29: محاسبه پیچیدگی در مرتب سازی درجیآیا O(n2)خیلی زیاد است؟الگوریتم تجربی(practical) چه میباشد؟

اسلاید 30: Faster Computer Vs Better Algorithmپیشرفت الگوریتم ها مفید تر از پیشرفت سخت افزار است.

اسلاید 31: ساختمان داده Data Structureانواع داده :داده هایی که در یک مجموعه قرار می گیرند(در ارتباط).Ex: integer= {0, +1,-1,+2,-2,….} days of week = {S,M,T,W,TH,SA}

اسلاید 32: Data objectداده هایی که نامربوط با هم هستند. Example: MyDataObject={apple, chair, 2,5,red,green ,jack}

اسلاید 33: Data StructureData oject +روابطی که وجود دارد برای مقایسه میان عناصرEx:369<370280+4=284

اسلاید 34: Data Structureمیان عناصری که مقایسه میشوند در یک مثال:3693 is more signification than 6 3 is immediately to the left of 69 is immediately to the right of 6

اسلاید 35: Data Structureروابط خاص معمولا توسط عملگر های خاص روی چندین نمونه داده ایجاد می شود عبارتند از:Add,subtract, predecessor,multiply ضرب ، تفریق ، جمع

اسلاید 36: Linear (or Ordered) listsInstannces are of the form(e0,e1,e2,….,en-1)Where ei denodes a list element n>=0 is finiteList size is n

اسلاید 37: Linear (or Ordered) listsL= (e0,e1,e2,e3,….,en)روابط زیر بر قرار است: : e0 عنصر جلوی لیست میباشد. “zeroth element”:en-1 عنصر آخرلیست میباشد. “last elements”: ei+1 دقیقا بعدازei قرار می گیرد.

اسلاید 38: مثالهایی از لیست های خطی:Student in COP3530=(jack,jill, Abe ,Henry,Mary ,…,judy)Exams in COP3530=(exam1, exam 2, exam3)Days of Week=(S,M,T,W,TH,SA)Months=(Jan,Feb ,Mar ,Apr,…,Nov,Dec)

اسلاید 39: Linear list Oprations-size()اندازه گیری سایز لیست Example: L=(a,b,c,d,e)Size=5

اسلاید 40: Linear list Oprations-get(the index)یک عنصر را میگیرد و اندیس آن را بعنوان خروجی می دهد.Example: L=(a,b,c,d,e)Get(0)=aGet(2)=cGet(4)=e Get(-1)=errorGet(9)=error

اسلاید 41: Linear list Oprations-indexof (the element)اندیس هر عنصر را برمی گرداند. L= (a,b,d,b,a) Index of(d)=2Index of(a)=0Index of(z)=-1

اسلاید 42: Linear list Oprations-remove(the index)حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند. L=(a,b,c,d,e,f,g)Remove(2) returns cand L become (a,b,d,e,f,g) index of d,e,f and g decrease by 1

اسلاید 43: Linear list Oprations-remove(the index)حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند.L=(a,b,c,d,e,f) Remove(-1)=>error Remove(20)=>error

اسلاید 44: Data structure specification Language independetAbstract Data TypeJava Abstaract class

اسلاید 45: Liner List Abstaract Data Type AbstractData Type Linear List{ instancesOrdered finit collection of zero or more elementsعملگر هاEmpty( ):نتیجه درست را بر می گرداند اگر و فقط اگر لیست خالی باشد ،در غیرنتیجه : false میبا شد.Size( ):اندازه لیست را بر می گرداند.بعبارتی تعداد عناصر داخل لیست را بر می گرداند.

اسلاید 46: Data Representation MethodsArray ---chapter 5Linked---chapter 6Simulated

اسلاید 47: Linear List Array Representation 1 2 3 4 5 6 L=(a,b,c,d,e)

اسلاید 48: Right to Left Mapping

اسلاید 49: Mapping That Skip Every Other position

اسلاید 50: Wrap Around Mapping

اسلاید 51: Represention Used In Text 1 2 3 4 5 6

اسلاید 52: Add/Remove An Element _1Size=5

اسلاید 53: Add/Remove An Element_2Add ( l, g)size-=6

اسلاید 54: Length of Array element[]چون نمی دانیم چه تعداد عنصر در لیست وجود خواهد داشت ،بنابراین باید یک مقدار اولیه برای آن فرض کرد.و سپس بر حسب نیاز آن را افزایش داد.

اسلاید 55: Liner List Abstaract Data TypeGet (index): خروجی آن اندیس عنصر میباشد بر طبق جایگاه آن ودرصورتی مقدار(1-) را برمی گرداند که عنصر مورد نظر در لیست نباشد.Remove (index):عنصر را حذف کرده و محتوای عنصر را برمی گرداند.Add (index, x): عنصر x را در index داده شده اضافه کرده و پس از آن شماره اندیس ما بقی عناصر از موقعیت جاری یک واحد افزایش میابد.Output( ):خروجی لیست است که از چپ به راست مرتب می شود.

اسلاید 56: Linear List As Java abstract ClassPublic abstractclass Linear ListAsAbstractClass{Public abstarct Boolean isEmpty();Public abstarct int size();Public abstarct object get(int index);Public abstarct int indexOf(Object the element);Public abstarct object remove(int index);Public abstarct void add(int index, Object the element);Public abstarct string to sorting();}

اسلاید 57: Linked Representationعناصر لیست در حافظه با ترتیبی دلخواه نگهداری می شوند.explicit information (called a link)اطلاعات صریح که لینک نامیده می شوندبرای رفتن از یک عنصر به عنصر دیگر استفاده میشوند

اسلاید 58: Memory Layoutabcdecaedbهرلینک از یک جدول دلخواه استفاده می کند. A linked representation uses an arbitrary layout.برای نمایش لیست ها از آرایه ها استفاده می شود. L = (a,b,c,d,e)

اسلاید 59: Linked Representationتهی می باشد. (e) اشاره گر عنصر:firstNodeبرای اشاره به عنصر شروع استفاده میشود.caedbfirstNode

اسلاید 60: Normal Way To Draw A Linked Listفیلد اشاره گر فیلد دادهabcdenullfirstNode

اسلاید 61: Chainدریک زنجیر یا در یک لیست از اشاره گر هاهر نود نشان دهنده یک عنصر می باشد.از یک نود به نود دیگر یک اشاره گر وجود دارد.اشاره گر آخرین لیست تهی میباشد.abcdenullfirstNode

اسلاید 62: Node Representationpackage dataStructures;class ChainNode{ Object element; ChainNode next;} nextelement

اسلاید 63: Constructors Of ChainNode ChainNode() {}nullnullnullelementnextelementChainNode(Object element) {this.element = element;} ChainNode(Object element, ChainNode next) {this.element = element; this.next = next;}

اسلاید 64: get(0)checkIndex(0);desiredNode = firstNode; return desiredNode.element;abcdenullfirstNode

اسلاید 65: get(1)checkIndex(1);desiredNode = firstNode.next; return desiredNode.element;abcdenullfirstNode

اسلاید 66: get(2)checkIndex(2);desiredNode = firstNode.next.next; return desiredNode.element;abcdenullfirstNode

اسلاید 67: get(5)checkIndex(5); desiredNode = firstNode.next.next.next.next.next;return desiredNode.element; abcdenullfirstNode

اسلاید 68: NullPointerExceptiondesiredNode = firstNode.next.next.next.next.next.next;abcdenullfirstNode

اسلاید 69: Remove An Elementremove(0)abcdenullfirstNodefirstNode = firstNode.next;

اسلاید 70: abdenullfirstNodecremove(2)ابتدا نود قبل از نودی را که بخواهد حذف شود را انتخاب کنیدfirst node یعنی ccbeforeNode = firstNode.next;bbeforeNode

اسلاید 71: remove(2)اکنون اشاره گرآن را تغییر دهید. beforeNodeدرbeforeNode.next = beforeNode.next.next; beforeNodeabcdenullfirstNode

اسلاید 72: add(0,’f’)abcdenullfirstNodefnewNodeگام اول: نود جدید را انتخاب کنید که حتما دارای فیلد داده واشاره گرباشد .ChainNode newNode = new ChainNode(new Character(‘f’), firstNode);

اسلاید 73: add(0,’f’)abcdenullfirstNodefnewNodeگام اول: آن را بعنوان نود آغاز انتخاب کنید.firstNode = newNode;

اسلاید 74: One-Step add(0,’f’)abcdenullfirstNodefnewNodefirstNode = new ChainNode( new Character(‘f’), firstNode);

اسلاید 75: add(3,’f’)گام اول: ابتدا نود با اندیس 2را انتخاب کنید.abcdenullfirstNodefnewNodebeforeNodecگام دوم: حال نود جدید را ایجاد کرده بطوریکه دارای فیلد داده و فیلد اشاره گر داشته باشد.ChainNode newNode = new ChainNode(new Character(‘f’), beforeNode.next); finally link beforeNode to newNodebeforeNode.next = newNode;

اسلاید 76: Two-Step add(3,’f’)beforeNode = firstNode.next.next;beforeNode.next = new ChainNode(new Character(‘f’), beforeNode.next);abcdenullfirstNodefnewNodebeforeNodec

اسلاید 77: The Class Chain

اسلاید 78: The Class Chainnext (datatype ChainNode)element (datatype Object) کاربردChainNodeabcdenullfirstNodesize =تعدادعناصر لیست میباشد. شمارش

اسلاید 79: The Class Chain /** linked implementation of LinearList */package dataStructures;Import c++; // has Iteratorpublic class Chain implements LinearList{ // data members protected ChainNode firstNode; protected int size; // methods of Chain come here}

اسلاید 80: Constructors /** ایجاد یک لیست خالی */ public Chain(int initialCapacity) { // مقادیر اولیه :firstNode and size // null and 0 } public Chain() {this(0);}

اسلاید 81: The Method isEmpty /** مقدار درست را برمی گردانداگر وفقط اگر لیست خالی باشد */ public boolean isEmpty() {return size == 0;}

اسلاید 82: The Method size() /** خروجی آن شمارش تعداد عناصر داخل لیست میباشد */ public int size() {return size;}

اسلاید 83: The Method checkIndex /** @throws IndexOutOfBoundsException when * index is not between 0 and size - 1 *//**اندیس مربوط به هر عنصر را بر می گرداند و زمانی که 0 یا 1- را برگرداند به این مفهوم است که آن عنصر در لیست وجود ندارد.*/ void checkIndex(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException (index = + index + size = + size); }

اسلاید 84: The Method get public Object get(int index) { checkIndex(index); // نود دلخواه راتغییر دهید ChainNode currentNode = firstNode; for (int i = 0; i < index; i++) currentNode = currentNode.next; return currentNode.element; }abcdenullfirstNode

اسلاید 85: The Method indexOf public int indexOf(Object theElement) { // یک زنجیر از نودها را جستجو کنید ChainNode currentNode = firstNode; int index = 0; // اندیس نود جاری while (currentNode != null && !currentNode.element.equals(theElement)) { // به نود بعدی تغییر دهید currentNode = currentNode.next; index++; }

اسلاید 86: The Method indexOf // اطمینان از اینکه عنصر مربوطه را یافته ایم if (currentNode == null) return -1; else return index; }

اسلاید 87: Removing An Elementremove(0)firstNode = firstNode.next;abcdenullfirstNode

اسلاید 88: Remove An Element public Object remove(int index) { checkIndex(index); Object removedElement; if (index == 0) // نود شروع را حذف کنید { removedElement = firstNode.element; firstNode = firstNode.next; }

اسلاید 89: remove(2) را یافته و اشاره گر آن را تغییر دهیدbeforeNode beforeNode.next = beforeNode.next.next; beforeNodeabcdenullfirstNode

اسلاید 90: Remove An Element else { // جایگاهی برای قرار دادن نود جاری میباشد:q ChainNode q = firstNode; for (int i = 0; i < index - 1; i++) q = q.next; removedElement = q.next.element; q.next = q.next.next; // نود دلخواه را حذف کنید } size--; return removedElement; }

اسلاید 91: One-Step add(0,’f’)abcdenullfirstNodefnewNodefirstNode = new ChainNode(‘f’, firstNode);

اسلاید 92: Add An Element public void add(int index, Object theElement) { if (index < 0 || index > size) // موقعیت لیست نادرست است throw new IndexOutOfBoundsException (index = + index + size = + size); if (index == 0) // به جلو اضافه کنید. firstNode = new ChainNode(theElement, firstNode);

اسلاید 93: Two-Step add(3,’f’)beforeNode = firstNode.next.next;beforeNode.next = new ChainNode(‘f’, beforeNode.next);abcdenullfirstNodefnewNodebeforeNodec

اسلاید 94: Adding An Element else { // عنصر جدید را بیابید ChainNode p = firstNode; for (int i = 0; i < index - 1; i++) p = p.next; // pاضافه کنید بعد از p.next = new ChainNode(theElement, p.next); } size++; }

اسلاید 95: Chain With Header NodeabcdenullheaderNode

اسلاید 96: Empty Chain With Header NodeheaderNodenull

اسلاید 97: Circular ListabcdefirstNode

اسلاید 98: Doubly Linked ListabcdenullfirstNodenulllastNode

اسلاید 99: Doubly Linked Circular ListabcdefirstNode

اسلاید 100: Doubly Linked Circular List With Header NodeabceheaderNoded

اسلاید 101: Empty Doubly Linked Circular List With Header NodeheaderNode

اسلاید 102: Arrays

اسلاید 103: 1D Array Representation In C, and C++یک نمونه آرایه یک بعدی x = [a, b, c, d]د ر خانه های مجاور یکدیگر قرار میگیرند Memoryabcdstart location(x[i]) = start + i

اسلاید 104: Space Overheadspace overhead = 4 bytes for start + 4 bytes for x.length = 8 bytes(میزان فضایی که برای آرایه فوق نیاز داریم )Memoryabcdstart

اسلاید 105: 2D Arraysآرایه دو بعدی a declared as:int [][]a = new int[3][4];که در یک جدول نشان داده م شود.a[0][0] a[0][1] a[0][2] a[0][3]a[1][0] a[1][1] a[1][2] a[1][3]a[2][0] a[2][1] a[2][2] a[2][3]

اسلاید 106: Rows Of A 2D Arraya[0][0] a[0][1] a[0][2] a[0][3] row 0a[1][0] a[1][1] a[1][2] a[1][3] row 1a[2][0] a[2][1] a[2][2] a[2][3] row 2

اسلاید 107: Columns Of A 2D Arraya[0][0] a[0][1] a[0][2] a[0][3]a[1][0] a[1][1] a[1][2] a[1][3]a[2][0] a[2][1] a[2][2] a[2][3]column 0column 1column 2column 3

اسلاید 108: 2D Array Representation In C and C++سطر های آرایه دو بعدی ,آرایه های یک بعدی هستند.نمایش آرایه های دوبعد با استفاده از آرایه یک بعدی x = [row0, row1, row 2] row 0 = [a,b, c, d] row 1 = [e, f, g, h] row 2 = [i, j, k, l]and store as 4 1D arrays آرایه دو بعدی x a, b, c, de, f, g, hi, j, k, l

اسلاید 109: 2D Array Representation In Java, C, and C++x.length = 3x[0].length = x[1].length = x[2].length = 4abcdefghijklx[]

اسلاید 110: Space Overheadspace overhead = overhead for 4 1D arrays = 4 * 8 bytes = 32 bytes = (number of rows + 1) x 8 bytesabcdefghijklx[]

اسلاید 111: Array Representation In C and C++این نمایش آرایه آرایه ها نامیده می شود.با توجه به شکل فوق نیازبه حافظه ای با سایز های 3و4و4و4 برای ذخیره آرایه های یک بعدی دارد.یک بلوک حافظه شامل سایزتعداد ستونها و سطرها میباشدabcdefghijklx[]

اسلاید 112: Row-Major MappingExample 3 x 4 array:a b c de f g hi j k lآرایه فوق در یک آرایه یک بعدی قرار گرفته است بطوریکه هر عنصر آن یک سطر از آرایه فوق است و بعبارتی هر سطر آن یک آرایه یک بعدی می باشد.عناصرداخل هر سطر از چپ به راست مرتب شده اند .سطرها از بالا به پایین مرتب شده اند .We get y[] = {a, b, c, d, e, f, g, h, i, j, k, l}row 0row 1row 2…row i

اسلاید 113: Column-Major Mappinga b c de f g hi j k lآرایه فوق در یک آرایه یک بعدی قرار گرفته است بطوریکه هر عنصر آن یک ستون از آرایه فوق است و بعبارتی هر ستون آن یک آرایه یک بعدی می باشد. عناصرداخل هر ستون از بالا به پایین مرتب شده اند .ستون هااز چپ به راست مرتب شده اند . We get y = {a, e, i, b, f, j, c, g, k, d, h, l}

اسلاید 114: Sparse Matricessparse … تعدادبیشتر عناصر آن صفر می باشدdense … تعدادکمتر عناصر آن صفر می باشد

اسلاید 115: Representation Of Unstructured Sparse Matricesهر عنصر غیر صفری در ماتریس اسپارس را میتوان بصورت زیر نشان داد(row, column, value)

اسلاید 116: Single Linear List Example0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0list = row 1 1 2 2 4 4column 3 5 3 4 2 3value 3 4 5 7 2 6

اسلاید 117: Array Linear List Representation row 1 1 2 2 4 4list = column 3 5 3 4 2 3 value 3 4 5 7 2 6 element 0 1 2 3 4 5 row 1 1 2 2 4 4 column 3 5 3 4 2 3 value 3 4 5 7 2 6

اسلاید 118: Chain Representationساختار نود rowcolnextvalue

اسلاید 119: Single Chain row 1 1 2 2 4 4list = column 3 5 3 4 2 3 value 3 4 5 7 2 613315425274246343nullfirstNode2

اسلاید 120: One Linear List Per Row 0 0 3 0 4 0 0 5 7 00 0 0 0 0 0 2 6 0 0 row1 = [(3, 3), (5,4)]row2 = [(3,5), (4,7)]row3 = []row4 = [(2,2), (3,6)]

اسلاید 121: Array Of Row Chainsساختار نود nextvaluecol

اسلاید 122: Array Of Row Chains0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0row[]33null4553null7422null63null

اسلاید 123: Orthogonal List RepresentationNode structure.rowcolnextdownvalue

اسلاید 124: Row Lists0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0null133154235247422436nnn

اسلاید 125: Column Lists0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0133154235247422436nnn

اسلاید 126: Orthogonal Lists0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0nullrow[]133154235247422436nnnnnn

اسلاید 127: Variations May use circular lists instead of chains.

اسلاید 128: Stacksپشته نوعی لیست خطی میباشد.اولین عنصری که داخل پشته قرار میگیرد bottom نامیده می شودآخرین عنصری که داخل پشته قرار بگیرد top نامیده می شودعملیات حذف و درج فقط از top امکان پذیر می باشد

اسلاید 129: Stack Of Cupsبرای درج وحذف F باید از topعمل کرد.bottomtopCABDEFStack=LIFO=LAST IN FIRST OUTbottomtopCABDE

اسلاید 130: The Interface Stackpublic interface Stack{ public boolean empty(); public Object peek(); public void push(Object theObject); public Object pop();}

اسلاید 131: Parentheses Matching(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)Output pairs (u,v) such that the left parenthesis at position u is matched with the right parenthesis at v.(2,6) (1,13) (15,19) (21,25) (27,31) (0,32) (34,38)(a+b))*((c+d)(0,4)right parenthesis at 5 has no matching left parenthesis(8,12)left parenthesis at 7 has no matching right parenthesis

اسلاید 132: Parentheses Matchingعبارت را از چپ به راست بخوانید.وقتی به Left parenthesis رسید آن رادر پشته push کنید.وقتی به right parenthesis رسید آن رااز پشته pop کنید.

اسلاید 133: Example(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n) 0 1 2

اسلاید 134: Example(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n) 0 1(2,6)(1,13)15

اسلاید 135: Example(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n) 0 1(2,6)(1,13)(15,19)21

اسلاید 136: Example(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n) 0 1(2,6)(1,13)(15,19)(21,25)27

اسلاید 137: Example(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n) 0 1(2,6)(1,13)(15,19)(21,25)(27,31)(0,32)and so on

اسلاید 138: Towers Of Hanoi/BrahmaABC123464 حلقه طلا از ستون A بهC انتقال داده می شوند.هر ستون در آن مانند یک پشته عمل می کند.و هیچ حلقه بزرگی روی کوچکتر از خودش قرار نمی گیرد.

اسلاید 139: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC123

اسلاید 140: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC123

اسلاید 141: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC123

اسلاید 142: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC123

اسلاید 143: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC123

اسلاید 144: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC123

اسلاید 145: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC123

اسلاید 146: Towers Of Hanoi/Brahma3-disk Towers Of Hanoi/BrahmaABC1237 disk moves

اسلاید 147: Recursive SolutionABC1با استفاده از مساله برج هانوی n > 0 حلقه را میتوان از A به C با استفاده از B منتقل کرد.با استفاده از C تعداد n-1 حلقه را از A به B انتقال داده.

اسلاید 148: Recursive SolutionABC1حلقه اول ستون Aرا از Aبه C انتقال دهید.

اسلاید 149: Recursive SolutionABC1 n-1حلقه را از B به C انتقال دهید.

اسلاید 150: Recursive SolutionABC1moves(n) = 0 when n = 0moves(n) = 2*moves(n-1) + 1 = 2n-1 when n > 0

اسلاید 151: Stackspublic interface Stack{ public boolean empty(); public Object peek(); public void push(Object theObject); public Object pop();}

اسلاید 152: Derive From A Linear List ClassArrayLinearListChain

اسلاید 153: Derive From ArrayLinearListعنصر بالای پشته معادل چپ ترین ویا راست ترین عنصر داخل آرایه می باشد.empty() => isEmpty()O(1) timepeek() => get(0) or get(size() - 1)O(1) time0123456abcde

اسلاید 154: Derive From ArrayLinearListوقتی که top در موقعیت چپ ترین عنصر آرایه قراردارد push(theObject) => add(0, theObject)O(size) timepop() => remove(0)O(size) time0123456abcde

اسلاید 155: Derive From ArrayLinearListوقتی که top در موقعیت راست ترین عنصر آرایه قراردارد push(theObject) => add(size(), theObject)O(1) timepop() => remove(size()-1)O(1) timeuse right end of list as top of stack0123456abcde

اسلاید 156: Derive From Chainعنصر بالای پشته معادل چپ ترین ویا راست ترین عنصر داخل آرایه می باشد.empty() => isEmpty()O(1) timeabcdenullfirstNode

اسلاید 157: Derive From ChainabcdenullfirstNodeوقتی که top در موقعیت چپ ترین عنصر آرایه قراردارد peek() => get(0) O(1) time push(theObject) => add(0, theObject) O(1) time pop() => remove(0) O(1) time

اسلاید 158: Derive From ChainabcdenullfirstNodeوقتی که top در موقعیت راست ترین عنصر آرایه قراردارد peek() => get(size() - 1) O(size) time push(theObject) => add(size(), theObject) O(size) time pop() => remove(size()-1) O(size) time use left end of list as top of stack

اسلاید 159: empty() And peek()public boolean empty() {return isEmpty();}public Object peek(){ if (empty()) throw new EmptyStackException(); return get(size() - 1)} 0123456abcde

اسلاید 160: push(theObject) And pop()public void push(Object theElement) {add(size(), theElement);}public Object pop(){ if (empty()) throw new EmptyStackException(); return remove(size() - 1);}0123456abcde

اسلاید 161: A Faster pop()if (empty()) throw new EmptyStackException(); return remove(size() - 1);vs.try {return remove(size() - 1);}catch(IndexOutOfBoundsException e) {throw new EmptyStackException();}

اسلاید 162: push(…)public void push(Object theElement){ // increase array size if necessary if (top == stack.length - 1) stack = ChangeArrayLength.changeLength1D (stack, 2 * stack.length); // put theElement at the top of the stack stack[++top] = theElement;} 01234abcdetop

اسلاید 163: pop()public Object pop(){ if (empty()) throw new EmptyStackException(); Object topElement = stack[top]; stack[top--] = null; // enable garbage collection return topElement;} 01234abcdetop

اسلاید 164: Linked Stack From ScratchSee text.

اسلاید 165: Performance500,000 pop, push, and peek operations initial capacityClass 10 500,000ArrayStack 0.44s 0.22sDerivedArrayStack 0.60s 0.38sDerivedArrayStackWithCatch 0.55s 0.33sjava.util.Stack 1.15s -DerivedLinkedStack 3.20s 3.20sLinkedStack 2.96s 2.96s

اسلاید 166: Queuesیک لیست خطی می باشد. عنصر جلوی صف front نامیده میشود.عنصر انتهای لیست rear نامیده میشود.افزودن عنصر به لیست فقط ازانتهای صف rear امکان پذیر است.حذف کردن عناصراز لیست از جلوی صفfront امکان پذیر است.

اسلاید 167: Bus Stop QueueBus Stopfrontrearrearrearrearrear

اسلاید 168: Bus Stop QueueBus Stopfrontrearrearrear

اسلاید 169: Bus Stop QueueBus Stopfrontrearrear

اسلاید 170: Bus Stop QueueBus Stopfrontrearrear

اسلاید 171: The Interface Queuepublic interface Queue{ public boolean isEmpty(); public Object getFrontEelement(); public Object getRearEelement(); public void put(Object theObject); public Object remove();}

اسلاید 172: Derive From ArrayLinearListزمانی کهfront چپ لیست و rear در راست لیست باشد.Queue.isEmpty() => super.isEmpty()O(1) timegetFrontElement() => get(0)O(1) timegetRearElement() => get(size() - 1)O(1) timeput(theObject) => add(size(), theObject)O(1) timeremove() => remove(0)O(size) time0123456abcde

اسلاید 173: Derive From ArrayLinearListزمانی کهfront راست لیست و rear درچپ لیست باشد.Queue.isEmpty() => super.isEmpty()O(1) timegetFrontElement() => get(size() - 1)O(1) timegetRearElement() => get(0)O(1) timeput(theObject) => add(0, theObject)O(size) timeremove() => remove(size() - 1)O(1) time0123456edcba

اسلاید 174: Derive From ArrayLinearListعملیات درج وحذف در صف با (1)O صورت می گیرد.

اسلاید 175: Derive From ExtendedChainabcdenullfirstNodelastNodefrontrear وقتی که front چپ لیست و rearراست لیست قرار دارد Queue.isEmpty() => super.isEmpty() O(1) time getFrontElement() => get(0) O(1) time

اسلاید 176: Derive From ExtendedChainabcdenullfirstNodelastNodefrontrear getRearElement() => getLast() … new method O(1) time put(theObject) => append(theObject) O(1) time remove() => remove(0) O(1) time

اسلاید 177: Derive From ExtendedChainedcbanullfirstNodelastNoderearfront وقتی که front راست لیست و rearچپ لیست قرار دارد Queue.isEmpty() => super.isEmpty() O(1) time getFrontElement() => getLast() O(1) time

اسلاید 178: Derive From ExtendedChainabcdenullfirstNodelastNoderearfront getRearElement() => get(0) O(1) time put(theObject) => add(0, theObject) O(1) time remove() => remove(size-1) O(size) time

اسلاید 179: Custom Array Queueکاربرد یک آرایه یک بعدی بعنوان صفqueue[]کاربرد یک آرایه یک بعدی بعنوان صف حلقوی [0][1][2][3][4][5]

اسلاید 180: Custom Array Queueصف حلقوی با 3 عنصر پر شده است.[0][1][2][3][4][5]ABC

اسلاید 181: Custom Array Queueحالت دیگری از قرار گیری 3 عنصر در لیست حلقوی[0][1][2][3][4][5]ABC

اسلاید 182: Custom Array Queueکاربرد front and rear در لیست حلقویfront مکانی است که ب ابتدای لیست اشاره می کند.Rear مکانی است که به انتهای لیست اشاره می کند.[0][1][2][3][4][5]ABCfrontrear[0][1][2][3][4][5]ABCfront rear

اسلاید 183: Add An Element[0][1][2][3][4][5]ABCfrontrearrear درجهت عقربه های ساعت حرکت می کند.

اسلاید 184: Add An Elementrear درجهت عقربه های ساعت حرکت دهید. [0][1][2][3][4][5]ABCfrontrearدر مکانی که rear به آن اشاره می کند queue[rear] را اضافه کنید.D

اسلاید 185: Remove An Element[0][1][2][3][4][5]ABCfrontrearFront را یک واحد جابه جا کنید.

اسلاید 186: Remove An Element[0][1][2][3][4][5]ABCfrontrearFront را یک واحددر جهت عقربه های ساعت جابه جا کنید.و محتوای queue[front] را از صف حذف کنید.

اسلاید 187: Moving rear Clockwise[0][1][2][3][4][5]ABCfrontrearrear++; if (rear = = queue.length) rear = 0;rear = (rear + 1) % queue.length;

اسلاید 188: Empty That Queue[0][1][2][3][4][5]ABCfront rear

اسلاید 189: Empty That Queue[0][1][2][3][4][5]BCfront rear

اسلاید 190: Empty That Queue[0][1][2][3][4][5]Cfront rear

اسلاید 191: Empty That Queueزمانی تمام عناصر داخل صف حذف شود آنگاه: front = rear اگر صف خالی باشد front = rear = 0[0][1][2][3][4][5]front rear

اسلاید 192: A Full Tank Please[0][1][2][3][4][5]ABCfront rear

اسلاید 193: A Full Tank Please[0][1][2][3][4][5]ABCfront rearD

اسلاید 194: A Full Tank Please[0][1][2][3][4][5]ABCfront rearDE

اسلاید 195: A Full Tank Please[0][1][2][3][4][5]ABCfront rearDEFاگر به پر کردن صف ادامه دهیم در نهایت می رسیم به شرط: front = rearاگر دقت کنید همان شرط خالی بودن صف می باشد درصورتی که صف پر است!

اسلاید 196: Ouch!!!!!شرط پر و خالی بودن در صف حلقویQueue is empty iff (front == rear) && !lastOperationIsPutQueue is full iff (front == rear) && lastOperationIsPut

اسلاید 197: Ouch!!!!!شرط پر و خالی بودن در صف معمولیQueue is empty iff (size == 0)Queue is full iff (size == queue.length)

اسلاید 198: Trees

اسلاید 199: Nature Lover’s View Of A Treeریشهشاخهبرگ ها

اسلاید 200: Computer Scientist’s Viewشاخهبرگ هاریشهگره

اسلاید 201: Linear Lists And Treesکاربردهای لیست های خطی :برای داده های ترتیبی است(e0, e1, e2, …, en-1)روزهای هفتهماه های سالدانشجویان یک کلاسکاربرد درخت:برای داده هایی با سلسله مراتب یکسانمانند کارمندان یک شرکت

اسلاید 202: Hierarchical Data And Treesعنصری که در بالاترین مرتبه قرار دارد rootیا ریشه نامیده میشود.Childrenعناصری که در مراتب بعد از ریشه قرار می گیرند نامیده می شود.leaves عناصری هستند که فاقدchildren هستند.

اسلاید 203: great grand child of rootgrand children of rootchildren of rootClasses (Part Of Figure 1.1)ObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeExceptionroot

اسلاید 204: Definitionیک درخت از یک مجموعه عناصر متناهی تشکیل شده است.اولین عنصر ریشه نامیده می شود.مابقی عناصرزیر درخت نامیده subtrees of t می شود.

اسلاید 205: SubtreesObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeExceptionroot

اسلاید 206: LeavesObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeException

اسلاید 207: Parent, Grandparent, Siblings, Ancestors, DescendantsObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeException

اسلاید 208: Level 4Level 3Level 2LevelsObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeExceptionLevel 1

اسلاید 209: Cautionبه هرسطح یا Level در درخت یک شماره میدهیم:ریشه در level 0 قرار دارد.زیر درخت های ریشه از سطح 1شروع می شوند.البتهlevel ریشه می تواند از سطح یک نیز باشد بنابراین level مربوط به زیر درخت های ریشه ا سطح 2 شروع میشود.

اسلاید 210: height = depth = number of levelsLevel 3ObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeExceptionLevel 4Level 2Level 1

اسلاید 211: Node Degree = Number Of ChildrenObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeException321100100

اسلاید 212: Tree Degree = Max Node DegreeDegree of tree = 3.ObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeException321100100

اسلاید 213: Binary Treeدرخت دودویی از تعداد محدودی عنصر تشکیل شده است.اولین عنصر آن ریشه می باشد.درخت دودویی درختی است که درجه هر گره در آن یا صفر باشد یادو.تعریف:درجه گره:شامل تعداد زیر درخت های آن گره میباشد.اگر درجه گره دو باشد دو زیر درخت آن زیر درخت های چپ و راست نامیده می شوند.

اسلاید 214: Differences Between A Tree & A Binary Treeهر گره در درخت باینری درجه بیشتر از دو ندارد.یک درخت دودویی می تواند خالی باشد اما درخت معمولی نمی تواند خالی باشد.

اسلاید 215: Differences Between A Tree & A Binary Treeدر درخت باینری زیر درخت ها دارای ترتیب می باشند.اما در درخت معمولی برای زیر درخت ها ترتیبی قائل نیستیم.ababترتیب زیر درخت ها:متفاوت هستنداگر به دیددرخت باینری به آنها نگاه کرد.یکسان هستند اگر به دیددرخت معمولی به آنها نگاه کرد

اسلاید 216: Arithmetic Expressions(a + b) * (c + d) + e – f/g*h + 3.25عبارت محاسباتی بالا تسکیل شده از:Operators (+, -, /, *).عملگرها//Operands (a, b, c, d, e, f, g, h, 3.25, (a + b), (c + d), etc.).عملوند ها//Delimiters ((, )).

اسلاید 217: Operator Degreeانواع عملگر ها:عملگر های دودویی:نیازمند دو عملوند هستند.a + bc / de - fعملگر های یکانی:نیازمند یک عملوند هستند.+ g- h

اسلاید 218: Infix Formروش معمولی برای نوشتن یک عبارت.عملگر های دودوئی میان دو عملوند قرار می گیرند.a * ba + b * ca * b / c(a + b) * (c + d) + e – f/g*h + 3.25

اسلاید 219: Operator Prioritiesکدام عملگر زودتر اعمال می شود؟a + b * ca * b + c / dبرای عملگر هاترتیب یا اولویت قائل می شویمpriority(*) = priority(/) > priority(+) = priority(-)عملگری زودتر اعمال می شود که بالاترین اولویت را داشته باشد.

اسلاید 220: Tie Breakerاگر عملگرهایی که در عبارت قرار می گیرند دارای اولویت یکسان باشند از چپ به راست عملگر ها را روی عملوندها اعمال کنید.a + b - ca * b / c / d

اسلاید 221: Infix Expression Is Hard To Parseسه روش برای نمایش یک عبارت محاسباتی داریم:Infix:که درآن ابتدا عملوندچپ /بعدعملگردر وسط/ونهایتاعملوند راست قرار می گیرد.prefix :که درآن ابتدا عملگریا ریشه / بعدعملوندچپ /ونهایتاعملوند راست قرار می گیرد.postfix :که درآن ابتدا عملوندچپ عملگریا ریشه / بعدعملوندراست /ونهایتا ریشه قرار می گیرد.

اسلاید 222: Postfix Formمثال:Infix = a + bPostfix = ab+

اسلاید 223: Postfix ExamplesInfix = a + b * cPostfix =abc*+Infix = a * b + cPostfix =ab*c+Infix = (a + b) * (c – d) / (e + f) Postfix =ab+cd-*ef+/

اسلاید 224: Unary OperatorsReplace with new symbols.+ a => a @+ a + b => a @ b +- a => a ?- a-b => a ? b -

اسلاید 225: Postfix Evaluationعبارت محاسباتی را از چپ به راست بخوانیدبه هر oprand یا عملوند رسیدیددر پشته push کنید.زمانی که به عملوند رسیدید از پشته popکنید وعملگر را روی آن اعمال کنید.این روش برای این است که در postfix عملگر بعد از عملوند ها می آید.

اسلاید 226: Postfix Evaluation(a + b) * (c – d) / (e + f) a b + c d - * e f + /a b + c d - * e f + /stackaa b + c d - * e f + /ba b + c d - * e f + /

اسلاید 227: Postfix Evaluation(a + b) * (c – d) / (e + f) a b + c d - * e f + /a b + c d - * e f + /stack(a + b)a b + c d - * e f + /a b + c d - * e f + /a b + c d - * e f + /ca b + c d - * e f + /da b + c d - * e f + /

اسلاید 228: Postfix Evaluation(a + b) * (c – d) / (e + f) a b + c d - * e f + /stack(a + b)a b + c d - * e f + /(c – d)

اسلاید 229: Postfix Evaluation(a + b) * (c – d) / (e + f) a b + c d - * e f + /stack(a + b)*(c – d)a b + c d - * e f + /ea b + c d - * e f + /a b + c d - * e f + /fa b + c d - * e f + /

اسلاید 230: Postfix Evaluation(a + b) * (c – d) / (e + f) a b + c d - * e f + /stack(a + b)*(c – d)a b + c d - * e f + /(e + f)a b + c d - * e f + /a b + c d - * e f + /a b + c d - * e f + /a b + c d - * e f + /

اسلاید 231: Prefix Formدرprefix ابتدا عملگر و سپس عملوند چپ ونهایتا عموند راست می آید.Infix = a + bPostfix = ab+Prefix = +ab

اسلاید 232: Binary Tree Forma + b+ab- a-a

اسلاید 233: Binary Tree Form(a + b) * (c – d) / (e + f)/+ab-cd+ef*/

اسلاید 234: Merits Of Binary Tree Formکار با الگوریتم درخت باینری بهینه تر از عبارت محاسباتی است.Binary Tree+ab-cd+ef*/

اسلاید 235: Binary Tree Properties & Representation

اسلاید 236: Minimum Number Of Nodesحداقل تعداد گره های یک درخت باینری به اندازه ارتفاع آن میباشد.آخرین گره در درخت باینری معرف ارتفاع می باشد.حداقل تعداد گره ها در درخت دودوییh میباشد.

اسلاید 237: Maximum Number Of Nodesبرای درخت کامل:درختی که تمام گره های سطح آخرش وجود داشته باشد. برای محاسبه حداکثر تعداد گره هااز روش زیر:Maximum number of nodes= 1 + 2 + 4 + 8 + … + 2h-1= 2h - 1

اسلاید 238: Number Of Nodes & Heightاگر n تعداد گره های یک درخت باینری باشد محدوده آن :h <= n <= 2h – 1log2(n+1) <= h <= n

اسلاید 239: Full Binary Treeتعدادگره ها در یک درخت دودویی به ارتفاع h:2h – 1 میباشد.ارتفاع در درخت کامل بالا 4 میباشد.

اسلاید 240: Numbering Nodes In A Full Binary Treeتعداد نودهادر درخت باینری از 1 تا 2h – 1 متغیر است.شمارش سطوح از بالا به پایین می باشد.در هر سطح شمارش گره ها از چپ به راست می باشد.123456789101112131415

اسلاید 241: Node Number Properties والد هر گره مثل i درگره i / 2 آن میباشد ,البته به استثنای i = 1. زیرا:i = 1 ریشه میباشد وریشه والد ندارد .123456789101112131415

اسلاید 242: Node Number Properties گره چپ i در 2i میباشد.n تعدادگره های یک درخت باشد . اگر 2i > n باشد آنگاه i دارای فرزند چپ نمی باشد.123456789101112131415

اسلاید 243: Node Number Properties گره راست i در 2i+1 میباشد.n تعدادگره های یک درخت باشد . اگر 2i+1 > n باشد آنگاه i دارای فرزند راست نمی باشد.123456789101112131415

اسلاید 244: Complete Binary Tree With n Nodes در یک درخت باینری تعداد گره ها میان1 تا n می باشد.اگر درخت شامل هر n تا باشد آنگاه به آن درخت ,درخت کامل گویند و سطر آخر کاملا پر نشده باشد و گره ها ازچپ به راست قرار گرفته باشد.

اسلاید 245: Exampleمثال:درخت کامل را با 10 گره در نظر بگیرید.123456789101112131415

اسلاید 246: Binary Tree Representationبرای نمایش درخت دودویی می توان از آرایه استفاده کرد.نمایش با استفاده از لیست های پیوندی

اسلاید 247: Array Representationابتداگره های یک درخت را به صورت سطحیLevel Order از چپ به راست شماره گذاری کرده سپس درخت را سطحی پیمایش کرده به این صورت که گره i در tree[i] قرار می گیرد.tree[]0510abcdefghijbacdefghi j12345678910

اسلاید 248: Right-Skewed Binary Treeبرای نمایش یک درخت دودویی با استفاه ازیک آرایه با سایزn+1 تا 2nنیاز داریم.ab13c7d15tree[]0510a-b---c-------15d

اسلاید 249: Linked Representationتمام گره های درخت باینری در نمایش پیوندی به صورت یک نود نمایش داده می شود که دارای دو اشاره گر یکی به راست ویکی به چپ دارد.کل فضایی که نیاز داریم برای n گره درخت باینری جهت نمایش لیست پیوندی: n * (space required by one node).

اسلاید 250: The Class BinaryTreeNodepackage dataStructures;public class BinaryTreeNode{ Object element; BinaryTreeNode leftChild; // زیر درخت چپ BinaryTreeNode rightChild;// زیر درخت راست}

اسلاید 251: Linked Representation ExampleacbdfeghleftChildelementrightChildroot

اسلاید 252: Binary Tree Traversal MethodsPreorderInorderPostorderLevel order

اسلاید 253: Binary Tree Traversal Methodsدر پیمایش درخت باینری هر گره فقط یک مرتبه visitمیشود.

اسلاید 254: Binary Tree Traversal MethodsPreorderInorderPostorderLevel order

اسلاید 255: Preorder Traversalpublic static void preOrder(BinaryTreeNode t){ if (t != null) { visit(t); preOrder(t.leftChild); preOrder(t.rightChild); }}

اسلاید 256: Preorder Example (visit = print)abcabc

اسلاید 257: Preorder Example (visit = print)abcdefghijabdgheicfj

اسلاید 258: Preorder Of Expression Tree+ab-cd+ef*/معادل prefix در عبارت محاسباتی!/*+ab-cd+ef

اسلاید 259: Inorder Traversalpublic static void inOrder(BinaryTreeNode t){ if (t != null) { inOrder(t.leftChild); visit(t); inOrder(t.rightChild); }}

اسلاید 260: Inorder Example (visit = print)abcbac

اسلاید 261: Inorder Example (visit = print)abcdefghijgdhbeiafjc

اسلاید 262: Inorder By Projection (Squishing)abcdefghijgdhbeiafjc

اسلاید 263: Inorder Of Expression Tree+ab-cd+ef*/ea+b*cd/+f-

اسلاید 264: Postorder Traversalpublic static void postOrder(BinaryTreeNode t){ if (t != null) { postOrder(t.leftChild); postOrder(t.rightChild); visit(t); }}

اسلاید 265: Postorder Example (visit = print)abcbca

اسلاید 266: Postorder Example (visit = print)abcdefghijghdiebjfca

اسلاید 267: Postorder Of Expression Tree+ab-cd+ef*/معادل postfix در عبارت محاسباتی!ab+cd-*ef+/

اسلاید 268: Traversal Applicationsabcdefghij

اسلاید 269: Level OrderLet t be the tree root.while (t != null){ visit t and put its children on a FIFO queue; remove a node from the FIFO queue and call it t;}

اسلاید 270: Level-Order Example (visit = print)abcdefghijabcdefghij

اسلاید 271: Some Examplespreorder = abababinorder = abbaabpostorder = abbabalevel order = ababab

اسلاید 272: Preorder And Postorderpreorder = abababpostorder = ba

اسلاید 273: Inorder And Preorderinorder = g d h b e i a f j cpreorder = a b d g h e i c f jagdhbeifjc

اسلاید 274: Inorder And Preorderpreorder = a b d g h e i c f jb ریشه بعدی است/ gdh زیر درخت چپ / ei زیر درخت راست agdhbeifjcagdhfjcbei

اسلاید 275: Inorder And Preorderpreorder = a b d g h e i c f jd ریشه بعدی می باشد./g زیر درخت چپ/وhزیر درخت راست می باشد.agdhfjcbeiagfjcbeidh

اسلاید 276: Inorder And Postorderدر level orderپیمایش از چپ به راست می باشددر Post orderپیمایش از راست به چپ می باشد. inorder = g d h b e i a f j c postorder = g h d i e b j f c aTree root is a; gdhbei // زیر درخت چپfjc // زیردرخت راست

اسلاید 277: Inorder And Level Orderدر level orderپیمایش از چپ به راست می باشد. inorder = g d h b e i a f j c level order = a b c d e f g h i jTree root is a;gdhbei // زیر درخت چپfjc // زیردرخت راست

اسلاید 278: Priority Queuesدونوع صف اولویت دار تعریف می کنیم:صف با الویت بالاصف با الویت پایین

اسلاید 279: Min Priority Queueیک مجموعه از عناصر میباشد.برای هر عنصر یک کلید اولویت تعریف می کنیم. اعمال زیر را می توان روی آن انجام داد.چک کردن اینکه صف خالی است یا نه؟سایز و اندازه صفاضافه کردن یک عنصر به لیستپیدا کردن عنصر با کمترین اولویتحذف عنصری با کمترین اولویت

اسلاید 280: Max Priority Queueیک مجموعه از عناصر میباشد.برای هر عنصر یک کلید اولویت تعریف می کنیم. اعمال زیر را می توان روی آن انجام داد.چک کردن اینکه صف خالی است یا نه؟سایز و اندازه صفاضافه کردن یک عنصر به لیستپیدا کردن عنصر با بیشترین اولویتحذف عنصری با بیشترین اولویت

اسلاید 281: Complexity Of Operationsدو نمونه خوب می توان از heaps leftist و leftist trees نام برد. isEmpty, size, and get => O(1) timeput and remove => O(log n) time که در آن n طول لیست می باشد

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

اسلاید 283: Sorting Exampleمرتب کنیدپنج عنصری که کلید های آن به این قرار باشد: 6, 8, 2, 4, 1از صف با الویت بالا استفاده کنید.ابتدا عناصر را در یک صف ب الویت بالا قرار دهیدپنج مرتبه عمل حذف را انجام دهید در نهایت عناصر از راست به چپ مرتب می شوند.

اسلاید 284: After Putting Into Max Priority QueueSorted Array 68241صف با الویت بالا

اسلاید 285: After First Remove Max OperationSorted Array 62418صف با الویت بالا

اسلاید 286: After Second Remove Max OperationSorted Array 24186صف با الویت بالا

اسلاید 287: After Third Remove Max OperationSorted Array 21864صف با الویت بالا

اسلاید 288: After Fourth Remove Max OperationSorted Array 18642صف با الویت بالا

اسلاید 289: After Fifth Remove Max OperationSorted Array 86421صف با الویت بالا

اسلاید 290: Complexity Of Sortingمرتب سازی nعنصرn put operations => O(n log n) time.n remove max operations => O(n log n) time.total time is O(n log n).compare with O(n2)

اسلاید 291: Heap Sortکاربرد صف با الویت بالا در heap دیده می شود.این مرتب سازی با O(n) قابل انجام است.

اسلاید 292: Min Tree Definitionهر درختی دارای value یا یک مقدار می باشدMin tree:درختی است که در آن valueریشه از value تمام زیر درختها با فرزندانش کمتر باشد.

اسلاید 293: Min Tree Example249348799ریشه کمترین مقدار را دارد

اسلاید 294: Max Tree Example949842731ریشه بیشترین مقدار را دارد

اسلاید 295: Min Heap Definitionدرخت باینری کاملmin tree

اسلاید 296: Min Heap With 9 Nodesدرخت کامل با 9 گره

اسلاید 297: Min Heap With 9 Nodesدرخت کامل با 9 گره وهمچنین min tree246793863

اسلاید 298: Max Heap With 9 Nodesدرخت کامل با 9 گره وهمچنین max tree986726517

اسلاید 299: Heap HeightHeap درختی کامل می باشد که ارتفاع ان log2 (n+1).است

اسلاید 300: 987672651123456789100A Heap Is Efficiently Represented As An Array986726517

اسلاید 301: Moving Up And Down A Heap986726517123456789

اسلاید 302: Putting An Element Into A Max Heapدرخت کامل با 10 گره9867265177

اسلاید 303: Putting An Element Into A Max Heap 5گره جدید می باشد98672651775

اسلاید 304: Putting An Element Into A Max Heap20 گره جدید می باشد98672651777

اسلاید 305: Putting An Element Into A Max Heap20 گره جدید می باشد98672651777

اسلاید 306: Putting An Element Into A Max Heap20 گره جدید می باشد98672651777

اسلاید 307: Putting An Element Into A Max Heap20 گره جدید می باشد9867265177720

اسلاید 308: Putting An Element Into A Max Heapدرخت کامل با 11 گره9867265177720

اسلاید 309: Putting An Element Into A Max Heap15 گره جدید می باشد9867265177720

اسلاید 310: Putting An Element Into A Max Heap15 گره جدید می باشد98672651777208

اسلاید 311: Putting An Element Into A Max Heap15 گره جدید می باشد8672651777208915

اسلاید 312: Complexity Of Putپیچیدگی آن O(log n) زمانیکه سایز heap مقدار n باشد8672651777208915

اسلاید 313: Removing The Max Elementبزرگترین مقدلر در ریشه قرار دارد.8672651777208915

اسلاید 314: Removing The Max Elementپس از آنکه بزرگترین مقدار حذف شد86726517778915

اسلاید 315: Removing The Max Elementدر heap تعداد10 عنصر قرار می گیرد.867265177789158 را به heap اضافه کنید.

اسلاید 316: Removing The Max Element672651777915

اسلاید 317: Removing The Max Element672651777915

اسلاید 318: Removing The Max Element6726517779158

اسلاید 319: Removing The Max Element15 بزرگترین عنصر قرار می گیرد.6726517779158

اسلاید 320: Removing The Max Elementپس از آنکه بزرگترین مقدار حذف شد67265177798

اسلاید 321: Removing The Max Elementاکنون در heap تعداد9 عنصر قرار می گیرد.67265177798

اسلاید 322: Removing The Max Element62651798

اسلاید 323: Removing The Max Element62651798

اسلاید 324: Removing The Max Element626517987

اسلاید 325: Complexity Of Remove Max Elementپیچیدگی = O(log n)626517987

اسلاید 326: Initializing A Max Heapinput array = [-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]8476789371011152

اسلاید 327: Initializing A Max Heapابتدا موقعیت n/2 را در آرایه فوق محاسبه کرده و سپس از آن گره در درخت شروع کنید 8476789371011152

اسلاید 328: Initializing A Max HeapMax heap بودن را در درخت چک کنید.در درخت max heapمحتوای ریشه از کلیه عناصر آن بزرگتر می باشد.8476789371015112

اسلاید 329: Initializing A Max Heap8476789371015112

اسلاید 330: Initializing A Max Heap8976784371015112

اسلاید 331: Initializing A Max Heap8976784371015112

اسلاید 332: Initializing A Max Heap8976384771015112

اسلاید 333: Initializing A Max Heap8976384771015112

اسلاید 334: Initializing A Max Heap897638477101511مکان 11 با 2 عوض می شود.

اسلاید 335: Initializing A Max Heap8976384775111مکان 10 با 2 عوض می شود.10

اسلاید 336: Initializing A Max Heap8976384772111105

اسلاید 337: Initializing A Max Heap8976384772111105مکان 1را بیابید؟

اسلاید 338: 11Initializing A Max Heap8976384772105یافتن مکان 1

اسلاید 339: Initializing A Max Heap897638477211105یافتن مکان 1

اسلاید 340: Initializing A Max Heap897638477211105یافتن مکان 1

اسلاید 341: Initializing A Max Heap897638477211105انجام شد.1

اسلاید 342: Time Complexity8763477101152981ارتفاع درخت heap = hتعداد زیر درخت ها با ریشه در level j 2 j-1=پیچیدگی زمانی برای هر زیر درخت = O(h-j+1)

اسلاید 343: Complexityپیچیدگی زمانی برای زیر درخت سطح 2j-1(h-j+1) = t(j) <= j زمان کل= t(1) + t(2) + … + t(h-1) = O(n)

اسلاید 344: Extended Binary Treesیک درخت باینری را در نظر بگیریدو اضافه کنید یک نود خارجی هر جایی زیر درخت نداشته باشد.به همین دلیل به آن درخت باینری گسترش یافته می گویند.

اسلاید 345: A Binary Tree

اسلاید 346: An Extended Binary Treeتعداد گره های خارجی = n+1

اسلاید 347: The Function s()برای هر گره x در درخت باینری گسترش یافته با استفاده از تابع s(x) قادریم:طول کوتاهترین مسیر از x به گره خارجی در زیر درخت های ریشه محاسبه کرد.

اسلاید 348: s() Values Example

اسلاید 349: Binary Search TreesDictionary Operations:get(key)put(key, value)remove(key)Additional operations:ascend()get(index) (اندیس گره در درخت باینری را برمی گرداند.)remove(index) (کند محتوای اندیس در درخت باینری را حذف می)

اسلاید 350: Complexity Of Dictionary Operations get(), put() and remove()

اسلاید 351: Complexity Of Other Operations ascend(), get(index), remove(index)D is number of buckets

اسلاید 352: Definition Of Binary Search Treeدر یک درخت باینریهر گره دارای (key, value) میباشد.برای هر گره دلخواه x کلیه عناصر زیر درخت چپ آن کوچکتر از آن وکلیه عناصر زیر درخت راست آن بزرگتر از آن می باشد.

اسلاید 353: Example Binary Search Tree201062815403025فقط کلید ها را نشان داده است.

اسلاید 354: The Operation ascend()201062815403025پیمایش میانوندی آن با O(n) امکا ن پذیر است.

اسلاید 355: The Operation get()201062815403025پیچیدگی = O(height) = O(n(

اسلاید 356: The Operation put()201062815403025Put 35.35

اسلاید 357: The Operation put()Put 7.201062815403025357

اسلاید 358: The Operation put()201062815403025Put 18.35718

اسلاید 359: The Operation put()201062815403025پیچیدگی <= put() = O(height).35718

اسلاید 360: The Operation remove() گره در وضعیت های: اگر گره برگ باشداگر گره از درجه یک باشد.اگر گره از درجه دو باشد

اسلاید 361: Remove From A Leafحذف گره برگ = 720106281540302535718

اسلاید 362: Remove From A Leaf (contd.)حذف گره برگ = 3520106281540302535718

اسلاید 363: Remove From A Degree 1 Nodeحذف گره تک فرزندی = 4020106281540302535718

اسلاید 364: Remove From A Degree 1 Node (contd.)حذف گره تک فرزندی = 1520106281540302535718

اسلاید 365: Remove From A Degree 2 Nodeحذف گره دو فرزندی = 1020106281540302535718

اسلاید 366: Remove From A Degree 2 Node201062815403025جابه جا کنید با بزرگترین در زیر درخت چپ ویا با کوچکترین در زیر درخت راست.35718

اسلاید 367: Remove From A Degree 2 Node201062815403025جابه جا کنید با بزرگترین در زیر درخت چپ ویا با کوچکترین در زیر درخت راست.35718

اسلاید 368: Remove From A Degree 2 Node20862815403025جابه جا کنید با بزرگترین در زیر درخت چپ ویا با کوچکترین در زیر درخت راست.35718

اسلاید 369: Remove From A Degree 2 Node20862815403025بزرگترین کلید یا باید برگ باشد یا گره تک فرزندی35718

اسلاید 370: Another Remove From A Degree 2 Nodeحذف گره دو فرزندی 20 =20106281540302535718

اسلاید 371: Remove From A Degree 2 Node201062815403025جابه جا کنید با بزرگترین در زیر درخت چپ35718

اسلاید 372: Remove From A Degree 2 Node201062815403025جابه جا کنید با بزرگترین در زیر درخت چپ35718

اسلاید 373: Remove From A Degree 2 Node181062815403025جابه جا کنید با بزرگترین در زیر درخت چپ35718

اسلاید 374: Remove From A Degree 2 Node181062815403025پیچیدگی = O(height).357

اسلاید 375: Indexed Binary Search Treeجستجوی باینریدر هر نود یک فیلد اضافی وجود دارد:leftSize= شمارش تعداد نود های چپ درخت

اسلاید 376: Example Indexed Binary Search Tree20106281540302535718001140070013leftSize =red

اسلاید 377: leftSize And RankRank =موقعیت عناصر در inorder (inorder = مرتب کلید ها به صورت صعودی).[2,6,7,8,10,15,18,20,25,30,35,40]rank(2) = 0rank(15) = 5rank(20) = 7leftSize(x) = rank(x)

اسلاید 378: leftSize And Rank20106281540302535718001140070013sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]

اسلاید 379: get(index) And remove(index)72010628154030253571800114000013sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]

اسلاید 380: get(index) And remove(index)if index = x.leftSize x.element را انتخاب کن .if index < x.leftSize عنصری انتخاب می شود که محتوای index آن در زیر درخت چپ xمی باشد.if index > x.leftSizeعنصری انتخاب می شودکه محتوای (index - x.leftSize-1) آن در زیر درخت راست xمی باشد.

اسلاید 381: Linear List As Indexed Binary Treehebadfljikcg001140070013list = [a,b,c,d,e,f,g,h,i,j,k,l]

اسلاید 382: add(5,’m’)hebadfljikcg001140070013list = [a,b,c,d,e,f,g,h,i,j,k,l]

اسلاید 383: add(5,’m’)hebadfljikcg001140070013list = [a,b,c,d,e, m,f,g,h,i,j,k,l]find node with element 4 (e)

اسلاید 384: add(5,’m’)hebadfljikcg001140070013list = [a,b,c,d,e, m,f,g,h,i,j,k,l]find node with element 4 (e)

اسلاید 385: add(5,’m’)hebadfljikcg001140070013m را به راست گره e اضافه کرده استدر نتیجه زیر درخت راست e به عنوان زیر درخت راست mقرار می گیرد. m

اسلاید 386: add(5,’m’)hebadfljikcg001140070013mرا بعنوان فرزند چپ در زیر درخت راست گره e قرار دهید.m

اسلاید 387: add(5,’m’)پیچیدگی = O(height)