问AVL为何物,我愿称之为转转转
AVL(自平衡二叉树)
从AVL树的概念,AVL树的创建思想与算法步骤,AVL树的代码实现与分析展开阐述并图解分析
若有不足之处,欢迎指出
博主空间
https://blog.csdn.net/JOElib?type=blog广度优先算法
目录
AVL树的概述🐼
为什么有AVL树🦁
BST的缺陷😶🌫️
AVL的优点 😶🌫️
何为AVL🦁
AVL的特征😶🌫️:
AVL树的创建思路与算法步骤🐼
图解😶🌫️:
代码实现与分析🐼
节点类中🦁
1.右旋的核心代码🐻
代码分析🐨:
2.左旋的核心代码🐻
代码分析🐨:
3.判断树高的核心代码(最难)🐻
代码分析🐨:
4.建立左高与右高的方法🐻
代码分析🐨:
5,创建一个添加节点的方法🐻
代码分析🐨:
AVL树类中🦁
6.对底层节点的方法调用即可🐻
代码分析🐨:
结论🐼
AVL树的概述🐼
为什么有AVL树🦁
BST的缺陷😶🌫️
- 如果将一个有序列表构造成BST(二叉排序树)时,该树会变成一棵只有右子树或者只有左子树的二叉树,变相变成一个单向链表
- 由于变成了单向链表,其检索效率大大降低,不能发挥BST的优势
- 由于还要和左子树或者是右子树进行比较,检索效率可能比单向链表还低
AVL的优点 😶🌫️
- 不存在只有左子树或者是右子树的情况,检索效率大大增大
何为AVL🦁
AVL的特征😶🌫️:
- AVL树规定左子树与右子树的高度差不可以超过1,并且在左子树和右子树中.以他们为根节点的子树仍然是一颗AVL树
AVL树的创建思路与算法步骤🐼
- 左旋思想与步骤
- 创建一个新的节点,其权值等于原根节点的权值
- 新节点的左子树等于原根节点的左子树
- 新节点的右子树等于原根结点的右子树的左子树
- 原根节点的权值等于其右子节点的权值
- 原根结点的右子树等于其右子树的右子树
- 原根结点的左子节点等于新节点
- 右旋思想与步骤
- 创建一个新的节点,其权值等于原根节点的权值
- 新节点的右子树等于原根结点的右子树
- 新节点的左子树等于原根结点的左子树的右子树
- 原根结点的权值等于其左子节点的权值
- 原根结点的左子树等于其左子树的左子树
- 原根结点的右子节点等于新节点
图解😶🌫️:
代码实现与分析🐼
节点类中🦁
1.右旋的核心代码🐻
public void rightRotation() { var newNode = new Node(value); newNode.right = right; newNode.left = left.right; value = left.value; left = left.left; right = newNode; }代码分析🐨:
略,按照算法步骤即可
2.左旋的核心代码🐻
public void leftRotation() { var newNode = new Node(value); newNode.left = left; newNode.right = right.left; value = right.value; right = right.right; left = newNode; }代码分析🐨:
略,根据算法步骤即可
3.判断树高的核心代码(最难)🐻
public int height() { return Math.max(left != null ? left.height() : 0,right != null ? right.height() : 0) + 1; }代码分析🐨:
- 这里主要运用的思想是递归与回溯思想,利用递归,底层创建了许多的Math.max()
- 又根据谁调用,返回值给谁的原则,成就了该方法
- 以下是图解:
4.建立左高与右高的方法🐻
public int leftHeight() { if (left == null) { return 0; } return left.leftHeight(); } public int rightHeight() { if (right == null) { return 0; } return right.rightHeight(); }代码分析🐨:
-
最重要的就是校验是否为空,其他直接调取即可
5,创建一个添加节点的方法🐻
public void add(Node node) { if (node == null) { return; } if (node.value >= value) { if (right != null) { right.add(node); }else { right = node; } }else { if (left != null) { left.add(node); }else { left = node; } } if (rightHeight() - leftHeight() > 1) { if (right != null && right.leftHeight() > right.rightHeight()) { right.rightRotation(); } leftRotation(); }else if (leftHeight() > rightHeight()) { if (left != null && left.rightHeight() > left.leftHeight()) { left.leftRotation(); } rightRotation(); } }代码分析🐨:
- 主要对左旋右旋操作进行讲解,前面的在BST处有详细讲解
- 如果右子树高度与左子树高度差值大于一,说明要进行左旋操作
- 当右子树不为空时,且右子树的左子树高度比右子树的右子树高度大,我们先要对右子树进行右旋,再进行左旋
- 如果左子树高度与右子树高度差值大于一,说明要进行右旋操作
- 当左子树不为空,且左子树的右子树高度比左子树的左子树高度大,我们先要对左子树进行左旋,再进行右旋
原因图解😶🌫️:
AVL树类中🦁
6.对底层节点的方法调用即可🐻
public class AVLTree { public Node root; public int height(Node node) { if (node == null) { return 0; } return node.height(); } public void add(Node node) { if (root == null) { root = node; }else { root.add(node); } }代码分析🐨:
略
结论🐼
主要是对AVL树旋转问题的讲解,可能有点抽象,但是还是可以理解的,我来总结以下必须要掌握的几点:
1.AVL树旋转的算法步骤
2.高度的递归求解
3.为什么要有双旋转
🚇下一站:BST(二叉排序树)