Simulation expirment for proofing the theoretical as-sumption of time complexity for binary search tree
Other Title(s)
تجربة محاكاة لبرهنة الافتراض النظري لتعقيدات الوقت للبحث الثنائي الشجري
Author
Source
Ibn al-Haitham Journal for Pure and Applied Science
Issue
Vol. 27, Issue 2 (30 Jun. 2014), pp.251-259, 9 p.
Publisher
University of Baghdad College of Education for Pure Science / Ibn al-Haitham
Publication Date
2014-06-30
Country of Publication
Iraq
No. of Pages
9
Main Subjects
Abstract AR
لطالما تم التأكيد أن تطبيق تقنية البحث الثنائي الشجري لمعالجة مجموعة ما له أفضلية على تطبيق تقنية القائمة الموصولة، إذ أنه في البحث الشجري الثنائي المتوازن فإن معدل وقت البحث (للتحري عن وجود عنصر معين في المجموعة) هو O (log N) للأساس 2 إذ N هو عدد العناصر في الشجرة أو حجم الشجرة.
هذا البحث يقدم تجربة لقياس و مقارنة وقت البحث الثنائي الشجري المستحصل مع الوقت المتوقع (نظريا)،هذه التجربة العملية أثبتت صحة الفرضية، نفذت هذه التجربة باستخدام برنامج تربو باسكال مع تطبيق تقنية الاستدعاء الذاتي، و استخدام طريقة احصائية لإثبات الفرضية أعلاه، تم تقدير وقت البحث بوساطة عدد المقارنات المطلوبة.
Abstract EN
It is frequently asserted that an advantage of a binary search tree implementation of a set over linked list implementation is that for reasonably well balanced binary search trees the average search time (to discover whether or not a particular element is present in the set) is O (log N) to the base 2 where N is the number of element in the set (the size of the tree).
This paper presents an experiment for measuring and comparing the obtained binary search tree time with the expected time (theoretical), this experiment proved the correctness of the hypothesis, the experiment is carried out using a program in turbo Pascal with recursion technique implementation and a statistical method to prove the above hypothesis.
Search time is estimated by the number of comparisons needed.
American Psychological Association (APA)
Salih, Muna Mahdi. 2014. Simulation expirment for proofing the theoretical as-sumption of time complexity for binary search tree. Ibn al-Haitham Journal for Pure and Applied Science،Vol. 27, no. 2, pp.251-259.
https://search.emarefa.net/detail/BIM-545725
Modern Language Association (MLA)
Salih, Muna Mahdi. Simulation expirment for proofing the theoretical as-sumption of time complexity for binary search tree. Ibn al-Haitham Journal for Pure and Applied Science Vol. 27, no. 2 (2014), pp.251-259.
https://search.emarefa.net/detail/BIM-545725
American Medical Association (AMA)
Salih, Muna Mahdi. Simulation expirment for proofing the theoretical as-sumption of time complexity for binary search tree. Ibn al-Haitham Journal for Pure and Applied Science. 2014. Vol. 27, no. 2, pp.251-259.
https://search.emarefa.net/detail/BIM-545725
Data Type
Journal Articles
Language
English
Notes
Includes appendices : p. 255-258
Record ID
BIM-545725