Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 344 papers for “Optimal binary search tree”

A Concurrency-Optimal Binary Search Tree

Vitaly Aksenov, Vincent Gramoli, Petr Kuznetsov et al. · arXiv (Cornell University) · 2017

The paper presents the first \emph{concurrency-optimal} implementation of a binary search tree (BST). The implementation, based on a standard sequential implementation of an internal tree, ensures that every \emph{schedule} is accepted, i.e., interleaving of steps of the sequential code, unless linearizability is violated. To ensure this property, we use a novel read-write locking scheme that protects tree \emph{edges} in addition to nodes. Our implementation outperforms the state-of-the art BSTs on most basic workloads, which suggests that optimizing the set of accepted schedules of the sequential code can be an adequate design principle for efficient concurrent data structures.

Cited by 0Open access

Optimal Binary Search Tree Meet Object-Oriented Programming

Stuart Hansen, Lester I. Mccann · 2008

This paper presents an object–oriented approach to the problem of finding optimal binary search trees. We show that object–oriented techniques produce a solution that is an improvement over those created procedurally and that is well within the reach of our undergraduate students. Combining the study of optimality with that of object–oriented design helps the students gain a deeper appreciation of both. 1

Cited by 0

Construct Optimal Binary Search Tree by Using Greedy Algorithm

Chun Shi, Ming Zhao, Chunyu Li et al. · Advances in intelligent systems research/Advances in Intelligent Systems Research · 2016

Focus on some constructions of binary tree, there are many methods to resolve this problem. With analyzes between binary search tree and Huffman tree, we introduce information retrieval issue and compare the Huffman tree with optimal binary search tree. And we further present a method that use greedy algorithm to construct binary search tree and use C++ to realize method. Experimental provides some conclusions that greedy algorithm is more efficiency than dynamic programming algorithm.

Cited by 0Open access

Optimal Region for Binary Search Tree, Rotation and Polytope

Kensuke Onishi, Mamoru Hoshi · 2013

Abstract Given a set of keys and its weight, a binary search tree(BST) with the smallest path length among all trees with the keys and the weight is called optimal tree. Knuth showed that the optimal tree is computed in the time of square of the number of keys. In this paper, we propose algorithms that divide the weight space into regions corresponding to optimal trees by a construction algorithm of convex hull. It is proved that each BST has a non-empty region, called optimal region, for which only the tree is optimal and that two optimal regions are adjacent if the corresponding trees are transformed to each other by a single rotation. We describe a relation between associahedron and the convex hull of the whole BSTs. 1

Cited by 0

An Optimal Modification BTC Scheme Based on Binary Search Tree

Chia‐Chen Lin, Xiao Long Liu, Jian Jie Zhou et al. · 2014

With the purpose of improving the visual quality of an original block truncation coding (BTC) compressed image, an optimal modified BTC scheme (OMBTC) is proposed. The binary search tree (BST) technique is utilized to determine the optimal quantization of each image block. The proposed scheme is compared with several existing modification BTC schemes, the experimental results demonstrate that the proposed scheme can preserve high image quality after compression.

Cited by 2

Search cost for a nearly optimal path in a binary tree

Robin Pemantle · The Annals of Applied Probability · 2009

Consider a binary tree, to the vertices of which are assigned independent Bernoulli random variables with mean p≤1/2. How many of these Bernoullis one must look at in order to find a path of length n from the root which maximizes, up to a factor of 1−ɛ, the sum of the Bernoullis along the path? In the case p=1/2 (the critical value for nontriviality), it is shown to take Θ(ɛ−1n) steps. In the case p<1/2, the number of steps is shown to be at least n⋅exp(const ɛ−1/2). This last result matches the known upper bound from [Algorithmica 22 (1998) 388–412] in a certain family of subcases.

Cited by 12Open access

Efficient Aspect Finding in Sentiment Analysis using Optimal Binary Search Tree

M. Chitra, A. Tamilarasi, Mrs. T. Kavitha et al. · International Journal of Recent Technology and Engineering (IJRTE) · 2019

Sentiment Analysis is an interesting research area. It useful for analyze the user comments with the help of natural language processing. While consider a huge data and improper data, the sentiment classification with better accuracy is a very big challenge in sentiment analysis. The social media records relevant to Sentiment analysis is a difficult one to identify with a people’s situation, thoughts, and view in the direction of a certain event, which has a number of applications such as election guess and product assessment. This paper focuses on the basic idea of optimal binary search Tree Technique to find the optimal solution (aspect) from a sentence among the several aspects; specifically, we perform the classification process appropriate to various features, which is used to identify the best one aspect among the several aspect terms in a sentence. In the proposed system, We have introduced optimal binary search Tree aspect level sentiment analysis technique. Through this we are getting best and efficient aspect level solution compare to General Tree. The main novelty of the paper is analyzing how aspect sentiment extracted from each word in a sentence through Dictionary based approach with help of the syntactic Patterns. It provides a well understanding of the appropriate role of every words to obtain optimal Aspect in an efficiency way.

Cited by 0Open access

Search cost for a nearly optimal path in a binary tree. arXiv:math/0701741

Robin Pemantle · 2007

Consider a binary tree, to the vertices of which are assigned independent Bernoulli random variables with mean p ≤ 1/2. How many of these Bernoullis one must look at in order to find a path of length n from the root which maximizes, up to a factor of 1 − , the sum of the Bernoullis along the path? In the case, p = 1/2 (the critical value for nontriviality), it is shown to take Θ(−1n) steps. In the case p &amp;lt; 1/2, the number of steps is shown to be at least n · exp(const −1/2). This last result matches the known upper bound from [Ald98] in a certain family of subcases.

Cited by 0

Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming

Bo Han, Yongquan Lu · 2012

The classical algorithm uses Dynamic Programming to construct an Optimal Binary Search Tree. In this paper, we research into the dynamical process of building an Optimal Binary Search Tree and present an optimized solution. Time complexity is reduced from O (n 3 ) to O (n 2 ). Meanwhile, three feasible parallel solutions are put forward to achieve greater optimization. Some experiments on cluster have been done to compare efficiency of parallel and serial algorithm and the result shows that the parallel algorithm is much better. In the case of a larger amount of testing data, the parallel solution can save half of the time consumption. However, because of the particularity of this issue, the parallel algorithm has its own limitation.

Cited by 5Open access

Statically Optimal Binary Search Tree Computation Using Non-Serial Polyadic Dynamic Programming on GPU's

Mohsin Altaf Wani, Manzoor Ahmad · International Journal of Grid and High Performance Computing · 2018

Modern GPUs perform computation at a very high rate when compared to CPUs; as a result, they are increasingly used for general purpose parallel computation. Determining if a statically optimal binary search tree is an optimization problem to find the optimal arrangement of nodes in a binary search tree so that average search time is minimized. Knuth's modification to the dynamic programming algorithm improves the time complexity to O(n2). We develop a multiple GPU-based implementation of this algorithm using different approaches. Using suitable GPU implementation for a given workload provides a speedup of up to four times over other GPU based implementations. We are able to achieve a speedup factor of 409 on older GTX 570 and a speedup factor of 745 is achieved on a more modern GTX 1060 when compared to a conventional single threaded CPU based implementation.

Cited by 2

Binary Search on a Tape

T. C. Hu, Michelle L. Wachs · SIAM Journal on Computing · 1987

Given n records stored alphabetically on a tape, any comparison search procedure can be characterized by a binary tree. The complete binary tree (binary search) uses the minimum number of comparisons but not the minimum number of movements. The linear binary tree (sequential search) uses the minimum number of movements but not the minimum number of comparisons. A tape-optimal tree is a tree which minimizes the total cost of comparisons and movements. The tape-optimal tree is a “hybrid” of the linear tree and the complete binary tree, and is characterized for arbitrary n.

Cited by 9

Two-Way Comparison Search Trees AGeneralization of Binary Search Trees and Split Trees Abstract

David Spuler · 2008

Ageneralization of binary search trees and binary split trees is developed that takes advantage of two-way key comparisons — the two-way comparison tree. The two-way comparison tree is shown to have little use for dynamic situations, but to be an improvement over the optimal binary search tree and the optimal binary split tree for static data sets. An O(n) time and space algorithm is presented for construction of the optimal two-way comparison tree when access probabilities are equal; the construction of the optimal tree for more general probabilities is shown to be more difficult and unlikely to cost less than O(n 4). 1.

Cited by 0

Hybrid trees

W.A. Walker, C. C. Gotlieb · 1972

A generalization of the binary tree and the Trie, called the hybrid tree, is defined in which a node can correspond to a key, to any substring in a key, or to a character of the alphabet from which the keys are formed. An algorithm is given for constructing an optimal hybrid tree and it is shown that the search time of an optimal hybrid tree is never larger than the search time of the Trie or the optimal binary tree representing the same set of keys.

Cited by 0Open access

Abstract An Empirical Study of Nearly Optimal Binary Search Trees and Split Trees

David A. Spuler, Gopal K. Gupta · 2008

Given a set of keys and relative frequencies of successful and unsuccessful searches, it is possible to build an optimal binary search tree using an algorithm that costs O(n 2) time and space. This algorithm is not efficient enough in many circumstances and then one must look at building a nearly optimal tree more cheaply. This paper uses an empirical study to evaluate a number of algorithms that have been proposed for building nearly optimal binary search trees. The split tree, introduced by Sheil (1978), is discussed and anumber of algorithms for building nearly optimal split trees are also evaluated. In addition, a simple variant of the split tree is presented (which we call a &amp;amp;quot;modified split tree&amp;amp;quot;) and a number of algorithms for constructing nearly optimal modified split trees are included in the empirical study. The modified split tree does not require any keys to be stored twice (as is the case with split trees) and has limited space wastage. Amodel of search cost of binary search and split trees is also discussed. 1.

Cited by 0

Optimal Search in Trees

Yosi Ben-Asher, Eitan Farchi, Ilan Newman · SIAM Journal on Computing · 1999

It is well known that the optimal solution for searching in a finite total order set is binary search. In binary search we divide the set into two &amp;quot;halves&amp;quot; by querying the middle element and continue the search on the suitable half. What is the equivalent of binary search when the set P is partially ordered? A query in this case is to a point x 2 P , with two possible answers: `yes&amp;apos;, indicates that the required element is &amp;quot;below&amp;quot; x, or `no&amp;apos; if the element is not below x. We show that the problem of computing an optimal strategy for search in Posets that are tree-like (or forests) is polynomial in the size of the tree, and requires at most O(n 4 log 3 n) steps. Optimal solutions of such search problems are often needed in program testing and debugging, where a given program is represented as a tree and a bug should be found using a minimal set of queries. This type of search is also applicable in searching classified large tree-like data bases (e.g. the Internet). Keywords: Optimal ...

Cited by 0