共查询到20条相似文献,搜索用时 9 毫秒
1.
David Spuler 《Acta Informatica》1993,30(5):405-407
Andersson [1] presented a search algorithm for binary search trees that uses only two-way key comparisons by deferring equality comparisons until the leaves are reached. The use of a different search algorithm means that the optimal tree for the traditional search algorithm, which has been shown to be computable inO(n
2) time by Knuth [3], is not optimal with respect to the different search algorithm. This paper shows that the optimal binary search tree for Andersson's search algorithm can be computed inO(nlogn) time using existing algorithms for the special case of zero successful access frequencies, such as the Hu-Tucker algorithm [2]. 相似文献
2.
Eyas El-Qawasmeh 《Information Processing Letters》2004,92(5):257-265
Word prediction methodologies depend heavily on the statistical approach that uses the unigram, bigram, and the trigram of words. However, the construction of the N-gram model requires a very large size of memory, which is beyond the capability of many existing computers. Beside this, the approximation reduces the accuracy of word prediction. In this paper, we suggest to use a cluster of computers to build an Optimal Binary Search Tree (OBST) that will be used for the statistical approach in word prediction. The OBST will contain extra links so that the bigram and the trigram of the language will be presented. In addition, we suggest the incorporation of other enhancements to achieve optimal performance of word prediction. Our experimental results showed that the suggested approach improves the keystroke saving. 相似文献
3.
Arne Andersson 《Software》1991,21(10):1125-1128
An algorithm for searching in a binary search tree using two-way comparisons is presented. The number of comparisons required by this algorithm is only one more than when using three-way comparisons. Since most high-level programming languages do not supply three-way comparisons, the number of comparisons used de facto is reduced by a factor of two. We give experimental results to indicate the speed-up that may be achieved by the presented algorithm. 相似文献
4.
5.
Tomi A. Pasanen 《Theoretical computer science》2010,411(43):3867-3872
We consider random binary search trees when the input consists of a multiset, i.e. a set with multiple occurrences of equal elements, and prove that the randomized insertion and deletion algorithms given by Martínez and Roura (1998) [4] produce random search trees regardless of multiplicities; even if all the elements are equal during the tree updates, a search tree will maintain its randomness. Thus, equal elements do not degenerate a random search tree and they need not to be handled in any special way. We consider also stability of a search tree with respect to its inorder traversal and prove that the algorithms used produce stable trees. This implies an implicit indexing of equal elements giving another proof that multiplicities do not pose problems when maintaining random binary search trees. 相似文献
6.
7.
《国际计算机数学杂志》2012,89(7):803-812
We present a Markov chain model for the analysis of the behaviour of binary search trees (BSTs) under the dynamic conditions of insertions and deletions. The model is based on a data structure called a lineage tree, which provides a compact representation of different BST structures while still retaining enough information to model the effect of insertions and deletions and to compute average path length and tree height. Different lineages in the lineage tree correspond to states in the Markov chain. Transition probabilities are based on the number of BST structures corresponding to each lineage. The model is based on a similar lineage tree model developed for B-trees. The BST model is not intended for practical computations, but rather as a demonstration of the generalizability of the lineage tree approach for modeling data structures such as B-trees, B*-trees, B+-trees, BSTs, etc. 相似文献
8.
Much has been said in praise of self-adjusting data structures, particularly self-adjusting binary search trees. Self-adjusting trees are most suited to skewed key-access distributions as the techniques attempt to place the most commonly accessed keys near the root of the tree. Theoretical bounds on worst-case and amortized performance (i.e. performance over a sequence of operations) have been derived which compare well with those for optimal binary search trees. In this paper, we compare the performance of three different techniques for self-adjusting trees with that of AVL and random binary search trees. Comparisons are made for various tree sizes, levels of key-access-frequency skewness and ratios of insertions and deletions to searches. The results show that, because of the high cost of maintaining self-adjusting trees, in almost all cases the AVL tree outperforms all the self-adjusting trees and in many cases even a random binary search tree has better performance, in terms of CPU time, than any of the self-adjusting trees. Self-adjusting trees seem to perform best in a highly dynamic environment, contrary to intuition. 相似文献
9.
10.
11.
《Robotics and Autonomous Systems》2014,62(10):1440-1452
Unsupervised data clustering can be addressed by the estimation of mixture models, where the mixture components are associated to clusters in data space. In this paper we present a novel unsupervised classification algorithm based on the simultaneous estimation of the mixture’s parameters and the number of components (complexity). Its distinguishing aspect is the way the data space is searched. Our algorithm starts from a single component covering all the input space and iteratively splits components according to breadth first search on a binary tree structure that provides an efficient exploration of the possible solutions. The proposed scheme demonstrates important computational savings with respect to other state-of-the-art algorithms, making it particularly suited to scenarios where the performance time is an issue, such as in computer and robot vision applications. The initialization procedure is unique, allowing a deterministic evolution of the algorithm, while the parameter estimation is performed with a modification of the Expectation Maximization algorithm. To compare models with different complexity we use the Minimum Message Length information criteria that implement the trade-off between the number of components and data fit log-likelihood. We validate our new approach with experiments on synthetic data, and we test and compare to related approaches its computational efficiency in data-intensive image segmentation applications. 相似文献
12.
基于多维二进制搜索树的异常检测技术 总被引:1,自引:0,他引:1
将多维二进制搜索树(kd树)应用于异常检测,用kd树对网络数据进行组织、建立用户轮廓并以此为基础实现了一个异常检测系统,通过实验给出了系统对不同种类攻击的检测效果。实验结果表明,kd树在异常检测中具有很高的适用性。 相似文献
13.
We present an algorithm for generating a binary search tree that allows efficient computation of piecewise affine (PWA) functions defined on a polyhedral partition. This is useful for PWA control approaches, such as explicit model predictive control, as it allows the controller to be implemented online with small computational effort. The computation time is logarithmic in the number of regions in the PWA partition. 相似文献
14.
Will D. Gillett 《Acta Informatica》1984,21(2):183-192
Summary A data encoding scheme involving binary tree encodements is presented and analyzed. A closed-form formula for the number of n-bit legal memory configurations is developed. It is shown that the storage capacity loss due to the use of this scheme is not significant for large n.This work was supported in part under the NCHSR Grant HS03792 and the NIH Grant R R00396 相似文献
15.
16.
17.
18.
基于AVL树的事件响应函数搜索算法虽然搜索速度快,但容易在初始化时陷入局部最优结构,且未考虑到机器人在不同巡检阶段事件量的聚集性.为此,设计一种动态搜索权值构建AVL树的算法,利用单位时间内事件发生量影响其搜索权值,使巡检机器人在运行过程中根据某类事件数量动态调整AVL树结构,优化查找效率.利用VS2005开发仿真模型,仿真结果表明,该算法能够根据事件访问量动态调整AVL树,且巡检机器人现场测试结果表明,该算法使巡检效率提高25%以上. 相似文献
19.
20.
《Information Processing Letters》1986,23(3):123-126
Given a sequence of n ordered but not sorted b-bit integers, an algorithm is described to select the kth smallest by reducing the length of the original sequence until only the required kth value or those equal to the kth remain. Using the time to add two bits as the unit, a running time of O(b log n) is obtained by employing O(n) simple processors arranged in a binary tree. The algorithm is then adapted to run on a binary tree of processors with N leaves, where N log N ⩽ n, in O(bn/N) time for an optimal cost of O(bn). 相似文献