平衡二叉树AVL

文章列表

平衡二叉树AVL

平衡二叉树|B树|B+树

1. 平衡二叉树
- 1.1 如何调整最小不平衡子树
- 1.2 左旋、右旋代码实现
- 1.3 解决导致不平衡的四种情况
2. B树|B+树
- 2.1 2-3树
- 2.2 B树的插入和删除
- - 插入：
  - 删除：

1. 平衡二叉树

平衡二叉树解决了二叉排序树退化为单链表的问题；
平衡二叉树也称为自平衡二叉搜索树或AVL树；
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis；
平衡二叉树本质还是二叉排序树；
平衡二叉树的限制：空树或左右子树高度差的绝对值不超过1；
平衡因子：左子树高度-右子树高度，取值范围为{-1,0,1}；
调整最小不平衡子树使得整个二叉排序树平衡；
查找时间复杂度：O(log₂ⁿ)，借助递推公式：N_h=N_h-1+N_h-2+1；

在这里插入图片描述

1.1 如何调整最小不平衡子树

四种不平衡子树：LL、LR、RL、RR，分别表示1）在root树的左子节点的左子树插入节点导致不平衡；1）在root树的左子节点的右子树插入节点导致不平衡；1）在root树的右子节点的左子树插入节点导致不平衡；1）在root树的右子节点的右子树插入节点导致不平衡；
LL、RR为两种基本情况，对应解决方案为单旋转，分别为：右旋、左旋；
LL：树右旋

RR：树左旋
LR、RL为两种复杂情况，对应解决方案为双旋转，分别为：先左旋再右旋、先右旋再左旋；
LR：左子树左旋+树右旋

在这里插入图片描述
RL：右子树右旋+树左旋

1.2 左旋、右旋代码实现

左旋：
在这里插入图片描述

/
* 左旋
*/
private void leftRotate() {// 1.创建新节点，与当前根节点值一致TreeNode newNode = new TreeNode(val);// 2.新节点的左子树为root的左子树newNode.left=left;// 3. 新节点的右子树为root的右子树的左子树newNode.right=right.left;// 4.root的值替换为其右子节点的值val=right.val;// 5.root的右子树为右子树的右子树right=right.right;// 6.当前节点的左子树为新节点left=newNode;
}

右旋：
在这里插入图片描述

/* 右旋*/
private void rightRotate() {// 1.创建新节点，与当前根节点值一致TreeNode newNode = new TreeNode(val);// 2.新节点的右子树为root的右子树newNode.right=right;// 3. 新节点的左子树为root的左子树的右子树newNode.left=left.right;// 4.root的值替换为其左子节点的值val=left.val;// 5.root的左子树为左子树的左子树left=left.left;// 6.当前节点的右子树为新节点right=newNode;
}

1.3 解决导致不平衡的四种情况

class AVLTree{public TreeNode root;public AVLTree(TreeNode root){this.root=root;}public AVLTree() {}/* 插入节点*/public void insert(TreeNode node){// 根节点if (root==null){root=node;}else{root.insert(node);}}/* 中序遍历*/public void inOrder(){if (root==null){return;}root.inOrder();}/* 层序遍历*/public void levelOrder(){if (root==null){return;}root.levelOrder();}
}class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val){this.val=val;}public TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}/* 返回以当前节点为根节点的树的高度* @return*/public int getHeight(){return Math.max(left==null?0:left.getHeight(),right==null?0:right.getHeight())+1;}/* 返回以当前节点左子树的高度* @return*/public int getLeftHeight(){if (left==null){return 0;}return left.getHeight();}/* 返回以当前节点右子树的高度* @return*/public int getRightHeight(){if (right==null){return 0;}return right.getHeight();}@Overridepublic String toString() {return "TreeNode{" +"val=" + val +'}';}/* 新增节点，满足二叉排序树要求* @param node*/public void insert(TreeNode node) {if (node==null){return;}// 比较当前节点与node节点的大小关系if (node.val<val){if (left==null){left=node;}else{left.insert(node);}}else{if (right==null){right=node;}else{right.insert(node);}}// 左旋：右子树高度过大if (getRightHeight()-getLeftHeight()>1){// RR：右子树的右子树上插入节点导致不平衡if (right.getRightHeight()-right.getLeftHeight()>=1){leftRotate();}else if (right.getLeftHeight()-right.getRightHeight()>=1){ // RL：右子树的左子树上插入节点导致不平衡// 右子树进行右旋right.rightRotate();// 整棵树左旋leftRotate();}}else if (getLeftHeight()-getRightHeight()>1){ // 右旋：左子树高度过大// LL：左子树的左子树上插入节点导致不平衡if (left.getLeftHeight()-left.getRightHeight()>=1){rightRotate();}else if (left.getRightHeight()-left.getLeftHeight()>=1){ // LR：右左子树的右子树上插入节点导致不平衡// 左子树进行左旋left.leftRotate();// 整棵树右旋rightRotate();}}}/* 左旋*/private void leftRotate() {// 1.创建新节点，与当前根节点值一致TreeNode newNode = new TreeNode(val);// 2.新节点的左子树为root的左子树newNode.left=left;// 3. 新节点的右子树为root的右子树的左子树newNode.right=right.left;// 4.root的值替换为其右子节点的值val=right.val;// 5.root的右子树为右子树的右子树right=right.right;// 6.当前节点的左子树为新节点left=newNode;}/* 右旋*/private void rightRotate() {// 1.创建新节点，与当前根节点值一致TreeNode newNode = new TreeNode(val);// 2.新节点的右子树为root的右子树newNode.right=right;// 3. 新节点的左子树为root的左子树的右子树newNode.left=left.right;// 4.root的值替换为其左子节点的值val=left.val;// 5.root的左子树为左子树的左子树left=left.left;// 6.当前节点的右子树为新节点right=newNode;}/* 中序遍历*/public void inOrder(){if (left!=null){left.inOrder();}System.out.println("node:"+val);if (right!=null){right.inOrder();}}/* 层序遍历*/public void levelOrder() {Deque<TreeNode> queue=new ArrayDeque<>();queue.offer(this);while (!queue.isEmpty()){TreeNode cur = queue.poll();System.out.println("node:"+cur.val);if (cur.left!=null){queue.offer(cur.left);}if (cur.right!=null){queue.offer(cur.right);}}}
}