Dissertations / Theses on the topic 'Binary Search Trees'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 21 dissertations / theses for your research on the topic 'Binary Search Trees.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
INAGAKI, Yasuyoshi, Tomio HIRATA, and Xuehou TAN. "Designing Efficient Geometric Search Algorithms Using Persistent Binary-Binary Search Trees." Institute of Electronics, Information and Communication Engineers, 1994. http://hdl.handle.net/2237/15061.
Full textHarmon, Dion (Dion Kane). "New bounds on optimal binary search trees." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/34268.
Full textThis electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Includes bibliographical references (p. 153-156).
Binary search trees (BSTs) are a class of simple data structures used to store and access keys from an ordered set. They have been around for about half a century. Despite their ubiquitous use in practical programs, surprisingly little is known about their optimal performance. No polynomial time algorithm is known to compute the best BST for a given sequence of key accesses, and before our work, no o(log n)-competitive online BST data structures were known to exist. In this thesis, we describe tango trees, a novel O(log log n)-competitive BST algorithm. We also describe a new geometric problem equivalent to computing optimal offline BSTs that gives a number of interesting results. A greedy algorithm for the geometric problem is shown to be equivalent to an offline BST algorithm posed by Munro in 2000. We give evidence that suggests Munro's algorithm is dynamically optimal, and strongly suggests it can be made online. The geometric model also lets us prove that a linear access algorithm described by Munro in 2000 is optimal within a constant factor. Finally, we use the geometric model to describe a new class of lower bounds that includes both of the major earlier lower bounds for the performance of offline BSTs, and construct an optimal bound in this new class.
by Dion Harmon.
Ph.D.
Goudjil, Amar. "Data structures, binary search trees, a study of random Weyl trees." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0026/MQ50778.pdf.
Full textGoudjil, Amar. "Data structures, binary search trees : a study of random Weyl trees." Thesis, McGill University, 1998. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=21559.
Full textHolmgren, Cecilia. "Random Records and Cuttings in Binary Search Trees." Licentiate thesis, Uppsala universitet, Analys och tillämpad matematik, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-141580.
Full textManthey, Bodo. "Approximability of cycle covers and smoothed analysis of binary search trees." [S.l.] : [s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=978602366.
Full textKozma, László [Verfasser], and Raimund [Akademischer Betreuer] Seidel. "Binary search trees, rectangles and patterns / László Kozma ; Betreuer: Raimund Seidel." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2016. http://d-nb.info/1114735019/34.
Full textSayed, Hassan Adelyar. "The Complexity of Splay Trees and Skip Lists." Thesis, University of the Western Cape, 2008. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_6858_1263424080.
Full textOur main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists.
Holmgren, Cecilia. "Split Trees, Cuttings and Explosions." Doctoral thesis, Uppsala universitet, Matematiska institutionen, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-112239.
Full textLove, Lorna. "The suffix binary search tree." Thesis, University of Glasgow, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.270960.
Full textSedlář, František. "Algoritmy pro vyhledání nejdelšího shodného prefixu." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2013. http://www.nusl.cz/ntk/nusl-236363.
Full textAmri, Anis. "Autour de quelques statistiques sur les arbres binaires de recherche et sur les automates déterministes." Thesis, Université de Lorraine, 2018. http://www.theses.fr/2018LORR0301.
Full textThis Phd thesis is divided into two independent parts. In the first part, we provide an asymptotic analysis of some statistics on the binary search tree. In the second part, we study the coupon collector problem with a constraint. In the first part, following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyze the following statistics : the weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search procees, the weighted path length, the weighted Wiener index and the weighted depths of nodes with at most one child in a random binary search tree. In the second part, we study the asymptotic shape of the completion curve of the collection conditioned to T_n≤ (1+Λ), Λ>0, where T_n≃n lnn is the time needed to complete accessible automata, we provide a new derivation of a formula due to Korsunov [Kor78, Kor86]
Rosati, Matteo. "Decoding protocols for classical communication on quantum channels." Doctoral thesis, Scuola Normale Superiore, 2017. http://hdl.handle.net/11384/85834.
Full textAmri, Anis. "Autour de quelques statistiques sur les arbres binaires de recherche et sur les automates déterministes." Electronic Thesis or Diss., Université de Lorraine, 2018. http://www.theses.fr/2018LORR0301.
Full textThis Phd thesis is divided into two independent parts. In the first part, we provide an asymptotic analysis of some statistics on the binary search tree. In the second part, we study the coupon collector problem with a constraint. In the first part, following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyze the following statistics : the weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search procees, the weighted path length, the weighted Wiener index and the weighted depths of nodes with at most one child in a random binary search tree. In the second part, we study the asymptotic shape of the completion curve of the collection conditioned to T_n≤ (1+Λ), Λ>0, where T_n≃n lnn is the time needed to complete accessible automata, we provide a new derivation of a formula due to Korsunov [Kor78, Kor86]
Кучмій, О. О. "Реалізація телефонного довідника на структурах даних "зв’язний список" та "дерево пошуку"." Master's thesis, Сумський державний університет, 2018. http://essuir.sumdu.edu.ua/handle/123456789/72256.
Full textHung, Ling-Ju, and 洪綾珠. "Range Search Trees and the Maximum Agreement Subtree Problem on Binary Trees." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/92764435021626808896.
Full text國立中正大學
資訊工程研究所
91
An evolutionary tree is a rooted tree. Each internal node of evolutionaty trees has at least two children and the leaves are labelled with distinct symbols representing species. Constructing evolutionary trees for species sets is a fundamental work in computing biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in used. Different methods may lead to different trees for the same species. The resulting trees should be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study one formalization of the problem: the maximum agreement subtree(MAST) problem. The MAST problem is as follow: given a set L and T = {T1, T2, . . . , Tk}, a profile of rooted trees with leaf-labelled by the elements of L and T1 is a 2-d tree, find a maximum cardinality subset X of L such that the topological restrictions of T1, T2, . . . , Tk are isomorphic. In this paper, we use the range search tree method to implement Bryant's[17] algorithm. The overall running time of the algorithm under our data structure is O(n2 logk n) and improving the original algorithm which runs in O(kn3).
Lo, Wei-En, and 羅偉恩. "Fast Binary Search Packet Classification Based On Decision Trees." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/19616735166327089505.
Full text國立成功大學
資訊工程學系碩博士班
96
With the rapid growth of internet requirement and the occurrence of network applications, backbone routers nowadays need to classify packets into flows in a short time. In this paper, we propose a new algorithm called fast binary search packet classification to improve the efficiency on both search speed and the memory storage. In our algorithm, we first partition the filter table with decision tree but process a binary search on leaf nodes instead of the traditional tree traversal. We use a hash- based bit selecting strategy to replace the range cutting method in order to reduce memory usage and the impact caused by unbalance environment. Our algorithm can be implemented in two schemes. Variable-selected-bit scheme chooses different bit on each node and thus has better memory utilization. Fixed-selected-bit scheme chooses same bit on each node in the same level in order to reduce the packet encoding time and then increase the search speed. At last we compare our algorithm with two well-known algorithm － HiCuts and HyperCuts. Result shows that variable- selected-bit scheme has better performance on memory usage in all kinds of filter tables than others; another fixed-selected-bit scheme performs 20% better than HiCuts on search in filter tables with uniform distribution and even more than 50% better in an unbalance environment.
Manthey, Bodo [Verfasser]. "Approximability of cycle covers and smoothed analysis of binary search trees / Bodo Manthey." 2005. http://d-nb.info/978602366/34.
Full textArchibald, Margaret Lyn. "Combinatorial problems related to sequences with repeated entries." Thesis, 2006. http://hdl.handle.net/10539/1732.
Full textSequences of numbers have important applications in the field of Computer Science. As a result they have become increasingly regarded in Mathematics, since analysis can be instrumental in investigating algorithms. Three concepts are discussed in this thesis, all of which are concerned with ‘words’ or ‘sequences’ of natural numbers where repeated letters are allowed: • The number of distinct values in a sequence with geometric distri- bution In Part I, a sample which is geometrically distributed is considered, with the objective of counting how many different letters occur at least once in the sample. It is concluded that the number of distinct letters grows like log n as n → ∞. This is then generalised to the question of how many letters occur at least b times in a word. • The position of the maximum (and/or minimum) in a sequence with geometric distribution Part II involves many variations on the central theme which addresses the question: “What is the probability that the maximum in a geometrically distributed sample occurs in the first d letters of a word of length n?” (assuming d ≤ n). Initially, d is considered fixed, but in later chapters d is allowed to grow with n. It is found that for 1 ≤ d = o(n), the results are the same as when d is fixed. • The average depth of a key in a binary search tree formed from a sequence with repeated entries Lastly, in Part III, random sequences are examined where repeated letters are allowed. First, the average left-going depth of the first one is found, and later the right-going path to the first r if the alphabet is {1, . . . , r} is examined. The final chapter uses a merge (or ‘shuffle’) operator to obtain the average depth of an arbitrary node, which can be expressed in terms of the left-going and right-going depths.
Huang, Jung-Rong, and 黃俊榮. "Nonblocking Concurrent Binary Search Tree for Shared-Memory Multiprocessor." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/26538015162393547626.
Full text國立交通大學
資訊工程系
87
Binary search tree is often used in operating system, database system and graph algorithm. Nonblocking algorithm guarantees that some process will complete its operation within a finite number of steps in the system. The nonblocking algorithm, in contrast to the traditional lock-based algorithm, enjoys higher concurrency and fault-tolerance. In this thesis, we propose a nonblocking concurrent binary search tree algorithm. In order to maintain the data integrity in the course of concurrent insert and delete, we use the auxiliary node in the tree structure. The algorithm maintains binary search tree property without locking. Finally, we prove the correctness of our algorithms.
TingHuang, Po, and 黃柏庭. "Fast Decision Tree based Binary Search scheme for Packet Classification." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/53485088418884059817.
Full text