المشاركات

الفصل الثاني عشر

صورة
Binary Search Trees مقدمة في الفصل العاشر والحادي عشر اتعرضنا لاكتر من data structure , في الفصل العاشر اتعرضنا ل data structures بدائية أو بسيطة زي ال Array وال Stack وال Queue وال Linked List , وفي الفصل الحادي عشر اتعرضنا ل data structure أكثر تعقيدا وهي ال Hash Table , في الفصل ده ان شاء الله هنتعرض ل data structure شايفها أبسط من ال Hash Table وهي ال Binary Search Tree وهنختصرها ب BST , ال BST هي data structure بتدعم عمليات كتير , ممكن نقسم العمليات دي لقسمين كالعادة , أول قسم هو ال query operations ودي العمليات اللي بتستعلم عن البيانات بدون تعديل أي حاجة زي ال search وال maximum وال minimum وال successor وال predecessor , والقسم التاني هو ال maintaining operations ودي العمليات اللي بتعدل في البيانات الموجودة في ال tree زي ال insertion وال deletion , علشان ال BST بتدعم كل العمليات دي فبيعتبروها Dictionary و Priority Queue في نفس الوقت (ال Priority Queue اتشرحت في الفصل السادس) , لو فيه حاجة في العمليات دي غريبة عليك ارجع لمقدمة الباب ا

الفصل الحادي عشر

صورة
Hash Tables مقدمة اتعرضنا في الفصل العاشر لأبسط Data Structures وعرفنا ايه هي العمليات اللي بنحتاج ننفذها على ال Data Structures دي اللي هي ال Insertion وال Deletion وال Search . وعرفنا ان أي Data Structure بتنفذ ال 3 عمليات دول بتسمى Dictionary . معظم ال Data Structures مش بتبقى المشكلة في ال Insertion ولا في ال Deletion .. دي عمليات Data Structures كتير ممكن تنفذها في O(1) في ال Worst Case زي مثلا ال Doubly Linked List كمثال . المشكلة دايما في ال Search اللي معظم ال Data Structures بتنفذها في O(n) في ال Worst Case .. النهاردة هنتعرض لل Hash Tables ودي Data Structure بتمكنا من تنفيذ ال Insertion وال Deletion وال Search في O(1) في ال Average (Expected) case وتحت شروط معينة نقدر نوصل ل O(1) في ال Worst Case. ال Hash Table هو Generalization لفكرة ال Array بس علشان نفهم المعلومة دي كويس عايزين نشوف ال Array بنظرة مختلفة شوية .. مبدأيا ميزة ال Array في ال Direct Addressing .. أو القدرة على اننا ن access عنصر في ال array في O(1) وده بسبب وج