自平衡二叉查找树(Java实现)(2)

从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点,接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转,而每次 AVL 旋转耗费恒定的时间,删除处理在整体上耗费 O(log n) 时间。

删除操作需要考虑的情况较多,具体见代码实现吧。

3.查找

在AVL树中查找同在一般BST完全一样的进行,所以耗费 O(log n) 时间,因为AVL树总是保持平衡的。不需要特殊的准备,树的结构不会由于查询而改变。(这是与伸展树查找相对立的,它会因为查找而变更树结构。)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/d3ef82fa428d236f40e2d34eb945ea1d.html