从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点,接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转,而每次 AVL 旋转耗费恒定的时间,删除处理在整体上耗费 O(log n) 时间。
删除操作需要考虑的情况较多,具体见代码实现吧。
3.查找在AVL树中查找同在一般BST完全一样的进行,所以耗费 O(log n) 时间,因为AVL树总是保持平衡的。不需要特殊的准备,树的结构不会由于查询而改变。(这是与伸展树查找相对立的,它会因为查找而变更树结构。)