平衡二叉树
2021/12/26 23:09:45
本文主要是介绍平衡二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、什么是平衡二叉树
平衡因子(Balance Factor)
简称BF:BF(T) = h(l) - h(r),其中 h(l)和 h(r)分别是T的左、右子树的高度。
平衡二叉树(Balance Binary Tree)(AVL树)
空树,或者任一节点左、右子树的高度绝对值不超过1,|BF(T)|<=1。本质是一颗改进后的二叉搜索树。
2、二叉搜索树
具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
public void insertTree(Node node,int val){ if(node==null){ root = new Node(val); return; } if(val>= node.val){ if(node.right==null){ node.right = new Node(val); return; } insertTree(node.right,val); }else { if(node.left==null){ node.left = new Node(val); return; } insertTree(node.left,val); } }
上面就是排序树的建立方法,我们可以发现的树会有很多空节点。
平衡二叉树
如何判断是一棵二叉树?
只要左右节点的高度差小于二,那么他是一个平衡二叉树。
首先需要获得树的高度,层序遍历
public int treeHeight(Node node){ if(node==null){ return 0; } Queue<Node> queue = new LinkedList<>(); queue.offer(node); int preQueueSize = queue.size(); int height = 1; while (!queue.isEmpty()){ if(preQueueSize==0){ preQueueSize=queue.size(); height++; } preQueueSize--; Node queuePoll = queue.poll(); if(queuePoll.left!=null){ queue.offer(queuePoll.left); } if(queuePoll.right!=null){ queue.offer(queuePoll.right); } } return height; }
判断其是二叉树
public boolean isBalance(Node node){ if(node==null){ return true; } if(!isBalance(node.left)){ return false; } if(!isBalance(node.left)){ return false; } return Math.abs(treeHeight(node.left) - treeHeight(node.right)) < 2; }
构建二叉树
当我们插入新的节点的数据
RR 失衡
public Node rightRightRotation(Node node){ Node returnNode = node.right; node.right = returnNode.left; returnNode.left = node; return returnNode; }
RL 失衡
// RL 旋转 先右后左旋转 即右旋变为RR 再左单旋转 public Node rightLeftRotation(Node node){ Node nodeRight = node.right; Node returnNode = nodeRight.left; nodeRight.left = returnNode.right; returnNode.right = nodeRight; // 左单旋转 node.right = returnNode.left; returnNode.left = node; return returnNode; }
LL 失衡
// LL 旋转 右单旋转 public Node leftLeftRotation(Node node){ Node returnNode = node.left; node.left = returnNode.right; returnNode.right = node; return returnNode; }
LR 失衡
// LR 旋转 先左后右旋转 即先左旋变为LL 再右旋 public Node leftRightRotation(Node node){ // 先左旋转 Node nodeLeft = node.left; Node returnNode = nodeLeft.right; nodeLeft.right = returnNode.left; returnNode.left = nodeLeft; // 右单旋转 node.left = returnNode.right; returnNode.right = node; return returnNode; }
全部代码
package com.company; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Node { int val; Node left; Node right; public Node(int val) { this.val = val; } } class AVLTree{ Node root; // 中序遍历 public void middleView(Node node){ if(node==null){ return; } middleView(node.left); System.out.println(node.val); middleView(node.right); } // 迭代 中序遍历 public void middleViewStack(Node node){ Stack<Node> stack = new Stack<>(); // 我们需要有个node 辅助来记录之前的值 Node assitNode = node; while (!stack.empty()||assitNode!=null){ if(assitNode==null){ assitNode = stack.pop(); System.out.println(assitNode.val); assitNode = assitNode.right; continue; } stack.push(assitNode); assitNode = assitNode.left; } } public void insertTree(Node node,int val){ if(node==null){ root = new Node(val); return; } if(val>= node.val){ if(node.right==null){ node.right = new Node(val); return; } insertTree(node.right,val); }else { if(node.left==null){ node.left = new Node(val); return; } insertTree(node.left,val); } } public Node insertAvlTree(Node node, int val){ if(node==null){ return new Node(val); } if(val>=node.val){ node.right = insertAvlTree(node.right,val); if(Math.abs(treeHeight(node.left)-treeHeight(node.right))>=2){ // 代表不是平衡二叉树 if(val>node.right.val){ return rightRightRotation(node); }else{ return rightLeftRotation(node); } } }else { node.left = insertAvlTree(node.left,val); if(Math.abs(treeHeight(node.left)-treeHeight(node.right))>=2){ // LL 右单旋转 if(val< node.left.val){ return leftLeftRotation(node); }else { // LR return leftRightRotation(node); } } } return node; } public int treeHeight(Node node){ if(node==null){ return 0; } Queue<Node> queue = new LinkedList<>(); queue.offer(node); int preQueueSize = queue.size(); int height = 1; while (!queue.isEmpty()){ if(preQueueSize==0){ preQueueSize=queue.size(); height++; } preQueueSize--; Node queuePoll = queue.poll(); if(queuePoll.left!=null){ queue.offer(queuePoll.left); } if(queuePoll.right!=null){ queue.offer(queuePoll.right); } } return height; } // LL 旋转 右单旋转 public Node leftLeftRotation(Node node){ Node returnNode = node.left; node.left = returnNode.right; returnNode.right = node; return returnNode; } // LR 旋转 先左后右旋转 即先左旋变为LL 再右旋 public Node leftRightRotation(Node node){ // 先左旋转 Node nodeLeft = node.left; Node returnNode = nodeLeft.right; nodeLeft.right = returnNode.left; returnNode.left = nodeLeft; // 右单旋转 node.left = returnNode.right; returnNode.right = node; return returnNode; } // RR 旋转 左单旋转 public Node rightRightRotation(Node node){ Node returnNode = node.right; node.right = returnNode.left; returnNode.left = node; return returnNode; } // RL 旋转 先右后左旋转 即右旋变为RR 再左单旋转 public Node rightLeftRotation(Node node){ Node nodeRight = node.right; Node returnNode = nodeRight.left; nodeRight.left = returnNode.right; returnNode.right = nodeRight; // 左单旋转 node.right = returnNode.left; returnNode.left = node; return returnNode; } public boolean isBalance(Node node){ if(node==null){ return true; } if(!isBalance(node.left)){ return false; } if(!isBalance(node.left)){ return false; } return Math.abs(treeHeight(node.left) - treeHeight(node.right)) < 2; } } class test{ public static void main(String[] args) { int[] arrays = {9,4,1,354,5,4,8,1,3,16}; AVLTree avlTree = new AVLTree(); for(int i:arrays){ avlTree.root = avlTree.insertAvlTree(avlTree.root,i); } avlTree.middleViewStack(avlTree.root); System.out.println("root val " + avlTree.root.val); System.out.println("height " + avlTree.treeHeight(avlTree.root)); System.out.println("is right " + avlTree.isBalance(avlTree.root)); AVLTree avlTreeNoAvl = new AVLTree(); for(int i:arrays){ avlTreeNoAvl.insertTree(avlTreeNoAvl.root,i); } avlTreeNoAvl.middleView(avlTree.root); System.out.println("root val " + avlTreeNoAvl.root.val); System.out.println("height " + avlTreeNoAvl.treeHeight(avlTreeNoAvl.root)); System.out.println("is right " + avlTreeNoAvl.isBalance(avlTreeNoAvl.root)); } }
后面
之后可以做一下简化处理
这篇关于平衡二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南