Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 37 for “"Binary Search Tree"”.

  1. Lock-free Self-adjusting Binary Search Tree

    A binary search tree (BST) is a fundamental data structure for maintaining data in a way to allow fast search. As multi-core processors are widely used nowadays, such data structures require the ability to handle concurrent accesses to exploit the concurrent hardware. There are several algorithms …

    unlv Repository record for Lock-free Self-adjusting Binary Search Tree (opens in a new tab) Download PDF for Lock-free Self-adjusting Binary Search Tree (opens in a new tab)

  2. Self-stabilizing binary search tree maintenance algorithm

    Binary search tree is one of the most studied data structures. The main application of the binary search tree is in implementing efficient search operations. A binary search tree is a special binary tree which satisfies the property that for every processor p in the binary tree, the values of all …

    unlv Repository record for Self-stabilizing binary search tree maintenance algorithm (opens in a new tab) Download PDF for Self-stabilizing binary search tree maintenance algorithm (opens in a new tab)

  3. Formal verification of a concurrent binary search tree

    … version of the non-blocking linearizable binary search tree of Ellen et al., which appeared in the Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (pages 131-140), using the PVS specification and verification system. The algorithm and its specification …

    york Repository record for Formal verification of a concurrent binary search tree (opens in a new tab)

  4. An Investigation and Implementation of Some Binary Search Tree Algorithms

    … documents the results of an investigation into binary search trees. Because of their favourable characteristics binary search trees have become popular for information storage and retrieval applications in a one level store. The trees may be of two types, weighted and unweighted. Various …

    mcmaster Repository record for An Investigation and Implementation of Some Binary Search Tree Algorithms (opens in a new tab)

  5. Self Adjusting Contention Friendly Concurrent Binary Search Tree by Lazy Splaying

    … a partial blocking implementation of concurrent binary search tree data structure that is contention friendly, fast and scales well. It uses a technique, called lazy splaying to move frequently accessed items close to the root without making the root of the tree a sequential bottleneck. Most of …

    unlv Repository record for Self Adjusting Contention Friendly Concurrent Binary Search Tree by Lazy Splaying (opens in a new tab) Download PDF for Self Adjusting Contention Friendly Concurrent Binary Search Tree by Lazy Splaying (opens in a new tab)

  6. Approximately Optimum Search Trees in External Memory Models

    … and near optimal solutions to the classic binary search tree problem of Knuth. We are given a set of n keys (originally known as words), B_1, B_2, ..., B_n and 2n+1 frequencies. {p_1, p_2, ..., p_n} represent the probabilities of searching for each given key, and {q_0, q_1, ..., q_n} …

    waterloo Repository record for Approximately Optimum Search Trees in External Memory Models (opens in a new tab)

  7. An Investigation of Some New Tree Structures

    <p>A study of the tree structures developed by Finkel and Bentley (3 & 4) was done and the results are documented in this report. These tree structures, i.e. the quad tree and the k-d tree, were especially developed for associative retrieval. A comparison of the above tree structures and the well …

    mcmaster Repository record for An Investigation of Some New Tree Structures (opens in a new tab)

  8. On Lock-Free Data Structures for Dynamic Sets and Their Amortized Step Complexities

    … for dynamic sets, supporting Insert, Delete, and Search operations. Lock-free data structures can be difficult to analyze because operations may run forever. In an amortized analysis of these data structures, we consider the number of steps taken in an execution consisting of a sequence …

    toronto-retro Repository record for On Lock-Free Data Structures for Dynamic Sets and Their Amortized Step Complexities (opens in a new tab)

  9. An Investigation of Self-Organizing Binary Search Trees

    … 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 …

    mcmaster Repository record for An Investigation of Self-Organizing Binary Search Trees (opens in a new tab)

  10. Concurrent Localized Wait-Free Operations on a Red Black Tree

    A red-black tree is a type of self-balancing binary search tree. Some wait-free algorithms have been proposed for concurrently accessing and modifying a red-black tree from multiple threads in shared memory systems. Most algorithms presented utilize the concept of a "window", and are entirely …

    unlv Repository record for Concurrent Localized Wait-Free Operations on a Red Black Tree (opens in a new tab) Download PDF for Concurrent Localized Wait-Free Operations on a Red Black Tree (opens in a new tab)

  11. The Stylist: a Pascal program for analyzing prose style

    … using a new data structure called a Concordance Search Tree (CST). A CST is a binary search tree with a linked list threaded through it recording the order of the used of each word. An inorder traversal of the tree, with a traversal of the linked list during each visit, creates a concordance. …

    nps Repository record for The Stylist: a Pascal program for analyzing prose style (opens in a new tab)

  12. DEVELOPING A GAME FOR UNDERGRADUATE CS STUDENTS TO LEARN DATA STRUCTURES

    … exhibited by the fundamental concepts. The Binary Search Tree is cited as one of<br/>the most challenging data structures to learn.<br/>To address the challenges faced by students, this research proposes the use of gamification in education, which involves incorporating game elements into …

    openu Repository record for DEVELOPING A GAME FOR UNDERGRADUATE CS STUDENTS TO LEARN DATA STRUCTURES (opens in a new tab) Download PDF for DEVELOPING A GAME FOR UNDERGRADUATE CS STUDENTS TO LEARN DATA STRUCTURES (opens in a new tab)

  13. Concurrent Data Structures Using Multiword Compare and Swap

    … the performance of concurrent data structures, researchers have turned to highly complex fine-grained techniques. Resulting algorithms are often extremely difficult to understand and prove correct, allowing for highly cited works to contain correctness bugs that go undetected for long periods of …

    waterloo Repository record for Concurrent Data Structures Using Multiword Compare and Swap (opens in a new tab)

  14. Group Operations for Concurrent Binary Search Trees

    … operation might look up 10 different keys in a binary search tree, returning 10 results. Chen et al introduced group prefetching, an optimization for group operations on linked data structures that improves throughput by overlapping memory access latencies for independent traversals. …

    portland-state Repository record for Group Operations for Concurrent Binary Search Trees (opens in a new tab)

  15. On the connectivity interdiction problem, the geometry of data structures and Eulerian circuits

    … Scheme). The Geometry of the Minimum-cost Online Binary Search Tree Problem. In this problem, we want to find the optimum cost online self-adjusting binary search tree which searches any sequence of keys in the tree, a problem related to the Dynamic Optimality Conjecture [Sleator & Tarjan 1985]. …

    aalto Repository record for On the connectivity interdiction problem, the geometry of data structures and Eulerian circuits (opens in a new tab)

  16. Concurrent Lazy Splay Tree with Relativistic Programming Approach

    A splay tree is a self-adjusting binary search tree in which recently accessed elements are quick to access again. Splay operation causes the sequential bottleneck at the root of the tree in concurrent environment. The Lazy splaying is to rotate the tree at most one per access so that very …

    unlv Repository record for Concurrent Lazy Splay Tree with Relativistic Programming Approach (opens in a new tab) Download PDF for Concurrent Lazy Splay Tree with Relativistic Programming Approach (opens in a new tab)

  17. Data discretization simplified: Randomized binary search trees for data preprocessing.

    … discretization method based upon a randomized binary search tree that provides the sorting routine as one of the properties of inserting into the data structure. We then provide an experimental design to compare our simple discretization method against common methods used prior to learning with …

    wvu Repository record for Data discretization simplified: Randomized binary search trees for data preprocessing. (opens in a new tab)

  18. Limit theorems for functionals of recursive trees

    … to the analysis of random b-ary recursive trees with weighted edges. We investigate functionals related to distances with regard to limit theorems. We show central limit theorems for the depth of a random node and distances between two random nodes. Further, we prove limit theorems for the …

    freiburg-diss Repository record for Limit theorems for functionals of recursive trees (opens in a new tab)

  19. Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts

    … permute a sorted array into the level-order binary search tree (BST), level-order B-tree (B-tree), and van Emde Boas (vEB) layouts in-place. We analytically determine the complexity of our algorithms and empirically measure their performance. Given N elements and P processors, our fastest …

    hawaii Repository record for Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts (opens in a new tab)

  20. Counting Catalan: An Experimental Evaluation of the Mixing Time for the Triangulation Markov Chain

    … One such chain is induced by taking a binary search tree and performing a rotation or flip on one of its edges. We know that this chain eventually settles into the uniform distribution, but the time complexity bounds on the number of steps it takes to do so are not tight. We showcase an …

    calpoly Repository record for Counting Catalan: An Experimental Evaluation of the Mixing Time for the Triangulation Markov Chain (opens in a new tab)

Page 1 of 2