二叉查找树的一种优化结构——Treap  

One Kind of Two Fork Seek Tree Optimizes Structure——Treap

作　　者：林厚从[1] LIN Hou-cong　

机构地区：[1]南京大学,江苏,南京,210088

出　　处：《电脑知识与技术（过刊）》2007年第14期444-,448,共2页Computer Knowledge and Technology

摘　　要：二叉查找树是一种重要的数据结构,但它有一个致命的缺点,就是会退化成线性表,解决这一问题的常用方法是采用平衡树、红-黑树等复杂的数据结构,实现起来比较困难.本文提出一种较为简单的优化结构-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.

关 键 词：二叉查找树 Treap 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]