Search

Data security has become crucial to most enterprise and government applications due to the increasing amount of data generated, collected, and analyzed. Many algorithms have been developed to secure data storage and transmission. However, most existing solutions require multi-round functions to prevent differential and linear attacks. This results in longer execution times and greater memory consumption, which are not suitable for large datasets or delay-sensitive systems. To address these issues, this work proposes a novel algorithm that uses, on one hand, the reflection property of a balanced binary search tree data structure to minimize the overhead, and on the other hand, a dynamic offset to achieve a high security level. The performance and security of the proposed algorithm were compared to Advanced Encryption Standard and Data Encryption Standard symmetric encryption algorithms. The proposed algorithm achieved the lowest running time with comparable memory usage and satisfied the avalanche effect criterion with 50.1%. Furthermore, the randomness of the dynamic offset passed a series of National Institute of Standards and Technology (NIST) statistical tests.

The storage structure on the data block of the current blockchain systems is still a linked list. This traditional structure is one-way and is not efficient for query operation. In view of this, we proposed a novel searching structure based on a height balanced Binary Search Tree (BST). The data structure we proposed not only retains the characteristics of the traditional ledgers but also adds the function of quick query. Through the new data structure, we can quickly find the starting position of the search and start searching for all transaction records within a specified range of time from this position. We also made an analysis and comparisons in the final.

Pathfinding is the problem of finding the shortest path between a pair of nodes in a graph. In the context of uniform-cost undirected grid maps, heuristic search algorithms, such as A ☆ and weighted A ☆ ( W A ☆ ), have been dominantly used for pathfinding. However, the lack of knowledge about obstacle shapes in a gird map often leads heuristic search algorithms to unnecessarily explore areas where a viable path is not available. We refer to such areas in a grid map as blocked areas (BAs). This paper introduces a preprocessing algorithm that analyzes the geometry of obstacles in a grid map and stores knowledge about blocked areas in a memory-efficient balanced binary search tree data structure. During actual pathfinding, a search algorithm accesses the binary search tree to identify blocked areas in a grid map and therefore avoid exploring them. As a result, the search time is significantly reduced. The scope of the paper covers maps in which obstacles are represented as horizontal and vertical line-segments. The impact of using the blocked area knowledge during pathfinding in A ☆ and W A ☆ is evaluated using publicly available benchmark set, consisting of sixty grid maps of mazes and rooms. In mazes, the search time for both A ☆ and W A ☆ is reduced by 28 % , on average. In rooms, the search time for both A ☆ and W A ☆ is reduced by 30 % , on average. This is achieved while preserving the search optimality of A ☆ and the search sub-optimality of W A ☆ .

This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm that is closely related to the over thirty-year-old idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided. To do so, the process of self-adjustment is modeled similarly to a basic network creation game in which the nodes want to communicate with only a certain subset of all nodes. We show that, in general, the game (i.e., the process of local adjustments) does not converge, and that convergence is related to certain structures of the communication interests, which we call conflicts. We classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the self-adjusting tree performs well. Furthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances. However, for the other conflict classes, a distributed self-adjusting binary search tree adapts poorly.

Test data generation is a process of creating program inputs that satisfy specific testing criteria. Many works have been focused on test generation with respect to numeric and string data. Dynamic data structures, such as trees and linked lists, have been widely used in modern programming, but on which there are few studies presented. In general, generating a dynamic data structure is associated with a proper shape and valid values generation. It would be difficult to generate such dynamic data structures, as both shapes and values are necessary to be valid simultaneously. This paper focuses on binary tree structures and proposes a novel test generation approach that combines search based testing with constraint solving techniques. The approach creates the shapes of binary tree structures by using GA, and generates the values in their data fields by using constraint solving techniques. The experimental results show that the presented approach is promising and effective. Moreover, the studies investigate factors affecting the performance of the approach, and arrive at a conclusion that the test generation cost is cubic growing as the number of pointer constraints increases.

With the increasing resolution of digital elevation models (DEMs), computational efficiency problems have been encountered when extracting the drainage network of a large river basin at billion-pixel scales. The efficiency of the most time-consuming depression-filling pretreatment has been improved by using the O ( N log N ) complexity least-cost path search method, but the complete extraction steps following this method have not been proposed and tested. In this paper, an improved O ( N log N ) algorithm was proposed by introducing a size-balanced binary search tree (BST) to improve the efficiency of the depression-filling pretreatment further. The following extraction steps, including the flow direction determination and the upslope area accumulation, were also redesigned to benefit from this improvement. Therefore, an efficient and comprehensive method was developed. The method was tested to extract drainage networks of 31 river basins with areas greater than 500,000 km 2 from the 30-m-resolution ASTER GDEM and two sub-basins with areas of approximately 1000 km 2 from the 1-m-resolution airborne LiDAR DEM. Complete drainage networks with both vector features and topographic parameters were obtained with time consumptions in O ( N log N ) complexity. The results indicate that the developed method can be used to extract entire drainage networks from DEMs with billions of pixels with high efficiency.

The paper describes new algorithm based on binary search tree using, which have average case time complexity O(N∗log(H)) where N is the size of the input set of points and H is the number of vertices found to be on the convex hull. The algorithm calculates the approximate center and stores all convex hull points in balanced binary search tree by the angle from it. Implementation of the new algorithm is written in C++ and tested against well-known algorithms. We show that our approach works better on low percentage of points in hull which is common case in convex hull calculation.

There are many storage structure available to store data in memory of many forms. These structures can be array, class, linked list with its various forms, Tree, Binary Tree, Binary Search Tree (BST), etc. These can be differentiated in two major forms. First one uses continuous memory allocation and the second one can occupy any free memory block by pointed by the other memory locations. An array occupies continuous memory space for storage purpose and the size should also be known before allocating the space. Perhaps we can use dynamic memory allocation methods for arrays but a Linked List provides better options. There is a disadvantage in Linked List, it does not allow to perform binary search operation on it. The Binary Search Tree is more efficient than the other mentioned data structures. BST provides the two way traversal direction but sometimes the structure of the BST can become unbalanced due to unprocessed ordering of inserted data. In this presented paper, the BST is considered as unbalanced if the number of levels is more than the levels which is required to hold the nodes. The unbalanced BST can lead to a straight tree structure with only one intermediate node at each and every level in the worst case scenario. The structure of BST depends on the insertion order of key elements. By changing the insertion order, BST can be made balanced. The proposed Estimated Level Based Balanced BST provides a solution for finding an insertion order of key elements which will not lead to unbalanced Balanced BST.

Traversing binary tree is an important algorithm in data structure. This paper analyses and discusses the recursive algorithm implementation of preorder-traversing binary tree through instance. It would contribute beginners to understand more deeply the process of preorder-traversing and enhance their programming.

We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.

We show that for every $k$, the probability that a randomly selected vertex of a random binary search tree on $n$ nodes is at distance $k-1$ from the closest leaf converges to a rational constant $c_k$ as $n$ goes to infinity., 12 pages 1 figure

According to the issue of tag collision in the radio frequency identification technology, this paper proposes a binary tree search anti-collision algorithm, which takes different processing methods according to how many continuous collision. Compared with the dynamic binary tree search algorithm, the improved algorithm reduces the query information send by the reader. At the same time,the algorithm in the process of identifying tags reduces the query information, the query number and tag response times, so as to shorten the recognition time, further improve the search performance.

The paper presents the first concurrency-optimal implementation of a binary search tree (BST). The implementation, based on a standard sequential implementation of a partially-external tree, ensures that every schedule, i.e., interleaving of steps of the sequential code, is accepted unless linearizability is violated. To ensure this property, we use a novel read-write locking protocol that protects tree edges in addition to its nodes.

P-sets consists of an internal P-set XF and an outer P-set XF and has dynamic characteristics, which result from the internal dynamic characteristics on XF and the outer dynamic characteristics on XF. In order to extend the application of the P-sets, the paper proposes an F-recursive binary tree through applying the dynamic characteristics for the P-set XF. Meanwhile, the paper provides the structures and characteristics for the F-recursive binary tree, including some properties and theorems about the F-recursive binary tree. The paper also gives the method of constructing F-recursive binary tree. The F-recursive binary tree has inward contraction characteristics and recursive characteristics. It can be used many research fields, such as information science and technology, artificial intelligence, knowledge discovery, as well as control theory and control engineering.

The method of carrier acquisition which we have used in this paper is a modified form of binary search algorithm. This modified search algorithm is a hybrid of two search algorithms which are "Binary search tree" and "Modified search tree". Firstly the modulated signal is received by the receiver where it is analyzed to acquire carrier. The receiver consists of two sections. One section uses the binary search tree process while the other section uses the modified search tree. Firstly binary search tree is used for carrier acquisition method and secondly the modified search tree is used. The overall tree diagram is a real-time tree diagram and it is formed during the process of carrier acquisition. This hybrid tree structure proves more helpful for carrier acquisition process as it is more accurate, low cost, less complex and less time consuming.

Binary Search Tree (BST) is an important data structure for managing ordered data. Many algorithms---blocking as well as non-blocking---have been proposed for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations based on both external and internal representations of a search tree. An important step in executing an operation on a tree is to traverse the tree from top-to-down in order to locate the operation's window. A process may need to perform this traversal several times to handle any failures occurring due to other processes performing conflicting actions on the tree. Most concurrent algorithms that have proposed so far use a naïve approach and simply restart the traversal from the root of the tree. In this work, we present a new approach to recover from such failures more efficiently in a concurrent binary search tree based on internal representation using local recovery by restarting the traversal from the "middle" of the tree in order to locate an operation's window. Our approach is sufficiently general in the sense that it can be applied to a variety of concurrent binary search trees based on both blocking and non-blocking approaches. Using experimental evaluation, we demonstrate that our local recovery approach can yield significant speed-ups of up to 69% for many concurrent algorithms.

Binary sort tree is a special binary tree, can be used for sorting and searching area, realize the visualization has important significance. In this paper ,it is realized the visualization of binary sort tree by using object-oriented method and the features of complete binary tree, solve some problems when the method achieved.

tree traversal refers to the process of visiting each node in a specified order. Given the inorder traversal of a binary tree, along with one of its preorder or postorder traversals, the original binary tree can be uniquely identified. Many recursive and non recursive method of construction of the tree from inorder and any of the postorder or preorder traversal have been proposed. In this paper one of the proposed algorithms has been examined. This algorithm computes the wrong tree for some input sequences. We show a particular situation in which the algorithm fails and a solution for this situation is proposed. The proposed a modified non-recursive algorithm for reconstructing a binary tree which generates the correct tree otherwise an error has been reported.

Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.

We introduce a new algorithm for computing an approximately optimal binary search tree with known access probabilities or weights on items. The algorithm is simple to implement and it has two contributions. First, a randomized variant of the algorithm produces a binary search tree with expected performance that improves the previous theoretical guarantees (the performance is dependent on the value of the input random variable). More precisely, if p is the probability of accessing an item, then under expectation the item is found after searching lg1/p+0.087+lg"2(1+p"m"a"x) nodes, where p"m"a"x is the maximal probability among items. The previous best bound was lg1/p+1, albeit deterministic. For the optimal tree our upper bound implies a non-constructive performance bound of H+0.087+lg"2(1+p"m"a"x), where H is the entropy on the item distribution and the previous bound was H+1. The second contribution of the algorithm is a low cost in i/o models of cost such as the cache-oblivious model, while attaining simultaneously the above bound for the produced tree.

We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.

Deletions in binary search trees are difficult to analyse as they are not randomness preserving. We will present a new kind of tree which differs slightly from the standard binary search tree. It will be referred to as an ordered binary search tree as it stores a history element in its nodes, which provides information about the order in which the nodes were inserted. Using this extra information it is possible to design a new randomness preserving and order preserving deletion algorithm.

In evaluating the performance of online algorithms for search trees, one wants to compare them to the best offline algorithm available. In this paper we lower bound the cost of an optimal offline binary search tree using the Kolmogorov complexity of the request sequence. We obtain several applications for this result. First, any offline binary search tree algorithm can be at most a constant factor away from the entropy of the process producing the request sequence. Second, for a fraction 1−1/2m of request sequences of length m on n items the cost of any offline algorithm is Ω(m(logn−1)). Third, the expected cost of splay trees is within a constant factor of the expected cost of an optimal offline binary search tree algorithm in a subset of Markov chains.

We consider three random variables X n , Y n and Z n , which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X n , Y n and Z n are all asymptotically normal as n → ∞ by applying the contraction method.

We present a proof–based automatic synthesis experiment in the context of sorting binary trees, namely the synthesis of the function which inserts an element in a sorted binary tree at the appropriate place. The algorithm is automatically extracted from the automatically produced proof of the conjecture which expresses the existence of the desired output for each appropriate input of the function.This is a case study with the purpose of finding and illustrating general and domain specific inference rules and strategies for efficiently producing proofs from which the desired algorithms can be extracted.The construction of the necessary theory, of the provers, and the experiment itself are performed in the Theorema system.

In this paper, we develop a segment tree data structure for solving dynamic table lookup problems. The proposed dynamic segment tree (DST) uses all of the distinct end points of ranges as the keys based on a new range end point scheme. The new end point scheme generates fewer end points than the traditional end point scheme. DST is implemented as a balanced binary search tree augmented with a range set in each node. The performance of accessing and updating the ranges stored in each node is improved by an efficient range set data structure that combines the priority queue and the interval tree. Based on the proposed data structures, the time complexities of search, insertion, and deletion in a set of N arbitrary ranges are O(log N), O(log N times log Max), and O(Max times log N times log Max), respectively, where Max is the maximum number of ranges covering any address. In practical routing tables, Max is a small constant (six for the routing tables we tested). The memory requirement for DST is O(N log N). The experimental results using real Internet Protocol version 4 (IPv4) routing tables show that both the DST and prefix binary tree on binary tree (PBOB) by Lu et al. (2004) perform much better than the multiway range tree (MRT) by Warkhede et al. (2004) and prefix in B-tree (PIBT) by Lu et al. (2005) in terms of update speed and memory consumption, but DST performs much better than PBOB and a little slower than MRT and PIBT in terms of search speed

Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average-case complexity.We investigate what happens in between by analysing the smoothed height of binary search trees: Randomly perturb a given (adversarial) sequence and then take the expected height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions.On the one hand, we prove tight lower and upper bounds of roughly Θ((1−p)⋅n/p) for the expected height of binary search trees under partial permutations and partial alterations, where n is the number of elements and p is the smoothing parameter. This means that worst-case instances are rare and disappear under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse well balanced instances can become.

Concerning the identity-based binary tree key revocation scheme, the storage and use of binary tree can not be guaranteed in open cloud environment. This paper proposes a distributed key revocation scheme based on shared binary tree. The scheme splits the binary key tree into branches and distributes them to multiple nodes to save. Then multiple nodes work together to rebuild the key. At the same time, this paper optimizes the lookup algorithm during rebuilding. It solves the issues on distributed storage, safe use and fast reconstruction of the binary tree in the open environment. Experiments and analysis show that the scheme has higher efficiency and makes identity-based key revocation scheme run safely in the open environment.

We analyze two bottom-up reduction algorithms over binary trees that represent replaceable data within a certain system, assuming the binary search tree (BST) probabilistic model. These reductions are based on idempotent and nilpotent operators, respectively. In both cases, the average size of the reduced tree, as well as the cost to obtain it, is asymptotically linear with respect to the size of the original tree. Additionally, the limiting distributions of the size of the trees obtained by means of these reductions satisfy a central limit law of Gaussian type.

In this paper we propose using experiments with Balanced-Sample Binary Trees (BSBTrees) as assignments and lecture material in intermediate data structures courses (CS2/3). BSBTrees are composite data structures that have a temporarily constructed form that precedes their normal construction. We present them in the context of binary search trees. To do this we first investigate the retrieval properties of randomly generated binary search trees and show how temporary construction can improve both worst case and average case behavior. We provide a brief analysis of BSBTree performance and description of the classes that can be used for BSBTree implementation. Last we discuss the use of BSBTrees in CS2 and CS3 courses and a survey of student opinions about BSBTrees.

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.

We present a new lock-based algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. Some of the desirable characteristics of our algorithm are: (i) a search operation uses only read and write instructions, (ii) an insert operation does not acquire any locks, and (iii) a delete operation only needs to lock up to four edges in the absence of contention. Our algorithm is based on an internal representation of a search tree and it operates at edge-level (locks edges) rather than at node-level (locks nodes); this minimizes the contention window of a write operation and improves the system throughput. Our experiments indicate that our lock-based algorithm outperforms existing algorithms for a concurrent binary search tree for medium-sized and larger trees, achieving up to 59% higher throughput than the next best algorithm.

We present an O(n4)-time algorithm for the following problem: Given a set of items with known access frequencies, find the optimal binary search tree under the realistic assumption that each comparison can only result in a two-way decision: either an equality comparison or a less-than comparisons. This improves the best known result of O(n5) time, which is based on split tree algorithms. Our algorithm relies on establishing thresholds on the frequency of an item that can occur as an equality comparison at the root of an optimal tree.

We study an order-preserving general purpose data structure for binary data, the LPC-trie. The structure is a compressed trie, using both level and path compression. The memory usage is similar to that of a balanced binary search tree, but the expected average depth is smaller. The LPC-trie is well suited to modem language environments with efficient memory allocation and garbage collection. We present an implementation in the Java programming language and show that the structure compares favorably with a balanced binary search tree.

To solve the RFID tag collision problem, a new anti-collision algorithm is proposed by improving the binary tree search algorithm. Through improving the requesting establishment, this algorithm reduces the probability of collision bits and the number of tags requiring collision detection time by using the even number bits for impact identification. The simulation results show that compared with the traditional binary tree search algorithm and dynamic binary tree search algorithm, this algorithm has obvious advantages in terms of the length of the transmission of binary data. In addition, in terms of the average number of requests, the proposed algorithm provides the same performance with the faster identification process, and reduces the time of the transmission of information

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. In addition to read and write instructions, our algorithm uses (single-word) compare-and-swap (CAS) and bit-test-and-set (SETB) atomic instructions, both of which are commonly supported by many modern processors including Intel~64 and AMD64.In contrast to existing lock-free algorithms for a binary search tree, our algorithm is based on marking edges rather than nodes. As a result, when compared to other lock-free algorithms, modify (insert and delete) operations in our algorithm work on a smaller portion of the tree, thereby reducing conflicts, and execute fewer atomic instructions (one for insert and three for delete). Our experiments indicate that our lock-free algorithm significantly outperforms all other algorithms for a concurrent binary search tree in many cases, especially when contention is high, by as much as 100%.

Splay and randomized search trees (RSTs) are self-balancing binary tree structures with little or no space overhead compared to a standard binary search tree (BST). Both trees are intended for use in applications where node accesses are skewed, for example in gathering the distinct words in a large text collection for index construction. We investigate the efficiency of these trees for such vocabulary accumulation. Surprisingly, unmodified splaying and RSTs are on average around 25% slower than using a standard binary tree. We investigate heuristics to limit splay tree reorganization costs and show their effectiveness in practice. In particular, a periodic rotation scheme improves the speed of splaying by 27%, while other proposed heuristics are less effective. We also report the performance of efficient bit-wise hashing and red–blacktrees for comparison. Copyright © 2001 John Wiley & Sons, Ltd.

A fine analysis is given of the transitional behavior of the average cost of quicksort with median-of-three. Asymptotic formulae are derived for the stepwise improvement of the average cost of quicksort when iterating median-of-threek rounds for all possible values ofk. The methods used are general enough to apply to quicksort with median-of-(2t + 1) and to explain in a precise manner the transitional behaviors of the average cost from insertion sort to quicksort proper. Our results also imply nontrivial bounds on the expected height, "saturation level," and width in a random locally balanced binary search tree.

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.

A given binary resolution proof, represented as a binary tree, is said to be i>minimal if the resolutions cannot be reordered to generate an irregular proof. Minimality extends Tseitin"s regularity restriction and still retains completeness. A linear-time algorithm is introduced to decide whether a given proof is minimal. This algorithm can be used by a deduction system that avoids redundancy by retaining only minimal proofs and thus lessens its reliance on subsumption, a more general but more expensive technique. Any irregular binary resolution tree is made strictly smaller by an operation called i>Surgery, which runs in time linear in the size of the tree. After surgery the result proved by the new tree is nonstrictly more general than the original result and has fewer violations of the regular restriction. Furthermore, any nonminimal tree can be made irregular in linear time by an operation called i>Splay. Thus a combination of splaying and surgery efficiently reduces a nonminimal tree to a minimal one. Finally, a close correspondence between clause trees, recently introduced by the authors, and binary resolution trees is established. In that sense this work provides the first linear-time algorithms that detect minimality and perform surgery on clause trees.

We show that for a random binary search tree with n nodes and Horton-Strahler number Sn, lim n → ∞ P {S n ⩾ ( 1 log 3 + e) log n} = 0 , for all e >0. This result is confirmed by the experimental results of natural scientists and explains why the random binary search tree model is a poor choice for modeling the combinatorial structure of the human lung.

Search in a conventional binary search tree requires three-way key comparison ( ). High-level language support for three-way branch on comparison is rare, and experiments have shown that a modified tree requiring only two-way key comparison (

We consider the problem of building optimal binary search trees . The binary search tree is a widely used data structure for information storage and retrieval. A binary search tree T for a set of keys from a total order is a binary tree in which each node has a key value and all the keys of the left subtree are less than the key at the root and all the keys of the right subtree are greater than the key at the root, this property holding recursively for the left and right subtrees of the tree T . Suppose we are given n keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The optimal binary search tree problem is to construct a binary search tree on these n keys that minimizes the expected access time. One variant of this problem is when only the gaps have nonzero access probabilities, and is called the optimal alphabetic tree problem . Another related problem is when there is no order between the keys and there are probabilities associated only with the gaps and the objective is to build a binary tree with minimum expected weighted path length from the root. This is called the Huffman tree problem . In this survey, we assess known results on the structural properties of the optimal trees, algorithms and lower bounds to construct and to verify optimal trees and heuristics to construct nearly optimal trees and other related results.

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.

In this paper, we propose efficient maximum-likelihood (ML) decoding for binary Kronecker product-based (KPB) codes. This class of codes, have a matrix defined by the n-fold iterated Kronecker product Gn = F⊗n of a binary upper-triangular kernel matrix F, where some columns are suppressed given a specific puncturing pattern. Polar and Reed- Muller codes are well known examples of such KPB codes. The triangular structure of Gn enables to perform ML decoding as a binary tree search for the closest codeword to the received point. We take advantage of the highly regular fractal structure of Gn and the “tree folding” technique to design an efficient ML decoder, enabling to decode relatively longer block lengths than with a standard binary tree search. The tree κ-folding operation transforms the binary tree with N levels into a non-binary tree with N=2κ levels, where the search can be significantly accelerated by a suitable ordering of the branch metrics. For a given κ we can find (n over κ) different folding which lead to decoders with different complexity, for a given code. Using the proposed folded tree decoder, we provide exact ML performances of some Reed-Muller and polar codes over a binary AWGN channel for the block length up to 256.

In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence—any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.

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.