Smoothed analysis of binary search trees

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.     

Online shape learning using binary search trees

In this paper we propose an online shape learning algorithm based on the self-balancing binary search tree data structure for the storage and retrieval of shape templates. This structure can also be used for classification purposes. We introduce a similarity measure with which we can make decisions on how to traverse the tree and even backtrack through the search path to find more candidate matches. Then we describe every basic operation a binary search tree can perform adapted to such a tree of shapes. Note that as a property of binary search trees, all operations can be performed in O(logn)$O(\log n)$ time and are very efficient. Finally, we present experimental data evaluating the performance of the proposed algorithm and demonstrating the suitability of this data structure for the purpose it was designed to serve.     

Optimal binary search trees with costs depending on the access paths

We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexities of both algorithms are O(n^k+2) and O(n^k+1), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys which are paths of special kinds in binary search trees. Finally, using generating functions, we present an exact analysis of the number of steps performed by the algorithms.     

Query costs in HB(1) trees versus 2–3 trees

Query costs in random AVL trees are compared to those in random 2–3 trees. Both data structures are assumed to reside in main storage. Costs are calculated in terms of the number of node visits and key comparisons required to find a match or no match for a given key. The comparison is based upon theoretical concepts and implementation dependent considerations; e.g., data and instruction fetch. It is shown that if the cost of a key comparison is greater than or equal to the cost of a node access, then AVL trees are more advantageous.     

A method for constructing binary search trees by making insertions at the root

It is possible to construct a binary search tree by inserting items at the root instead of adding them as leaves. When used for sorting, the method has several desirable properties, including (a) fewer comparisons in the best case, (b) fewer comparisons in the worst case, (c) a reduced variance, and (d) good performance when the items are already nearly sorted or nearly reverse sorted. For applications in which the tree is searched for existing items as well as having new items added to it (e.g., in the construction of a symbol table), the tree can be made to exhibit stacklike behavior, so that the fewest comparisons are required to locate the most recently used items.     

Untangling the balancing and searching of balanced binary search trees

A balanced binary search tree can be characterized by two orthogonal issues: its search strategy and its balancing strategy. In this paper, we show how to decouple search and balancing strategies so that they can be expressed independently of each other, communicating only by basic operations such as rotations. Different balancing strategies, such as red–black trees and splay trees, and different search applications, such as key search and rank search, can be combined arbitrarily. As a new result, we show how optimal string search can be expressed as a search application on any balanced binary tree. We implement our framework in C++, with the heavy use of templates and inlining. It keeps balancing and searching separate, while still delivering a performance that compares favorably to widely used binary tree implementations. Common services, such as correctness checks and timing measurements, do not have to be rewritten for each tree implementation. The common framework simplifies experimentation with trees and search algorithms; as a demonstration, we present some simple comparisons of red–black trees, splay trees and treaps. Copyright © 2003 John Wiley & Sons, Ltd.     

Self-organizing maps whose topologies can be learned with adaptive binary search trees using conditional rotations

Numerous variants of Self-Organizing Maps (SOMs) have been proposed in the literature, including those which also possess an underlying structure, and in some cases, this structure itself can be defined by the user. Although the concepts of growing the SOM and updating it have been studied, the whole issue of using a self-organizing Adaptive Data Structure (ADS) to further enhance the properties of the underlying SOM, has been unexplored. In an earlier work, we impose an arbitrary, user-defined, tree-like topology onto the codebooks, which consequently enforced a neighborhood phenomenon and the so-called tree-based Bubble of Activity (BoA). In this paper, we consider how the underlying tree itself can be rendered dynamic and adaptively transformed. To do this, we present methods by which a SOM with an underlying Binary Search Tree (BST) structure can be adaptively re-structured using Conditional Rotations (CONROT). These rotations on the nodes of the tree are local, can be done in constant time, and performed so as to decrease the Weighted Path Length (WPL) of the entire tree. In doing this, we introduce the pioneering concept referred to as Neural Promotion, where neurons gain prominence in the Neural Network (NN) as their significance increases. We are not aware of any research which deals with the issue of Neural Promotion. The advantage of such a scheme is that the user need not be aware of any of the topological peculiarities of the stochastic data distribution. Rather, the algorithm, referred to as the TTOSOM with Conditional Rotations (TTOCONROT), converges in such a manner that the neurons are ultimately placed in the input space so as to represent its stochastic distribution, and additionally, the neighborhood properties of the neurons suit the best BST that represents the data. These properties have been confirmed by our experimental results on a variety of data sets. We submit that all these concepts are both novel and of a pioneering sort.     

ISA [k] trees: A class of binary search trees with minimal or near minimal internal path length

In recent years several authors have investigated binary search trees with minimal internal path length. In this paper we propose relaxing the requirement of inserting all nodes on one level before going to the next level. This leads to a new class of binary search trees called ISA [k] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[k] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[k] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2] or ISA[3] trees for best performance.     

Assembling approximately optimal binary search trees efficiently using arithmetics

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₂(1+pmax) nodes, where pmax 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₂(1+pmax), 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.     

An analytic approach to the height of binary search trees

By using analytic tools it is shown that the expected value of the heightH _n of binary search trees of sizen is asymptotically given by EH _n =c logn+ (log logn) and its variance by VH _n = ((log logn)²), wherec=4.31107 …. The same bounds have been obtained by Devroye and Reed [3] by completely different methods. Dedicated to Philippe Flajolet on the occasion of his 50th birthday This research was supported by the Austrian Science Foundation FWF, Grant P10187-MAT. Online publication September 22, 2000.     

The Variance of the height of binary search trees

By using analytic tools it is shown that the variance E(H_n−EH_n)² of the height H_n of binary search trees of size n is bounded.     

折半搜索法预测二元混合物的共沸点

在化工分离过程设计中,共沸点预测的作用十分重要,目前常用的方法有牛顿迭代和牛顿同伦等,都需要求解大型非线性方程组,且牛顿迭代法易发散,本文提出修正UNIFAC模型的逐次代入法同时与折半搜索联合的算法,既克服牛顿迭代计算时因取初值不合适时而容易发散的缺点,又不需要求解大型非线性方程组,且计算速度快,计算中对逐次代入法进行改进,使温度初值的取法更简捷,且无发散现象,通过验证乙醇-苯等10多种二元混合物,计算过程均可在1 MS以内完成,计算所得共沸点与文献所载实验值比较,平均误差＜1%,共沸点组成与文献所载实验值比较,平均误差＜2%,证明该法不但可用于二元混合物共沸点预测,又可在相应大型数据库中查找可产生共沸效果的混合物.     

基于二进制数据库的信息搜索算法

提出了一个有效的雷达信息搜索算法。该算法基于对二进制雷达记录数据库的分析,建立了可视化的数据结构,提出了信息搜索的单支树组织模型,采用深度优先和回溯算法简化了搜索复杂度,成功地解决了二进制数据文件的结构化处理问题,为使用、操作记录数据库提供了算法基础。实践证明,该方法简便、稳定,能快捷地处理信息搜索问题。     

Binary search with delayed and missing answers

How many questions are necessary and sufficient to guess an unknown number x in the set S={1,2,…,n}, by using only comparison questions, that is questions of the type “Is x?a?”, a∈S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d?0 and c=1.     

A function for generating nearly balanced binary search trees from sets of non-random keys

A function for generating nearly balanced binary search trees from sets of non-random keys is described. This function can be used in hashing organization where collisions are resolved by construction of binary trees. In particular it can be used as the secondary function in the relatively new technique of dynamic hashing.