平衡二叉树（AVL树）

本文主要是介绍平衡二叉树（AVL树），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

假如有个数列{1,2,3,4,5,6} 创建一个二叉排序树

1）左子树全部为空，更像一个单链表

2）插入速度没有影响

3）查询速度明显降低（因为需要依次比较），不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢

4）解决方案—平衡二叉树（AVL）

平衡二叉树：

　　　　1）平衡二叉树又叫平衡二叉搜索树，可以保证查询效率高

　　　　2）特点：一个空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一个平衡二叉树。常用实现方法：红黑树、AVL、替罪羊树、Treap、伸展树等

这篇关于平衡二叉树（AVL树）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！