摘要
二叉查找树是一种重要的数据结构,但它有一个致命的缺点,就是会退化成线性表,解决这一问题的常用方法是采用平衡树、红-黑树等复杂的数据结构,实现起来比较困难.本文提出一种较为简单的优化结构-Treap,它是采用随机化的思想,将二叉查找树和堆有效结合在一起,从而实现相对平衡的二叉树结构.
Binary search tree is an important data structure,it has a fatal flaw in that it will degenerate into linear list.The common method used to solve this problem is to balance the tree,the red-black tree or other complex data structure,and relatively difficult.This paper presents a relatively simple optimization of structure-Treap.It is the use of random ideas and binary search trees and heap together thus relatively balanced binary tree structure.
出处
《电脑知识与技术（过刊）》
2007年第14期444-,448,共2页
Computer Knowledge and Technology
