接近最优高度的二分搜索树

• 作者: 于长云 伍颖文
• 来源期刊: 微小型计算机开发与应用
• 学科: 工学
• 关键词: 数据结构 二分搜索树
• 年，卷（期）: 1994,（1）
• 页码范围: 24-28
• 页数: 5页
• 分类号: TP311.12

摘要

本文研究对称二分Ｂ树（Ｓｙｍｍｅｔｒｉｃ Ｂｉｎａｒｙ Ｂ－ｔｒｅｅｓ）的一种拓广形式，即ＳＢＢ（Ｋ）树。这种树结构高度仅为［（１＋１／Ｋ）ｌｏｇ（ｎ＋１）］，通过改变Ｋ值，树重构平均代价为Ｏ（ｏｌｇｎ），维护算法在最坏情况时仅耗费常数代价。