当前位置：首页 > news >正文

数据结构与算法——平衡二叉树

news 来源：原创 2024/9/20 17:45:59

1、基本介绍

1）平衡二叉树又叫平衡二叉搜索树(Self-balanceing binary search tree)，又被称为AVL树，可以保证查询效率较高。
2）具有以下特点：它是一颗空树或它的左右两颗子树的高度差绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用的实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等

二叉排序树可能存在的问题：
在这里插入图片描述

左子树全部为空，从形式上看，更像一个单链表
插入速度没有影响
查询速度明显降低（因为需要依次比较），不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
解决方案——平衡二叉树

2、应用案例—— 单旋转（左旋转、右旋转）、双旋转

全部代码实现

public class AVLTreeDemo {public static void main(String[] args) {
//        int[] arr = {4, 3, 6, 5, 7, 8};int[] arr = {10,12,8,9,7,6};// 创建一个AVLTree对象AVLTree avlTree = new AVLTree();// 添加节点for (int i = 0; i < arr.length; i++) {avlTree.add(new Node(arr[i]));}// 遍历System.out.println("中序遍历");avlTree.infixOrder();System.out.println("在没有平衡处理前");System.out.println(avlTree.getRoot().height());System.out.println("树的左子树的高度=" + avlTree.getRoot().leftHeight());System.out.println("树的右子树的高度=" + avlTree.getRoot().rightHeight());System.out.println("当前的根节点=" + avlTree.getRoot());}
}class AVLTree {private Node root;public Node getRoot() {return root;}// 查找要删除的节点public Node search(int value) {if (root == null) {return null;}return root.search(value);}// 查找父节点public Node searchParent(int value) {if (root == null) {return null;}return root.searchParent(value);}//1、 返回的以 node 为根结点的二叉排序树的最小节点的值//2、 删除 node 为根结点的二叉排序树的最小节点/*** @param node 传入的节点（当做二叉排序树的根结点）* @return 返回的以 node 为根结点的二叉排序树的最小节点的值*/public int delRightTreeMin(Node node) {Node target = node;//循环地查找左子节点，就会找到最小值while (target.left != null) {target = target.left;}// 这时target就指向了最小节点，删除最小节点delNode(target.value);return target.value;}// 删除节点public void delNode(int value) {if (root == null) {return;} else {// 1、需求先去找到要删除的节点 targetNodeNode targetNode = search(value);// 如果没有找到要删除的节点if (targetNode == null) {return;}// 如果我们发现当前这颗二叉树只有一个节点if (root.left == null && root.right == null) {root = null;return;}// 去找到targetNode的父节点Node parent = searchParent(value);// 如果要删除的是叶子节点if (targetNode.left != null && targetNode.right == null) {// 判断targetNode是父节点的左子节点还是右子节点if (parent.left != null && parent.left.value == value) {// 是左节点parent.left = null;} else if (parent.right != null && parent.right.value == value) {// 是右节点parent.right = null;}} else if (targetNode.left != null && targetNode.right != null) {// 删除有两颗子树的节点int minValue = delRightTreeMin(targetNode.right);targetNode.value = minValue;} else {// 删除只有一颗子树的节点// 如果要删除的节点有左子节点if (targetNode.left != null) {if (parent != null) {// 如果 targetNode 是parent 的左子节点if (parent.left.value == value) {parent.left = targetNode.left;} else { // targetNode 是 parent 的右子节点parent.right = targetNode.left;}} else {root = targetNode.left;}} else {// 如果要删除的节点有右子节点if (parent != null) {// 如果 targetNode 是 parent 的左子节点if (parent.left.value == value) {parent.left = targetNode.right;} else {// 如果 targetNode 是 parent 的右子节点parent.right = targetNode.right;}} else {root = targetNode.right;}}}}}// 添加节点的方法public void add(Node node) {if (root == null) {root = node;// 如果root是空值 直接让root指向node} else {root.add(node);}}//中序遍历public void infixOrder() {if (root != null) {root.infixOrder();} else {System.out.println("二叉排序树为空，不能遍历！");}}
}// 创建Node节点
class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}// 返回左子树的高度public int leftHeight() {if (left == null) {return 0;}return left.height();}//返回右子树的高度public int rightHeight() {if (right == null) {return 0;}return right.height();}// 返回以当前节点为根结点的树的高度public int height() {return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;}// 左旋转方法private void leftRotate() {// 创建新的节点 以当前根节点的值Node newNode = new Node(value);// 把新的节点的左子树设置成当前节点的左子树newNode.left = left;// 把新的节点的右子树设置成当前节点的右子树的左子树newNode.right = right.left;// 把当前节点的值替换成右子节点的值value = right.value;// 把当前节点的右子树设置成当前节点右子树的右子树right = right.right;// 把当前节点的左子树（左子节点）设置成新的节点left = newNode;}// 右旋转private void rightRotate() {Node newNode = new Node(value);newNode.right = right;newNode.left = left.right;value = left.value;left = left.left;right = newNode;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}/*** 查找要删除的节点** @param value 希望删除的节点的值* @return 如果找到返回该节点，否则返回null*/public Node search(int value) {if (value == this.value) {return this;} else if (value < this.value) {// 如果查找的值小于当前节点，向左子树递归查找if (this.left == null) {return null;}this.left.search(value);} else {// 如果查找的值大于当前节点，向右子树递归查找if (this.right == null) {return null;}return this.right.search(value);}return null;}/*** 查找要删除节点的父节点** @param value 要找的节点的值* @return 返回的是要删除的节点的父节点，如果没有就返回null*/public Node searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {// 如果查找到值小于当前节点的值，并且当前节点的左子节点不为空if (value < this.value && this.left != null) {return this.left.searchParent(value);// 向左子树递归查找} else if (value > this.value && this.right != null) {return this.right.searchParent(value);// 向右子树递归查找} else {return null;// 没有找到父节点}}}// 添加节点的方法// 递归的形式添加节点，注意需要满足二叉排序树的要求public void add(Node node) {if (node == null) {return;}// 判断传入的节点的值，和当前子节点值大小if (node.value < this.value) {// 如果当前节点左子节点为nullif (this.left == null) {this.left = node;} else {// 递归地像左子树添加this.left.add(node);}} else {// 添加的节点的值大于当前节点的值if (this.right == null) {this.right = node;} else {// 递归地像右子树添加this.right.add(node);}}// 当添加完一个节点后，如果：（右子树的高度 - 左子树的高度） > 1， 左旋转if(rightHeight() - leftHeight() > 1) {// 如果它的右子树的左子树的高度大于它的右子树的右子树的高度if(right != null && right.leftHeight() > right.rightHeight()) {// 先对右子节点进行右旋转right.rightRotate();// 再对当前节点进行左旋转leftRotate();// 左旋转。。。} else {// 直接左旋转即可leftRotate();}return; // 必须要！！！}// 当添加完一个节点后， 如果(左子树的高度 - 右子树的高度) > 1， 右旋转if(leftHeight() - rightHeight() > 1) {// 如果它的左子树的右子树的高度大于它的左子树的高度if(left != null && left.rightHeight() > left.leftHeight()) {// 先对当前节点的左节点（左子树） -》 左旋转left.leftRotate();// 再对当前节点进行右旋转rightRotate();} else {// 直接进行右旋转rightRotate();}}}// 中序遍历public void infixOrder() {if (this.left != null) {this.left.infixOrder();}System.out.println(this.toString());if (this.right != null) {this.right.infixOrder();}}
}