java数据结构和算法——平衡二叉树的介绍
一、二叉排序树可能存在的问题
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在
1、数列{1,2,3,4,5,6}构建的二叉排序树(BST)如下图：
2、上图中二叉排序树(BST)存在的问题
- 左子树全部为空，从形式上看，更像一个单链表
- 插入速度没有影响
- 查询速度明显降低(因为需要依次比较), 不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
3、上图中二叉排序树(BST)存在问题的解决方案
- 使用平衡二叉树(AVL)
二、平衡二叉树(AVL)的基本介绍
- 平衡二叉树是基于二叉排序树的基础上构建的，也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
三、平衡二叉树(AVL)的特点
- 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
- 平衡二叉树的常用实现方法有红黑树算法、AVL算法、替罪羊树算法、Treap算法、伸展树算法等。
四、平衡二叉树(AVL)的图形举例
1、下图示例是平衡二叉树
2、下图示例是平衡二叉树
3、下图示例不是平衡二叉树