Log in

Relevant bibliographies by topics / Binary Search Trees

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers

Academic literature on the topic 'Binary Search Trees'

Author: Grafiati

Published: 4 June 2021

Last updated: 8 June 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Binary Search Trees"

1

Martínez, Conrado, and Salvador Roura. "Randomized binary search trees." Journal of the ACM 45, no. 2 (March 1998): 288–323. http://dx.doi.org/10.1145/274787.274812.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Jung, Haejae, and Sartaj Sahni. "Supernode Binary Search Trees." International Journal of Foundations of Computer Science 14, no. 03 (June 2003): 465–90. http://dx.doi.org/10.1142/s0129054103001844.

Full text

Abstract:

Balanced binary search tree structures such as AVL, red-black, and splay trees store exactly one element per node. We propose supernode versions of these structures in which each node may have a large number of elements. Some properties of supernode binary search tree structures are established. Experiments oonducted by us show that the supernode structures proposed by us use less space than do the corresponding one-element-per-node versions and also take less time for the standard dictionary operations: search, insert and delete.

APA, Harvard, Vancouver, ISO, and other styles

3

Dobosiewicz, Wlodzimierz. "Optimal binary search trees." International Journal of Computer Mathematics 19, no. 2 (January 1986): 135–51. http://dx.doi.org/10.1080/00207168608803511.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Nagaraj, S. V. "Optimal binary search trees." Theoretical Computer Science 188, no. 1-2 (November 1997): 1–44. http://dx.doi.org/10.1016/s0304-3975(96)00320-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Nurmi, Otto, and Eljas Soisalon-Soininen. "Chromatic binary search trees." Acta Informatica 33, no. 5 (August 1996): 547–57. http://dx.doi.org/10.1007/bf03036462.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

De Prisco, Roberto, and Alfredo De Santis. "On binary search trees." Information Processing Letters 45, no. 5 (April 1993): 249–53. http://dx.doi.org/10.1016/0020-0190(93)90212-r.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Nurmi, Otto, and Eljas Soisalon-Soininen. "Chromatic binary search trees." Acta Informatica 33, no. 6 (September 1, 1996): 547–57. http://dx.doi.org/10.1007/s002360050057.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ragde, Prabhakar. "Simple Balanced Binary Search Trees." Electronic Proceedings in Theoretical Computer Science 170 (December 12, 2014): 78–87. http://dx.doi.org/10.4204/eptcs.170.6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Sánchez-Couso, José-Ramón, and María-Inés Fernández-Camacho. "Reductions in binary search trees." Theoretical Computer Science 355, no. 3 (April 2006): 327–53. http://dx.doi.org/10.1016/j.tcs.2005.12.015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Sleator, Daniel Dominic, and Robert Endre Tarjan. "Self-adjusting binary search trees." Journal of the ACM 32, no. 3 (July 1985): 652–86. http://dx.doi.org/10.1145/3828.3835.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Binary Search Trees"

1

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 text

APA, Harvard, Vancouver, ISO, and other styles

2

Harmon, Dion (Dion Kane). "New bounds on optimal binary search trees." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/34268.

Full text

Abstract:

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006.
This 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.

APA, Harvard, Vancouver, ISO, and other styles

3

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 text

APA, Harvard, Vancouver, ISO, and other styles

4

Goudjil, 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 text

Abstract:

This thesis covers the study of a particular class of binary search trees, the Weyl trees formed by consecutive insertion of numbers {theta}, {2theta}, {3theta}, ..., where theta is an irrational number from (0,1), and {x} denotes the fractional part of x. Various properties of the structure of these trees are explored and a relationship with the continued fraction expansion of theta is shown. Among these properties, an approximation of the height Hn of a Weyl tree with n nodes is given when theta is chosen at random and uniformly on (0, 1). The main result of this work is that in probability, Hn ∼ (12/pi2) log n log log n.

APA, Harvard, Vancouver, ISO, and other styles

5

Holmgren, 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 text

APA, Harvard, Vancouver, ISO, and other styles

6

Manthey, 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 text

APA, Harvard, Vancouver, ISO, and other styles

7

Kozma, 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 text

APA, Harvard, Vancouver, ISO, and other styles

8

Sayed, 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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

9

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 text

Abstract:

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 ﬁrst 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 inﬁnitely divisible distributions. It was shown that with modiﬁcations, 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 inﬁnity. 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 describe 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 immigration. Using this method it was demonstrated that when the tree is stable (i.e., ﬁnite), there is the same type of expression for the number of vertices as for normal split trees.

APA, Harvard, Vancouver, ISO, and other styles

10

Love, Lorna. "The suffix binary search tree." Thesis, University of Glasgow, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.270960.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Books on the topic "Binary Search Trees"

1

Roy, Abhijit Kumar, and Biplab Pal. 50 Uncommon Quiz Problems in AP/GT Computer Science for High Schools Vol-02 : (Stacks and Queues, Linked Lists and Binary Search Trees, Data Structures Graphs, Recursion in JavaScript). Independently Published, 2022.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Binary Search Trees"

1

AbouEisha, Hassan, Talha Amin, Igor Chikalov, Shahid Hussain, and Mikhail Moshkov. "Binary Search Trees." In Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining, 245–52. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-91839-6_17.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Mankowski, Michal, and Mikhail Moshkov. "Binary Search Trees." In Dynamic Programming Multi-Objective Combinatorial Optimization, 87–97. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-63920-4_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Lu, Yung-Hsiang, and George K. Thiruvathukal. "Binary Search Trees." In Intermediate C Programming, 255–67. 2nd ed. Boca Raton: CRC Press, 2023. http://dx.doi.org/10.1201/9781003257981-21.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Demaine, Erik D., John Iacono, Stefan Langerman, and Özgür Özkan. "Combining Binary Search Trees." In Automata, Languages, and Programming, 388–99. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-39206-1_33.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Brodal, Gerth Stølting, and Gabriel Moruz. "Skewed Binary Search Trees." In Lecture Notes in Computer Science, 708–19. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11841036_63.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Lee, Kent D., and Steve Hubbard. "Balanced Binary Search Trees." In Undergraduate Topics in Computer Science, 241–65. Cham: Springer International Publishing, 2024. http://dx.doi.org/10.1007/978-3-031-42209-6_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Lee, Kent D., and Steve Hubbard. "Balanced Binary Search Trees." In Undergraduate Topics in Computer Science, 237–60. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-13072-9_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Bose, Prosenjit, Sébastien Collette, Rolf Fagerberg, and Stefan Langerman. "De-amortizing Binary Search Trees." In Automata, Languages, and Programming, 121–32. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31594-7_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Duch, Amalia, Vladimir Estivill-Castro, and Conrado Martínez. "Randomized K-Dimensional Binary Search Trees." In Algorithms and Computation, 198–209. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-49381-6_22.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Chlebus, Bogdan S., and Imrich Vrťo. "Unifying binary-search trees and permutations." In Fundamentals of Computation Theory, 190–99. Berlin, Heidelberg: Springer Berlin Heidelberg, 1991. http://dx.doi.org/10.1007/3-540-54458-5_63.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Binary Search Trees"

1

Ellen, Faith, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. "Non-blocking binary search trees." In Proceeding of the 29th ACM SIGACT-SIGOPS symposium. New York, New York, USA: ACM Press, 2010. http://dx.doi.org/10.1145/1835698.1835736.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Chatterjee, Bapi, Nhan Nguyen, and Philippas Tsigas. "Efficient lock-free binary search trees." In the 2014 ACM symposium. New York, New York, USA: ACM Press, 2014. http://dx.doi.org/10.1145/2611462.2611500.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Demaine, Erik D., Dion Harmon, John Iacono, Daniel Kane, and Mihai Pâtraşcu. "The Geometry of Binary Search Trees." In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2009. http://dx.doi.org/10.1137/1.9781611973068.55.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Iacono, John, and Stefan Langerman. "Weighted dynamic finger in binary search trees." In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611974331.ch49.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Natarajan, Aravind, and Neeraj Mittal. "Fast concurrent lock-free binary search trees." In the 19th ACM SIGPLAN symposium. New York, New York, USA: ACM Press, 2014. http://dx.doi.org/10.1145/2555243.2555256.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Al-Furaih, Ibraheem, Srinivas Aluru, Sanjay Goil, and Sanjay Ranka. "Parallel construction of multidimensional binary search trees." In the 10th international conference. New York, New York, USA: ACM Press, 1996. http://dx.doi.org/10.1145/237578.237605.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Chalermsook, Parinya, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. "Pattern-Avoiding Access in Binary Search Trees." In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2015. http://dx.doi.org/10.1109/focs.2015.32.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Rasala, Richard. "A model C++ tree iterator class for binary search trees." In the twenty-eighth SIGCSE technical symposium. New York, New York, USA: ACM Press, 1997. http://dx.doi.org/10.1145/268084.268114.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Culberson, J. C. "The effect of updates in binary search trees." In the seventeenth annual ACM symposium. New York, New York, USA: ACM Press, 1985. http://dx.doi.org/10.1145/22145.22168.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Drachsler, Dana, Martin Vechev, and Eran Yahav. "Practical concurrent binary search trees via logical ordering." In the 19th ACM SIGPLAN symposium. New York, New York, USA: ACM Press, 2014. http://dx.doi.org/10.1145/2555243.2555269.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!