赞
踩
目录
平衡二叉树的本质其实也是二叉排序树,具体可参考:
平衡二叉树的特点是任意节点的子树的高度差都小于等于1。
平衡二叉树的构建基本分为三种情况,左旋转、右旋转、双旋转
1、当根节点的右子树的高度比左子树高度大于1时,即高度相差2以上,则进行左旋转,思路如下图:
2、当根节点的左子树的高度比右子树高度大于1时,则进行右旋转:
3、如下图,复合右旋转条件,但是右旋转后还不是平衡二叉树,则分以下两种情况
3.1 当符合右旋条件,并且根节点的左子节点的右子树高度大于左子树的时候,先进行一次左旋转
3.2 当符合左旋转条件,并且根节点的右子树的左子树节点大于右子树节点的时候,先进行一次右旋转
- /**
- * @author 浪子傑
- * @version 1.0
- * @date 2020/6/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};
- int[] arr = {10, 11, 7, 6, 8, 9};
- AVLTree avlTree = new AVLTree();
- for (int i : arr) {
- avlTree.add(new Node(i));
- }
-
- System.out.println(avlTree.root.height());
- System.out.println(avlTree.root.leftHeight());
- System.out.println(avlTree.root.rightHeight());
- }
- }
-
- class Node {
-
- int value;
- Node left;
- Node right;
-
- public Node(int value) {
- this.value = value;
- }
-
- /**
- * 左旋转
- */
- public void leftRotate() {
- // 创建一个新的节点,值为当前节点的值
- Node newNode = new Node(value);
- // 把新节点的左子树设为当前节点的左子树
- newNode.left = left;
- // 把新节点的右子树设为当前右子节点的左子树
- newNode.right = right.left;
- // 把当前节点的值换位右子节点的值
- this.value = right.value;
- // 把当前节点的右子树设为右子节点的右子树
- right = right.right;
- // 把当前节点的左子树设为新节点
- left = newNode;
- }
-
- /**
- * 右旋转
- */
- public void rightRotate() {
- // 创建一个新的节点并将当前值赋给新节点
- Node newNode = new Node(value);
- // 把新节点的右子树设为当前节点的右子树
- newNode.right = right;
- // 把新节点的左子树设为当前节点左子节点的右子树
- newNode.left = left.right;
- // 把当前值设为左子树节点的值
- this.value = left.value;
- // 把当前节点的左子树设为左子节点的左子树
- this.left = left.left;
- // 把当前节点的右子树设为新节点
- this.right = newNode;
-
-
- }
-
- /**
- * 返回右子树的高度
- *
- * @return
- */
- public int rightHeight() {
- if (right == null) {
- return 0;
- } else {
- return right.height();
- }
- }
-
- /**
- * 返回左子树的高度
- *
- * @return
- */
- public int leftHeight() {
- if (left == null) {
- return 0;
- } else {
- return left.height();
- }
- }
-
- /**
- * 获取以当前节点为根节点的树的高度
- *
- * @return
- */
- public int height() {
- return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
- }
-
- /**
- * 查询要删除的节点
- *
- * @param value
- * @return
- */
- public Node search(int value) {
- // 如果要查找的值==当前节点的值,返回当前节点
- // 如果要查找的值 < 当前节点,则向该节点的左子树查找
- // 否则向该节点的右子树查找
- if (this.value == value) {
- return this;
- } else if (value < this.value) {
- // 如果该节点的左子节点为null,直接返回null
- if (this.left == null) {
- return null;
- }
- return this.left.search(value);
- } else {
- if (this.right == null) {
- return null;
- }
- return this.right.search(value);
- }
- }
-
- /**
- * 查找要删除节点的父节点
- *
- * @param value
- * @return
- */
- public Node searchParent(int value) {
- // 如果当前节点的子节点不为空,并且当前节点子节点的值 == value,则返回当前节点
- // 如果当前节点的左子节点不为null,并且当前节点的值 > value,则向该节点的左子节点遍历
- // 如果当前节点的右子节点不为null,并且当前节点的值不> value,则向该节点的右子节点遍历
- // 否则没有找到,返回null
- if ((this.left != null && this.left.value == value) ||
- (this.right != null && this.right.value == value)) {
- return this;
- } else if (this.left != null && this.value > value) {
- return this.left.searchParent(value);
- } else if (this.right != null && this.value <= value) {
- return this.right.searchParent(value);
- } else {
- return null;
- }
- }
-
- /**
- * 添加节点
- *
- * @param node
- */
- public void add(Node node) {
- // 如果该节点为null,直接返回
- if (node == null) {
- return;
- }
- // add的节点小于当前节点,说明应该在当前节点的左边
- // 否则放在当前节点的右边
- if (node.value < this.value) {
- // 如果当前节点的左边没有子节点,则直接把add节点放在当前节点的左子节点
- // 否则的话,遍历当前左子节点,直到找到合适位置
- if (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,则进行左旋转
- // 如果当前节点的左节点比右节点的高度 > 1,则进行右旋转
- if (rightHeight() - leftHeight() > 1) {
- // 如果当前节点的右子节点的左子树高度大于右子树的高度,则先进行右旋转
- if (right != null && right.leftHeight() > right.rightHeight()) {
- right.leftRotate();
- }
- leftRotate();
- } else if (leftHeight() - rightHeight() > 1) {
- // 如果当前节点的左子节点的右子树高度大于左子树的高度,则先进行左旋转
- if (left != null && left.rightHeight() > left.leftHeight()) {
- left.leftRotate();
- }
- rightRotate();
- }
-
- }
-
- /**
- * 中序遍历
- */
- public void middleOrder() {
- if (this.left != null) {
- this.left.middleOrder();
- }
- System.out.println(this);
- if (this.right != null) {
- this.right.middleOrder();
- }
- }
-
- @Override
- public String toString() {
- return "Node{" +
- "value=" + value +
- '}';
- }
- }
-
- class AVLTree {
-
- Node root;
-
- /**
- * 删除节点
- *
- * @param value
- */
- public void delete(int value) {
- // 如果父节点为null,直接返回
- if (root == null) {
- return;
- } else {
- Node targetNode = search(value);
- // 如果要删除的节点为null,直接返回
- if (targetNode == null) {
- return;
- }
- // 如果父节点的左右节点都为null,说明只有一个节点,直接将root设为null即可
- if (root.left == null && root.right == null) {
- root = null;
- return;
- }
- Node parentNode = searchParent(value);
- // 如果要删除节点的左右节点都为null,说明该要删除的节点为子节点
- if (targetNode.left == null && targetNode.right == null) {
- // 如果父节点的左子节点不为null并且是要删除的节点,则将父节点的左子节点设为null
- // 如果父节点的右子节点不为null并且是要删除的节点,则将父节点的右子节点设为null
- if (parentNode.left != null && parentNode.left.value == value) {
- parentNode.left = null;
- } else if (parentNode.right != null && parentNode.right.value == value) {
- parentNode.right = null;
- }
- } else if (targetNode.left != null && targetNode.right != null) {
- // 如果要删除的左右子节点都不为null,则查找要删除节点右子节点的最小值,删除最小节点并将值赋给要删除节点
- int treeMin = delRightTreeMin(targetNode.right);
- System.out.println("最小的为---" + treeMin);
- targetNode.value = treeMin;
- } else {
- // 如果要删除的节点左右子节点有一个为null
- // 如果要删除的子节点为root节点
- if (parentNode == null) {
- // 如果左子节点不为null,则将左子节点赋给root
- // 否则将右子节点赋给root
- if (targetNode.left != null) {
- root = targetNode.left;
- } else {
- root = targetNode.right;
- }
- } else if (parentNode.left.value == value) {
- // 如果要删除的节点为parentNode的左子节点
- // 如果要删除的节点的左子节点不为null,则将parentNode的左子节点指向要删除节点的左子节点
- // 否则则指向要删除节点的右子节点
- if (targetNode.left != null) {
- parentNode.left = targetNode.left;
- } else {
- parentNode.left = targetNode.right;
- }
- } else {
- if (targetNode.right != null) {
- parentNode.right = targetNode.right;
- } else {
- parentNode.right = targetNode.left;
- }
- }
-
- }
- }
- }
-
- /**
- * 返回以node节点为根节点的二叉排序树的最小值
- *
- * @param node
- * @return
- */
- public int delRightTreeMin(Node node) {
- Node target = node;
- while (target.left != null) {
- target = target.left;
- }
- delete(target.value);
- return target.value;
- }
-
- /**
- * 查找要删除的节点
- *
- * @param value
- * @return
- */
- public Node search(int value) {
- if (root == null) {
- return null;
- } else {
- return root.search(value);
- }
- }
-
- /**
- * 查询要删除的父节点
- *
- * @param value
- * @return
- */
- public Node searchParent(int value) {
- if (root == null) {
- return null;
- } else {
- return root.searchParent(value);
- }
- }
-
- /**
- * 添加子节点
- *
- * @param node
- */
- public void add(Node node) {
- if (root == null) {
- root = node;
- } else {
- root.add(node);
- }
- }
-
- /**
- * 中序遍历
- */
- public void infixOrder() {
- if (root != null) {
- root.middleOrder();
- } else {
- System.out.println("当前root为空");
- }
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。