TAVL:一种高效索引结构

摘要

本文在简要介绍线索二叉树和高度平衡二叉树的查找、构造、更新方法的基础上,将二者结合,提出了线索高度平衡二叉树(TAVL)结构,这种结构添加、删除、查找单个节点操作的复杂度与高度平衡二叉树相同(O(log2n))而优于线索二又树(O(n)),查找中序下相邻节点操作的复杂度(O(log2n))低于线索二叉树与高度平衡二叉树(O(n)).