type
status
date
slug
summary
tags
category
icon
password
AI summary

1、看一个案例(说明二叉排序树可能的问题)

给你一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST), 并分析问题所在.
notion image
左边BST 存在的问题分析: 1.左子树全部为空,从形式上看,更像一个单链表. 2.插入速度没有影响 查询速度明显降低(因为需要依次比较), 3.不能发挥BST的优势,因为每次还需要比较左子树,其查询速度比单链表还慢 4.解决方案-平衡二叉树(AVL)

2、基本介绍

平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树,
可以保证查询效率较高
。 具有以下特点:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 举例说明, 看看下面哪些AVL树, 为什么?
notion image
①②都是AVL树,③不是

3、应用案例-单旋转(左旋转)

要求: 给你一个数列,创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}
notion image

3.1、左旋转代码实现

4、应用案例-单旋转(右旋转)

要求: 给你一个数列,创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}
notion image

4.1、右旋转代码实现

5、应用案例-双旋转

前面的两个数列,进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下,单旋转不能完成平衡二叉树的转换。比如数列 int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到,并没有转成 AVL树.
notion image
int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到,并没有转成 AVL树
解题思路
notion image
notion image

5.1、双旋转代码实现

6、代码整合

 
普里姆算法排序算法-算法时间复杂度和空间复杂度概念 详细讲解