Relevant bibliographies by topics / Binary Search Trees / Journal articles
To see the other types of publications on this topic, follow the link: Binary Search Trees.

Journal articles 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 top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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
11

Gagie, Travis. "Restructuring binary search trees revisited." Information Processing Letters 95, no. 3 (August 2005): 418–21. http://dx.doi.org/10.1016/j.ipl.2005.03.014.

Full text
APA, Harvard, Vancouver, ISO, and other styles
12

Hivert, F., J. C. Novelli, and J. Y. Thibon. "The algebra of binary search trees." Theoretical Computer Science 339, no. 1 (June 2005): 129–65. http://dx.doi.org/10.1016/j.tcs.2005.01.012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
13

Hu, T. C., and P. A. Tucker. "Optimal alphabetic trees for binary search." Information Processing Letters 67, no. 3 (August 1998): 137–40. http://dx.doi.org/10.1016/s0020-0190(98)00101-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
14

Manthey, Bodo, and Rüdiger Reischuk. "Smoothed analysis of binary search trees." Theoretical Computer Science 378, no. 3 (June 2007): 292–315. http://dx.doi.org/10.1016/j.tcs.2007.02.035.

Full text
APA, Harvard, Vancouver, ISO, and other styles
15

Hofri, M., and H. Shachnai. "Efficient Reorganization of Binary Search Trees." Algorithmica 31, no. 3 (November 2001): 378–402. http://dx.doi.org/10.1007/s00453-001-0057-z.

Full text
APA, Harvard, Vancouver, ISO, and other styles
16

Chauvin, Brigitte, Michael Drmota, and Jean Jabbour-Hattab. "The Profile of Binary Search Trees." Annals of Applied Probability 11, no. 4 (November 2001): 1042–62. http://dx.doi.org/10.1214/aoap/1015345394.

Full text
APA, Harvard, Vancouver, ISO, and other styles
17

Flajolet, Philippe, Xavier Gourdon, and Conrado Mart�nez. "Patterns in random binary search trees." Random Structures and Algorithms 11, no. 3 (October 1997): 223–44. http://dx.doi.org/10.1002/(sici)1098-2418(199710)11:3<223::aid-rsa2>3.0.co;2-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
18

Bassetti, Federico, and Fabrizio Leisen. "Maximal Flow in Branching Trees and Binary Search Trees." Methodology and Computing in Applied Probability 13, no. 3 (February 6, 2010): 475–86. http://dx.doi.org/10.1007/s11009-010-9164-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
19

Komorowski, Michał, and Tomasz Trzciński. "Random Binary Search Trees for approximate nearest neighbour search in binary spaces." Applied Soft Computing 79 (June 2019): 87–93. http://dx.doi.org/10.1016/j.asoc.2019.03.031.

Full text
APA, Harvard, Vancouver, ISO, and other styles
20

CHO, SEONGHUN, and SARTAJ SAHNI. "A NEW WEIGHT BALANCED BINARY SEARCH TREE." International Journal of Foundations of Computer Science 11, no. 03 (September 2000): 485–513. http://dx.doi.org/10.1142/s0129054100000296.

Full text
Abstract:
We develop a new class of weight balanced binary search trees called β-balanced binary search trees (β-BBSTs). β-BBSTs are designed to have reduced internal path length. As a result, they are expected to exhibit good search time characteristics. Individual search, insert, and delete operations in an n node β-BBST take O( log n) time for [Formula: see text]. Experimental results comparing the performance of β-BBSTs, WB(α) trees, AVL-trees, red/black trees, treaps, deterministic skip lists and skip lists are presented. Two simplified versions of, β-BBSTs are also developed.
APA, Harvard, Vancouver, ISO, and other styles
21

Devroye, Luc, and Ralph Neininger. "Distances and Finger Search in Random Binary Search Trees." SIAM Journal on Computing 33, no. 3 (January 2004): 647–58. http://dx.doi.org/10.1137/s0097539703424521.

Full text
APA, Harvard, Vancouver, ISO, and other styles
22

Sen, Siddhartha, Robert E. Tarjan, and David Hong Kyun Kim. "Deletion Without Rebalancing in Binary Search Trees." ACM Transactions on Algorithms 12, no. 4 (September 2, 2016): 1–31. http://dx.doi.org/10.1145/2903142.

Full text
APA, Harvard, Vancouver, ISO, and other styles
23

Al-Furajh, I., S. Aluru, S. Goil, and S. Ranka. "Parallel construction of multidimensional binary search trees." IEEE Transactions on Parallel and Distributed Systems 11, no. 2 (2000): 136–48. http://dx.doi.org/10.1109/71.841750.

Full text
APA, Harvard, Vancouver, ISO, and other styles
24

Anderson, Richard, Sampath Kannan, Howard Karloff, and Richard E. Ladner. "Thresholds and optimal binary comparison search trees." Journal of Algorithms 44, no. 2 (August 2002): 338–58. http://dx.doi.org/10.1016/s0196-6774(02)00203-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
25

Zheng, S. "A new representation of binary search trees." Information Sciences 74, no. 3 (November 1993): 275–82. http://dx.doi.org/10.1016/0020-0255(93)90100-z.

Full text
APA, Harvard, Vancouver, ISO, and other styles
26

HINZE, RALF. "A fresh look at binary search trees." Journal of Functional Programming 12, no. 6 (November 2002): 601–7. http://dx.doi.org/10.1017/s0956796801004269.

Full text
Abstract:
Binary search trees are old hat, aren't they? Search trees are routinely covered in introductory computer science classes and they are widely used in functional programming courses to illustrate the benefits of algebraic data types and pattern matching. And indeed, the operation of insertion enjoys a succinct and elegant functional formulation. Figure 1 contains the six-liner given in the language Haskell 98.Alas, both succinctness and elegance are lost when it comes to implementing the dual operation of deletion, also shown in figure 1. Two additional helper functions are required causing the code size to double in comparison with insertion.
APA, Harvard, Vancouver, ISO, and other styles
27

Grübel, Rudolf. "On the silhouette of binary search trees." Annals of Applied Probability 19, no. 5 (October 2009): 1781–802. http://dx.doi.org/10.1214/08-aap593.

Full text
APA, Harvard, Vancouver, ISO, and other styles
28

Chauvin, B., T. Klein, J. F. Marckert, and A. Rouault. "Martingales and Profile of Binary Search Trees." Electronic Journal of Probability 10 (2005): 420–35. http://dx.doi.org/10.1214/ejp.v10-257.

Full text
APA, Harvard, Vancouver, ISO, and other styles
29

Natarajan, Aravind, and Neeraj Mittal. "Fast concurrent lock-free binary search trees." ACM SIGPLAN Notices 49, no. 8 (November 26, 2014): 317–28. http://dx.doi.org/10.1145/2692916.2555256.

Full text
APA, Harvard, Vancouver, ISO, and other styles
30

Bóna, Miklós. "k -Protected vertices in binary search trees." Advances in Applied Mathematics 53 (February 2014): 1–11. http://dx.doi.org/10.1016/j.aam.2013.09.003.

Full text
APA, Harvard, Vancouver, ISO, and other styles
31

Tsapanos, Nikolaos, Anastasios Tefas, and Ioannis Pitas. "Online shape learning using binary search trees." Image and Vision Computing 28, no. 7 (July 2010): 1146–54. http://dx.doi.org/10.1016/j.imavis.2009.10.012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
32

Mahmoud, Hosam M. "One-sided variations on binary search trees." Annals of the Institute of Statistical Mathematics 55, no. 4 (December 2003): 885–900. http://dx.doi.org/10.1007/bf02523399.

Full text
APA, Harvard, Vancouver, ISO, and other styles
33

Andersson, Arne, Christian Icking, Rolf Klein, and Thomas Ottmann. "Binary search trees of almost optimal height." Acta Informatica 28, no. 2 (February 1990): 165–78. http://dx.doi.org/10.1007/bf01237235.

Full text
APA, Harvard, Vancouver, ISO, and other styles
34

Prodinger, Helmut. "The -Version of Binary Search Trees: An Average Case Analysis." ISRN Combinatorics 2013 (December 19, 2013): 1–8. http://dx.doi.org/10.1155/2013/450627.

Full text
Abstract:
Following a suggestion of Cichoń and Macyna, binary search trees are generalized by keeping (classical) binary search trees and distributing incoming data at random to the individual trees. Costs for unsuccessful and successful search are analyzed, as well as the internal path length.
APA, Harvard, Vancouver, ISO, and other styles
35

Tarjan, Robert E., Caleb Levy, and Stephen Timmel. "Zip Trees." ACM Transactions on Algorithms 17, no. 4 (October 31, 2021): 1–12. http://dx.doi.org/10.1145/3476830.

Full text
Abstract:
We introduce the zip tree , 1 a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a binary search tree in which each node has a numeric rank and the tree is (max)-heap-ordered with respect to ranks, with rank ties broken in favor of smaller keys. Zip trees are essentially treaps [8], except that ranks are drawn from a geometric distribution instead of a uniform distribution, and we allow rank ties. These changes enable us to use fewer random bits per node. We perform insertions and deletions by unmerging and merging paths ( unzipping and zipping ) rather than by doing rotations, which avoids some pointer changes and improves efficiency. The methods of zipping and unzipping take inspiration from previous top-down approaches to insertion and deletion by Stephenson [10], Martínez and Roura [5], and Sprugnoli [9]. From a theoretical standpoint, this work provides two main results. First, zip trees require only O (log log n ) bits (with high probability) to represent the largest rank in an n -node binary search tree; previous data structures require O (log n ) bits for the largest rank. Second, zip trees are naturally isomorphic to skip lists [7], and simplify Dean and Jones’ mapping between skip lists
APA, Harvard, Vancouver, ISO, and other styles
36

Tarjan, Robert E., Caleb Levy, and Stephen Timmel. "Zip Trees." ACM Transactions on Algorithms 17, no. 4 (October 31, 2021): 1–12. http://dx.doi.org/10.1145/3476830.

Full text
Abstract:
We introduce the zip tree , 1 a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a binary search tree in which each node has a numeric rank and the tree is (max)-heap-ordered with respect to ranks, with rank ties broken in favor of smaller keys. Zip trees are essentially treaps [8], except that ranks are drawn from a geometric distribution instead of a uniform distribution, and we allow rank ties. These changes enable us to use fewer random bits per node. We perform insertions and deletions by unmerging and merging paths ( unzipping and zipping ) rather than by doing rotations, which avoids some pointer changes and improves efficiency. The methods of zipping and unzipping take inspiration from previous top-down approaches to insertion and deletion by Stephenson [10], Martínez and Roura [5], and Sprugnoli [9]. From a theoretical standpoint, this work provides two main results. First, zip trees require only O (log log n ) bits (with high probability) to represent the largest rank in an n -node binary search tree; previous data structures require O (log n ) bits for the largest rank. Second, zip trees are naturally isomorphic to skip lists [7], and simplify Dean and Jones’ mapping between skip lists
APA, Harvard, Vancouver, ISO, and other styles
37

Crain, Tyler, Vincent Gramoli, and Michel Raynal. "A Fast Contention-Friendly Binary Search Tree." Parallel Processing Letters 26, no. 03 (September 2016): 1650015. http://dx.doi.org/10.1142/s0129626416500158.

Full text
Abstract:
This paper presents a fast concurrent binary search tree algorithm. To achieve high performance under contention, the algorithm divides update operations within an eager abstract access that returns rapidly for efficiency reason and a lazy structural adaptation that may be postponed to diminish contention. To achieve high performance under read-only workloads, it features a rebalancing mechanism and guarantees that read-only operations searching for an element execute lock-free. We evaluate the contention-friendly binary search tree using Synchrobench, a benchmark suite to compare synchronization techniques. More specifically, we compare its performance against five state-of-the-art binary search trees that use locks, transactions or compare-and-swap for synchronization on Intel Xeon, AMD Opteron and Oracle SPARC. Our results show that our tree is more efficient than other trees and double the throughput of existing lock-based trees under high contention.
APA, Harvard, Vancouver, ISO, and other styles
38

Mohammad Nezhad, Ezzat, Mehri Javanian, and Ramin Imany Nabiyyi. "Weakly protected nodes in random binary search trees." RAIRO - Theoretical Informatics and Applications 56 (2022): 2. http://dx.doi.org/10.1051/ita/2022002.

Full text
Abstract:
Here, we derive the exact mean and variance of the number of weakly protected nodes (the nodes that are not leaves and at least one of their children is not a leaf) in binary search trees grown from random permutations. Furthermore, by using contraction method, we prove normal limit law for a properly normalized version of this tree parameter.
APA, Harvard, Vancouver, ISO, and other styles
39

Chan, Tat-Hung. "Computing average path lengths of binary search trees." ACM SIGCSE Bulletin 23, no. 3 (September 1991): 10. http://dx.doi.org/10.1145/126459.126463.

Full text
APA, Harvard, Vancouver, ISO, and other styles
40

Dekking, Michel, and Peter Van der Wal. "Uniform distribution modulo one and binary search trees." Journal de Théorie des Nombres de Bordeaux 14, no. 2 (2002): 415–24. http://dx.doi.org/10.5802/jtnb.366.

Full text
APA, Harvard, Vancouver, ISO, and other styles
41

Devroye, Luc, and John Michael Robson. "On the Generation of Random Binary Search Trees." SIAM Journal on Computing 24, no. 6 (December 1995): 1141–56. http://dx.doi.org/10.1137/s0097539792224954.

Full text
APA, Harvard, Vancouver, ISO, and other styles
42

HOLMGREN, CECILIA. "Random Records and Cuttings in Binary Search Trees." Combinatorics, Probability and Computing 19, no. 3 (March 5, 2010): 391–424. http://dx.doi.org/10.1017/s096354830999068x.

Full text
Abstract:
We study the number of random records in a binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.
APA, Harvard, Vancouver, ISO, and other styles
43

Aguech, Rafik, Anis Amri, and Henning Sulzbach. "On Weighted Depths in Random Binary Search Trees." Journal of Theoretical Probability 31, no. 4 (July 11, 2017): 1929–51. http://dx.doi.org/10.1007/s10959-017-0773-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
44

Gordon, Dan. "Eliminating the flag in threaded binary search trees." Information Processing Letters 23, no. 4 (November 1986): 209–14. http://dx.doi.org/10.1016/0020-0190(86)90137-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
45

Güntzer, U., and M. Paul. "Jump interpolation search trees and symmetric binary numbers." Information Processing Letters 26, no. 4 (December 1987): 193–204. http://dx.doi.org/10.1016/0020-0190(87)90005-6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
46

Kuba, Markus, and Alois Panholzer. "The left–right-imbalance of binary search trees." Theoretical Computer Science 370, no. 1-3 (February 2007): 265–78. http://dx.doi.org/10.1016/j.tcs.2006.10.033.

Full text
APA, Harvard, Vancouver, ISO, and other styles
47

Mahmoud, Hosam M., and Ralph Neininger. "Distribution of distances in random binary search trees." Annals of Applied Probability 13, no. 1 (2003): 253–76. http://dx.doi.org/10.1214/aoap/1042765668.

Full text
APA, Harvard, Vancouver, ISO, and other styles
48

Drachsler, Dana, Martin Vechev, and Eran Yahav. "Practical concurrent binary search trees via logical ordering." ACM SIGPLAN Notices 49, no. 8 (November 26, 2014): 343–56. http://dx.doi.org/10.1145/2692916.2555269.

Full text
APA, Harvard, Vancouver, ISO, and other styles
49

Panholzer, Alois, and Helmut Prodinger. "Spanning tree size in random binary search trees." Annals of Applied Probability 14, no. 2 (May 2004): 718–33. http://dx.doi.org/10.1214/105051604000000071.

Full text
APA, Harvard, Vancouver, ISO, and other styles
50

Jabbour-Hattab, Jean. "Martingales and large deviations for binary search trees." Random Structures and Algorithms 19, no. 2 (2001): 112–27. http://dx.doi.org/10.1002/rsa.1023.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Binary Search Trees' for other source types:
Dissertations / Theses
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!

To the bibliography