type
status
date
slug
summary
tags
category
icon
password
AI summary
1、看一个案例(说明二叉排序树可能的问题)
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.
左边BST 存在的问题分析: 1.左子树全部为空，从形式上看，更像一个单链表. 2.插入速度没有影响 查询速度明显降低(因为需要依次比较), 3.不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢 4.解决方案-平衡二叉树(AVL)
2、基本介绍
平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，
可以保证查询效率较高
。
具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
举例说明, 看看下面哪些AVL树, 为什么?
①②都是AVL树，③不是
3、应用案例-单旋转(左旋转)
要求: 给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}
3.1、左旋转代码实现
4、应用案例-单旋转(右旋转)
要求: 给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}
4.1、右旋转代码实现
5、应用案例-双旋转
前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列
int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL树.
int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL树
解题思路
5.1、双旋转代码实现
6、代码整合
- 作者:IT小舟
- 链接:https://www.codezhou.top/article/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91(AVL%E6%A0%91)
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。