A Fast Parallelizable Algorithm for Constructing Balanced Binary Search Trees
- Original Research
- Published: 14 July 2022
- Volume 3 , article number 367 , ( 2022 )
Cite this article
- Pavel S. Ruzankin ORCID: orcid.org/0000-0002-5262-3037 1
122 Accesses
1 Altmetric
Explore all metrics
We suggest a new non-recursive algorithm for constructing a balanced binary search tree given an array of numbers. The algorithm has O ( N ) time and O (1) auxiliary memory complexity if the given array of N numbers is sorted. The resulting tree is of minimal height and can be transformed into a complete binary search tree while retaining minimal height with \(O(\log N)\) time and O (1) auxiliary memory. The algorithm allows simple and effective parallelization resulting in time complexity \(O((N/s)+s+\log N)\) , where s is the number of parallel threads.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Similar content being viewed by others
Space-Efficient Parallel Algorithms for Combinatorial Search Problems
Parallel String Sample Sort
Parallel Construction of Succinct Trees
Aghaieabiane N, Koppelaar H, Nasehpour P. An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals. J Algorithms Comput. 2017;49(1):93–113.
Google Scholar
Das VV. A new non-recursive algorithm for reconstructing a binary tree from its traversals. In: 2010 International Conference on Advances in Recent Technologies in Communication and Computing, Kottayam, 2010; pp 261–263. https://doi.org/10.1109/ARTCom.2010.88 .
Find first set. Wikipedia article. https://en.wikipedia.org/wiki/Find_first_set . Retrieved 1 Jun 2022.
Gagie T. New ways to construct binary search trees. In: Ibaraki T, Katoh N, Ono H (eds) Algorithms and computation. ISAAC 2003. Lecture Notes in Computer Science, vol. 2906, Springer, Berlin, Heidelberg, 2003.
Knuth DE. The art of computer programming: sorting and searching, vol. 3. Reading: Addison-Wesley Pub. Co; 1973.
MATH Google Scholar
Other built-in functions provided by GCC. https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html . Retrieved 27 Aug 2021.
Stephenson CJ. A method for constructing binary search trees by making insertions at the root. Int J Comput Inf Sci. 1980;9:15–29.
Article Google Scholar
Vaucher JG. Building optimal binary search trees from sorted values in O(N) time. In: Essays in Memory of Ole-Johan Dahl, 2004; pp 376–388.
Wirth N. Algorithms + data structures = programs. Englewood Cliffs: Prentice-Hall; 1976.
Download references
The study was supported by the program for fundamental scientific research of the Siberian Branch of the Russian Academy of Sciences, project FWNF-2022-0009.
Author information
Authors and affiliations.
Sobolev Institute of Mathematics, Novosibirsk, Russia
Pavel S. Ruzankin
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Pavel S. Ruzankin .
Ethics declarations
Conflict of interest.
The author declares that has no conflict of interest.
Additional information
Publisher's note.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Reprints and permissions
About this article
Ruzankin, P.S. A Fast Parallelizable Algorithm for Constructing Balanced Binary Search Trees. SN COMPUT. SCI. 3 , 367 (2022). https://doi.org/10.1007/s42979-022-01285-9
Download citation
Received : 28 August 2021
Accepted : 01 July 2022
Published : 14 July 2022
DOI : https://doi.org/10.1007/s42979-022-01285-9
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Binary search tree
- Parallel algorithm
- Find a journal
- Publish with us
- Track your research
Help | Advanced Search
Statistics > Machine Learning
Title: learning a binary search with a recurrent neural network. a novel approach to ordinal regression analysis.
Abstract: Deep neural networks are a family of computational models that are naturally suited to the analysis of hierarchical data such as, for instance, sequential data with the use of recurrent neural networks. In the other hand, ordinal regression is a well-known predictive modelling problem used in fields as diverse as psychometry to deep neural network based voice modelling. Their specificity lies in the properties of their outcome variable, typically considered as a categorical variable with natural ordering properties, typically allowing comparisons between different states ("a little" is less than "somewhat" which is itself less than "a lot", with transitivity allowed). This article investigates the application of sequence-to-sequence learning methods provided by the deep learning framework in ordinal regression, by formulating the ordinal regression problem as a sequential binary search. A method for visualizing the model's explanatory variables according to the ordinal target variable is proposed, that bears some similarities to linear discriminant analysis. The method is compared to traditional ordinal regression methods on a number of benchmark dataset, and is shown to have comparable or significantly better predictive power.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | [stat.ML] |
| (or [stat.ML] for this version) | |
| Focus to learn more arXiv-issued DOI via DataCite |
Submission history
Access paper:.
- Other Formats
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bibliographic and Citation Tools
Code, data and media associated with this article, recommenders and search tools.
- Institution
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .
- DOI: 10.22214/IJRASET.2017.10195
- Corpus ID: 62887591
Comparative Performance Analysis of Binary Search in Sequential and Parallel Processing
- Shubham Dubey
- Published 23 October 2017
- Computer Science
- International Journal for Research in Applied Science and Engineering Technology
Figures and Tables from this paper
One Citation
A comparative analysis of the efficiencies of binary and linear search algorithms, 13 references, research on optimization and parallelization of optimal binary search tree using dynamic programming, comparing linear search and binary search algorithms to search an element from a linear list implemented through static array, dynamic array and linked list, binary search algorithm, randomized binary search trees, modified binary search algorithm, designing optimal binary search tree using parallel genetic algorithms, context indexing in search engine using binary search tree, parallel computing system for image intelligent processing, related papers.
Showing 1 through 3 of 0 Related Papers
IEEE Account
- Change Username/Password
- Update Address
Purchase Details
- Payment Options
- Order History
- View Purchased Documents
Profile Information
- Communications Preferences
- Profession and Education
- Technical Interests
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
- We're Hiring!
- Help Center
Binary Search Trees
Related Papers
Fernanda Argota
By applying object-oriented design to the definition of a binary search tree, Berman and Duvall [1] designed a data structure comprised of three classes: (i) an EmptyBST class to model empty binary search trees, (ii) a NonEmptyBST class to model non-empty binary search trees, and (iii) a BST base class for common attributes of EmptyBST and NonEmptyBST objects. That paper noted the problem of inserting new values into such a structure: since insertions occur at an EmptyBST object, an EmptyBST would have to "turn into " a NonEmptyBST; a behavior beyond the capabilities of the classes in most languages. This paper presents three C++ solutions to the insertion problem in their order of development. The first solution uses a procedural programming technique, with the second and third solutions shifting to a more object-oriented approach. This chronology illustrates the author's ongoing battle to shift from procedural to object-oriented thinking.
ACM SIGCSE Bulletin
Information Processing Letters
Sukhamay Kundu
South African Computer Journal
Brink Van Der Merwe
We consider two ways of inserting a key into a binary search tree: leaf insertion which is the standard method, and root insertion which involves additional rotations. Although the respective cost of constructing leaf and root insertion binary search trees trees, in terms of comparisons, are the same in the average case, we show that in the worst case the construction of a root insertion binary search tree needs approximately 50% of the number of comparisons required by leaf insertion.
Robert Duvall
The Binary Search Tree serves as an important example when teaching data structures. We explore new approaches to understanding the implementation of a Binary Search Tree, using concepts from Object-Oriented Programming and C++. The Binary Search Tree illustrates how adopting a new approach and a new language can lead to a new way of thinking about a familiar problem.
jagannadha varma Pinnamaraju
Srinidhi Deshpande
A data structure is proposed to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. The tree is one of the most powerful of the advanced data structures and it often pops up in even more advanced subjects such as AI and compiler design. Surprisingly though the tree is important in a much more basic application-namely the keeping of an efficient index. This research paper gives us brief description of importance of tree in data structure, types of trees, implementation with their examples.
Discrete Mathematics & Theoretical Computer Science
Alois Panholzer
There are three classical algorithms to visit all the nodes of a binary tree - preorder, inorder and postorder traversal. From this one gets a natural labelling of the internal nodes of a binary tree by the numbers , indicating the sequence in which the nodes are visited. For given (size of the tree) and (a number between 1 and
Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.
RELATED PAPERS
Henk Koppelaar , Peyman Nasehpour
David Maier
Ramesh Singh Rawat
Erkki Makinen
Journal of Algorithms and Computation
Peyman Nasehpour , Henk Koppelaar
International Journal of Computer Science and Mobile Computing
pijush kumar
Robert Logozar
Representations for Genetic and Evolutionary Algorithms
Franz Rothlauf
International Journal of Computer Applications
Pradeep Kaushik
Computer Science Education
Stephen Edwards
International Journal of Advanced Computer Science and Applications
Emilia Todorova , Ivaylo Donchev
Journal of Computer Science IJCSIS
Sashka Davis
Journal of the ACM
Robert Tarjan
Aldon Walker
Proceedings of the 1971 international ACM SIGIR …
The Computer Journal
Adrijan Božinovski , Nevena Ackovska
Dr. Inayat ur-Rehman
isromania .in
Amitava Bagchi
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2024
Learn Python practically and Get Certified .
Popular Tutorials
Popular examples, reference materials, learn python interactively, dsa introduction.
- What is an algorithm?
- Data Structure and Types
- Why learn DSA?
- Asymptotic Notations
- Master Theorem
- Divide and Conquer Algorithm
Data Structures (I)
- Types of Queue
- Circular Queue
- Priority Queue
Data Structures (II)
- Linked List
- Linked List Operations
- Types of Linked List
- Heap Data Structure
- Fibonacci Heap
- Decrease Key and Delete Node Operations on a Fibonacci Heap
Tree based DSA (I)
- Tree Data Structure
- Tree Traversal
- Binary Tree
- Full Binary Tree
- Perfect Binary Tree
- Complete Binary Tree
- Balanced Binary Tree
- Binary Search Tree
Tree based DSA (II)
- Insertion in a B-tree
- Deletion from a B-tree
- Insertion on a B+ Tree
- Deletion from a B+ Tree
- Red-Black Tree
- Red-Black Tree Insertion
- Red-Black Tree Deletion
Graph based DSA
- Graph Data Structure
- Spanning Tree
- Strongly Connected Components
- Adjacency Matrix
- Adjacency List
- DFS Algorithm
- Breadth-first Search
- Bellman Ford's Algorithm
Sorting and Searching Algorithms
- Bubble Sort
- Selection Sort
- Insertion Sort
- Counting Sort
- Bucket Sort
Linear Search
Binary Search
Greedy algorithms.
- Greedy Algorithm
- Ford-Fulkerson Algorithm
- Dijkstra's Algorithm
- Kruskal's Algorithm
- Prim's Algorithm
- Huffman Coding
- Dynamic Programming
- Floyd-Warshall Algorithm
- Longest Common Sequence
Other Algorithms
- Backtracking Algorithm
- Rabin-Karp Algorithm
DSA Tutorials
Quicksort Algorithm
Binary Search Tree(BST)
Insertion Sort Algorithm
- Counting Sort Algorithm
Binary Search is a searching algorithm for finding an element's position in a sorted array.
In this approach, the element is always searched in the middle of a portion of an array.
Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.
- Binary Search Working
Binary Search Algorithm can be implemented in two ways which are discussed below.
- Iterative Method
Recursive Method
The recursive method follows the divide and conquer approach.
The general steps for both methods are discussed below.
- If x == arr[mid] , then return mid . Else, compare the element to be searched with arr[mid] .
- If x > arr[mid] , compare x with the middle element of the elements on the right side of arr[mid] . This is done by setting low to low = mid + 1 .
- Binary Search Algorithm
Iteration Method
- Python, Java, C/C++ Examples (Iterative Method)
- Python, Java, C/C++ Examples (Recursive Method)
- Binary Search Complexity
Time Complexities
- Best case complexity : O(1)
- Average case complexity : O(log n)
- Worst case complexity : O(log n)
Space Complexity
The space complexity of the binary search is O(1) .
- Binary Search Applications
- In libraries of Java, .Net, C++ STL
- While debugging, the binary search is used to pinpoint the place where the error happens.
Table of Contents
Sorry about that.
Our premium learning platform, created with over a decade of experience and thousands of feedbacks .
Learn and improve your coding skills like never before.
- Interactive Courses
- Certificates
- 2000+ Challenges
Related Tutorials
DS & Algorithms
IMAGES
VIDEO
COMMENTS
Abstract and Figures. This paper proposes a modification to the traditional binary search algorithm in which it checks the presence of the input element with the middle element of the given set of ...
Binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array. In In computer science, binary search , also known as half-interval search , [1] logarithmic search , [2] or binary chop , [3] is a search algorithm that finds a position of a target value within a ...
This research presents an optimized Binary Search algorithm that ensures that search is performed if and only if the search key is within the feasible search space, thus exhibiting a faster time complexity than the Binary Search algorithm- in particular, when the search key is outside the feasible search space of the list.
In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by Emamjomeh-Zadeh et al. (in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, pp. 519-532, 2016) to the problem of ...
This paper proposes a modification to the traditional binary search algorithm in which it checks the presence of the input element with the middle element of the given set of elements at each iteration. Modified binary search algorithm optimizes the worst case of the binary search algorithm by comparing the input element with the first & last ...
This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is ...
Binary Search Tree (BST) is an acyclic graph that is widely used to arrange the data for optimal search. In order to maintain the binary search tree in optimal shape several algorithms have been proposed. A recently proposed technique [1] applies single and double rotations to balance the binary search tree. However, due to double rotation it takes almost double time as compared to single ...
We present a new non-recursive algorithm for construct-ing a binary search tree. The algorithm has O(N) time and O(1) auxiliary memory complexity if the given array of N numbers is sorted. We use an array-based representation of the BST. The O(1) auxiliary memory complexity means that, except for the resulting arrays used to store the tree, we.
In this research paper, it provides a detailed study of Binary Search and how the time complexity of Binary Search can be reduced by using Odd Even Based Binary Search Algorithm, which is an ...
Deep neural networks are a family of computational models that are naturally suited to the analysis of hierarchical data such as, for instance, sequential data with the use of recurrent neural networks. In the other hand, ordinal regression is a well-known predictive modelling problem used in fields as diverse as psychometry to deep neural network based voice modelling. Their specificity lies ...
The user has to wait till the completion of processing to find whether search is successful or not. In this research paper, it provides a detailed study of Binary Search and how the time complexity of Binary Search can be reduced by using Odd Even Based Binary Search Algorithm, which is an extension of classical binary search strategy.
Among state of art approaches binary search relies on divide and conquer approach explore key item at mid element of array after each iteration and accordingly moves interval to new sub range. ... This paper research into the dynamical process of building an Optimal Binary Search Tree and presents an optimized solution that time complexity is ...
In this paper, we consider randomized algorithms to dynamically maintain a dictionary in a BST. We call the BSTs produced by our algorithms randomized binary search trees (RBSTs). In Sections 2 and 3, we show that RBSTs are, in fact, random binary search trees, irrespective of the order in which the keys were
The rest of the paper is organized as follows. Section2reviews related work. Section3 introduces the system framework. Section4presents the experimental evaluation. Section5 discusses the results. Section6concludes the paper. 2. Background and Related Work Cryptography is the ancient practice of securing data for transmission and storage. It
The Problem ‣ Observation #1 ‣ we can stop searching for 11 if we reach 12 ‣ we can stop searching for x if we reach y > x ‣ Why? ‣ since array is sorted, 11 can't be after 12 ‣ since array is sorted, x can't be after y ‣ But what if we're looking for 25? 9 1 1 3 4 7 8 101012181921232324
This paper studies a generalization of the classic binary search problem of locating a desired value within a sorted list. The classic problem can be viewed as determining the correct one-dimensional, binary-valued threshold function from a finite class of such functions based on queries taking the form of point samples of the function. The classic problem is also equivalent to a simple binary ...
binary search algorithm is quite useful. The binary search algorithm can be applied to an array whose elements are to be required in sorted form [1][2]. Each iteration of binary search narrows the search interval by half of the search interval of its previous iteration. The time required by binary search is O (log 2 N)[1][5].
also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 <= 3 and 4 > 3. Watch out for the exact wording in the problems -- a "binary search tree" is different from a "binary tree". The nodes at the bottom edge of the tree have empty subtrees and are called "leaf" nodes (1, 4, 6) while the others
Abstract. In this paper we present randomized algorithms over binary search trees such that: a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a ...
We present a detailed study of left-right-imbalance measures for random binary search trees under the random permutation model, i.e., where binary search trees are generated by random permutations of f1;2; : : : ; ng. For random binary search trees of size n we study (i) the difierence between the left and the right depth of a randomly chosen node,
View PDF. Binary Search Trees • A Binary Search Tree (BST) is a special type of binary tree - it represents information is an ordered format - A binary tree is binary search tree if for every node w, all keys in the left subtree of i have values less than the key of w and all keys in the right subtree have values greater than key of w. 1 ...
Binary Search is a searching algorithm for finding an element's position in a sorted array. In this approach, the element is always searched in the middle of a portion of an array. Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.
This paper gives the least upper bound on the weighted path length of an optimum lexicographic (alphabetic) binary search tree as a function of n, given the total weight of the n terminal nodes ...