<p> This investigation examines several methods designed to minimize the computational cost of retrieving records from a binary search tree.</p> <p> No knowledge of the probabilities with which these records are requested is assumed. The aim of each method is to gradually restructure an initial, arbitrary (and perhaps costly) tree into one which has minimal search cost, on the basis of experience.</p> <p> While no one such 'self-organizing' method has yet received theoretical substantiation, it is hoped that this empirial investigation may assist in this endeavour.</p> / Thesis / Master of Science (MSc)

Student Number : 9708525G - PhD thesis - School of Mathematics - Faculty of Science / Sequences 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.

<p>Our 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.</p>

No description available.

<p>Our 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.</p>

Magister Scientiae - MSc / Our 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. / South Africa

Magister Curationis / Binary search trees (BSTs) are important data structures which are widely used in various guises. Splay trees are a specific kind of binary search tree, one without explicit balancing. Skip lists use more space than BSTs and are related to them in terms of much of their run-time behavior. Even though binary search trees have been used for about half a century, there are still many open questions regarding their run-time performance and algorith mic complexity. In many instances, their worst-case, average-case, and best-case behaviors are unknown and need further research. Our analysis provides a basis for selecting more suitable data structures and algorithms for specific processes and applications. We contrast the empirical behavior of splay trees and skip lists with their theoretical behavior. In particular we explore when splay trees outperform skip lists and vice versa. The performance of a splay tree depends on the history of accesses to its el ements. On the other hand, the performance of a skip list depends on an indepen dent randomization of the height of links that lead to specific elements. Therefore, probabilistic methods are used to analyze the operation of splay trees and skip lists. Our 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.

This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”. In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees. In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees. In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution. In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to de­scribe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immi­gration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.

In this thesis we compared some variants of binary search trees that approach dynamic optimality: Tango trees, Multisplay trees, and Splay trees. We empirically tested the behavior of these three types of trees, as well as Red-Black trees. We measured the amount of visited nodes per operation and running time on real hardware. We proved that Tango trees and Multisplay trees are in most cases less efficient than Splay trees and Red-Black trees. Cache-related effects played a surprisingly large part in the behavior of Red-Black tree and Splay tree. 1

Cette thèse comporte deux parties indépendantes. Dans la première partie, nous nous intéressons à l’analyse asymptotique de quelques statistiques sur les arbres binaires de recherche (ABR). Dans la deuxième partie, nous nous intéressons à l’étude du problème du collectionneur de coupons impatient. Dans la première partie, en suivant le modèle introduit par Aguech, Lasmar et Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], on définit la profondeur pondérée d’un nœud dans un arbre binaire enraciné étiqueté comme la somme de toutes les clés sur le chemin qui relie ce nœud à la racine. Nous analysons alors dans ABR, les profondeurs pondérées des nœuds avec des clés données, le dernier nœud inséré, les nœuds ordonnés selon le processus de recherche en profondeur, la profondeur pondérée des trajets, l’indice de Wiener pondéré et les profondeurs pondérées des nœuds avec au plus un enfant. Dans la deuxième partie, nous étudions la forme asymptotique de la courbe de la complétion de la collection conditionnée à T_n≤ (1+Λ), Λ>0, où T_n≃n ln⁡n désigne le temps nécessaire pour compléter la collection. Puis, en tant qu’application, nous étudions les automates déterministes et accessibles et nous fournissons une nouvelle dérivation d’une formule due à Korsunov [Kor78, Kor86] / This 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 ln⁡n is the time needed to complete accessible automata, we provide a new derivation of a formula due to Korsunov [Kor78, Kor86]