详解平衡二叉搜索树( AVL树二叉树) 操作（附图解）Java实现

缺乏、安全感 2021-12-24 11:01 278阅读 0赞

二叉树

（个人纯手写，花了几天时间调试，有问题欢迎留言一起讨论  ）

**目录**

1、二叉树的概念：

（1）、简介

（2）、为什么需要二叉树呢？

2、二叉树的插入操作

（1）、静态内部类属性

（2）、插入：

3、遍历查找等简单操作

（1）、遍历

（2）、查找：

（3）、查找父节点：

4、二叉树的删除：

（1）、被删除的节点，是一颗叶子节点

（2）、被删除的节点有一颗右子节点

（3）、要删除的节点有一颗左子节点

（4）、要删除的节点有两个子节点：

5、树的旋转：

（1）、单旋转之左左情况

（2）、单旋转之右右情况

（3）、双旋转 ：

6、Java代码实现：

--------------------

# 1、二叉树的概念： #

## （1）简介 ##

树是一种非线性的数据结构，在现实生活中，我们一般的树长这个样子的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70][]

但是在编程的世界中，我们一般把树倒过来看，这样容易我们分析；二叉树每个结点最多有两个子树的树结构，所以叫二叉树，不是三四五叉树，它是一种单向关系的特殊链表结构；这也是二叉树名字的由来，如下图1.1：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 1][]

## （2）、为什么需要二叉树呢？ ##

假如我有一个插入和查找都比较频繁需求，

你会发现，用有序链表，插入操作成本小，查找成本大O(N)；

用有序数组，查找成本小。但插入操作成本很大O(N)。

二叉树，本质上，是对链表和数组的一个折中。所以，我们折中使用排序二叉树（二叉树仅仅作为排序二叉树的基础），查找、插入操作成本也挺小O(logN)。具体的应用就是由排序二叉树（由于普通排序二叉树可能会有不平衡的情况）引申出来的红黑树（linux中ext3文件系统管理），AVL树“windows对进程地址空间的管理”。

（3）、平衡二叉搜索树（Self-balancing binary search tree）：又被称为AVL树（Adelson-Velskii and Landis发明者命名）（有别于AVL算法），且具有以下性质：它是一棵空树或，它的任意一颗节点的左右两个子树高度差的绝对值<=1，并且左右两个子树都是一棵平衡二叉树；

# 2、二叉树的插入操作 #

## （1）静态内部类属性 ##

先来看一给出的下二叉树中的节点静态内部类属性：

/**
    	 * 内部类Node树对象，存值E value，左子节点，右子节点 Node<E>表示泛型，
         *可以支持对传入类型的排序存储
    	 */
    	private static class Node<E> {
    		E value;
    		Node<E> left;
    		Node<E> right;
    		// 值0表示根节点，值1表示左节点，值2表示右节点
    		// 如图中的节点5、7、10、22、23、24、30都属于左节点类型，
    		// isLeftRight属性值为1;
    		// 如图中的15、17、30、36、38都属于右节点类型,
    		// isLeftRight属性值为2;
    		Integer isLeftRight;
    
    		public Node(E value, Node<E> leftNode, Node<E> rightNode,
                 Integer isLeftRight) {
    			this.value = value;
    			this.left = leftNode;
    			this.right = rightNode;
    			this.isLeftRight = isLeftRight;
    		}
    	}

## （2）插入： ##

先插入第一个节点是根节点，按照递归方式，小的节点插入到根节点到左边，大的节点插入到根节点的右边；

例如第一个插入的节点是20，那么20作为根节点，下面插入10的时候，判断10小于20，把10放到根节点20的左边，30大于20，就把30放到根节点20的右边；

这时候，20叫做10和30的父节点，10是20的左子节点，30是20的右子节点；

依次类推，再插入15节点和7节点，因为15和7都小于根节点20，所以都插入到20的左边；因为是二叉树，20只能有10和30两个子节点；所以再把10作为左边子树的父节点，15大于10，15插入到10的右边，7小于10，7插入到10的左边；同理，10叫做7和15的父节点，7叫做10的左子节点，15叫做10的右子节点；如下图1.2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 2][]

为了方便后续删除等操作，同时在插入节点的时候，我们会为这颗节点标记为左节点（值为1）还是右节点类型（值为2）；

上述代码中静态内部类Node<E>中的字段：Integer isLeftRight 用来存储左右节点类型的字段；

如上图1.2：节点7、10都叫做左子节点类型，isLeftRight = 1；

如上图1.2：节点15、30都叫做右子节点类型，isLeftRight = 2；

特殊情况，根节点20的类型值 isLeftRight = 0 ;（一棵树只有一个根节点）

# 3、遍历查找等简单操作 #

## （1）遍历 ##

我们先把节点都插入，形成一棵树了，开始遍历操作，一共有3种方式：

前序遍历：先访问中间根节点，然后访问左子节点、再访问右子节点

中序遍历：左、中、右；

后续遍历：左、右、中；

都是采用递归的方式遍历，下面的代码中，我只实现了前序遍历方式，其他两种方式类似，写了一种其他两种很好实现；

## （2）查找： ##

查找的节点是否存在这颗树种，递归遍历；

## （3）查找父节点： ##

辅助方法；查找的节点的父节点，为了方便实现删除操作;

# 4、二叉树的删除： #

删除稍微复杂一些，删除共有几种情况：

## （1）、被删除的节点，是一颗叶子节点 ##

被删除的节点，是一颗叶子节点，没有左子树，也没有右子树，这种情况比较简单，如下图2，删除节点6或者22；这里需要做一个判断：

（a）、6是一颗右子节点（在他父节点的右边），找到他的父节点5，将5的right置空，将6的节点置对象Node赋值为null，有助于帮助垃圾回收；

（b）、22是一颗左子节点（在他父节点的左边），找到他的父节点23，将23的left置空，将22的节点置对象Node赋值为null，有助于帮助垃圾回收；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 3][]

## （2）、被删除的节点有一颗右子节点 ##

要删除的节点有一颗右子节点，例如需要删除31，他有一颗右子节点32；同样需要判断31节点是一个左子节点，同时找到他的父节点33，将父节点33的左引用left指向到31的右子节点32，同时31的Node节点置空，如图3.1：

（其实这里还有一种情况没有列举，要删除的节点有一颗右子节点，但是他是一颗右子节点，例如删除节点16，操作类似）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 4][]

## （3）、要删除的节点有一颗左子节点 ##

被删除的节点有一颗左子节点，例如需要删除23，他有一颗左子节点22；同样需要判断23节点是一个左子节点，找到他的父节点24，将父节点24的左引用left指向到23的左子节点22，同时原来的23Node节点置空，如图3.2：

（还有一种情况，要删除的节点有一颗左子节点，但是他是一颗右子节点，例如需要删除节点17，操作类似）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 5][]

## （4）、要删除的节点有两个子节点： ##

（a）、要删除节点30，在30的右子树中找到最左的节点，就是最小的值，即31，用31的值替代30，判断最小左节点31是否还有右节点，如果它有右节点（说明最小节点31肯定是一个左子节点，因为我这里说找到左子树最小的值，左边不可能再有子节点了，所以只需要判断是否有右节点），让他的父节点33的左子节点指向31的右子节点32(Node33.left=Node31.right，同时赋值30节点的值为31:Node30.value= Node31.value;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 6][]

（b）、要删除节点10，在30的右子树中找到最左的节点，最小的值，即16，用16的值替代10，判断最小左节点16是否还有右节点，这里没有右子节点，则需要判断16是左子节点（让父亲节点左指向为空: findParentNode (Node16).left=null）；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 7][]

（c）、这里假如删除的节点是7的时候，7的右树最小节点为8，8是一个右子节点，则让8的父节点7，右指向指向为空，同时赋值7为8节点的值findParentNode (Node8).right=null，Node7.value=Node8.value；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 8][]

# 5、树的旋转： #

在一些极端的情况下，插入的二叉树可能会影响它的效率，使它无法发挥二叉树的特性，这样就使我们创建二叉树失去了他的初衷意义；

例如，有一组依次插入的数据：1，2，3，4，5 ，这颗二叉树的性能，就跟普通的链表一样了，查找性能将会非常慢，如下图5.1:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 9][]

那么我们怎么作才能是一颗二叉树保持平衡呢？那就是对二叉树做旋转操作；

在每插入（删除）一个节点时候，都需要做一次平衡判断，如果不平衡(平衡条件: 它的任意一颗节点的左右子树高度差的绝对值<=1)则需要旋转操作:

## （1）、单旋转之左左情况 ##

单旋转之左左情况，向右旋转：例如有以下两种情况

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 10][]

我们先来看情况一的旋转：

a、当左边最小的子节点为7的时候，左边插入了一个节点5，作为20节点来说，5的高度值比30多了2，所以插入5，导致了二叉树不平衡；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 11][]

那么把20作为当前节点，进行旋转操作，共分为以下a~f六个步骤：

（a）、创建一个新的节点，值等于当前节点的值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 12][]

（b）、把新节点的右子树设置为当前节点的右子树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 13][]

（c）、把新节点左子树设置为当前节点的左子树的右子树（假如当前节点的左子树的右子树不为空，此处为11）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 14][]

（d）、当前节点的值变成它的左子树的值（Node20.value=Node10.value）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 15][]

（e）、当前的左子节点的左子节点变为当前节点的左子节点（Node20.left = Node20.left.left，7和5都向上升一级）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 16][]

（f）、当前节点的右节点指向新节点（Node20.right = newNode）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 17][]

旋转完成以后，与旋转前对比如下，这样就没有高度值差大于1的情况了：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 18][]

b、情况二的旋转，就简单多了，依然可以使用上述通用流程

## （2）、单旋转之右右情况 ##

单旋转之右右情况，把上述（1）的描述的左变右，右变左，即左旋转：

（a）、创建一个新的节点，值等于当前节点的值

（b）、把新节点的左子树设置为当前节点的左子树

（c）、把新节点右子树设置为当前节点的右子树的左子树

（d）、当前节点的值变成它的右子树的值

（e）、当前的右子节点的右子节点变为当前节点的右子节点

（f）、当前节点的左节点指向新节点

右右情况左旋转完成后，与旋转前对比图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 19][]

## （3）双旋转 ： ##

a、在上述步骤（1）的情况一当中，如果不是往节点7的左边插入节点5，而是往节点11的左边插入15，节点15和30对于20来说导致不平衡，假如直接进行左左情况右旋转操作以后：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 20][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 21][]

还是造成了节点7和15的高度不一样，右旋转以后不平衡，那怎么解决呢？

b、在进行右旋转的时候，如果该节点左边的子树的左高度比右高度小（例如10作为根节点的左子树中，节点7就比15的高度小），那么需要先把该节点左边的子树进行一次左旋转，然后对该节点再进行右旋转如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 22][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 23][]

需要旋转的节点20，那么他的左子树11的左高度比右高度高了，此时再按照讲述过的步骤（1）进行左左情况的右旋转，就可以解决平衡问题了；

# 6、Java代码实现： #

二叉平衡树，上述整体逻辑描述完了，完整代码如下：

/**
     * @author Ethan
     * 
     *         20190625
     * 
     *         创建一颗平衡二叉树，支持泛型对象E，支持E排序
     * 
     *         支持增、删、查、旋转等操作
     */
    public class AVLTree<E extends Comparable<E>> {
    
    	/**
    	 * 单独指定根节点
    	 */
    	public Node<E> root;
    
    	/**
    	 * 构造方法，初始化根节点为null
    	 */
    	public AVLTree() {
    		this.root = null;
    	}
    
    	/**
    	 * 内部类Node树对象，存值E value，左子节点，
    	 * 右子节点 Node<E>表示泛型，可以支持对传入类型的排序存储
    	 */
    	private static class Node<E> {
    		E value;
    		Node<E> left;
    		Node<E> right;
    		// 值0表示根节点，值1表示左节点，值2表示右节点
    		// 如图中的节点5、7、10、22、23、24、30都属于左节点类型，
    		// isLeftRight属性值为1;
    		// 如图中的15、17、30、36、38都属于右节点类型,
    		// isLeftRight属性值为2;
    		Integer isLeftRight;
    
    		public Node(E value, Node<E> leftNode,
    			Node<E> rightNode, Integer isLeftRight) {
    			this.value = value;
    			this.left = leftNode;
    			this.right = rightNode;
    			this.isLeftRight = isLeftRight;
    		}
    	}
    
    	/**
    	 * 1.1、为树添加节点，提供对外的方法
    	 * 
    	 * @param node
    	 */
    	public Node<E> addNode(E e) {
    		return insert(e, root);
    	}
    
    	/**
    	 * 1.2、为树添加节点，内部实现
    	 */
    	private Node<E> insert(E e, Node<E> node) {
    
    		// 添加的第一个元素为根节点
    		if (null == root) {
    			root = new Node<E>(e, null, null, 0);
    			System.out.println("root:" + root.value);
    			return root;
    		}
    		// 比较插入的元素，与节点的大小，如果大于，则往节点右边插入
    		// 如果小于该节点，反之左边（第一次与root节点比较）
    		int compareInt = e.compareTo(node.value);
    
    		if (compareInt > 0) {
    			if (node.right != null) {
    				// 右边有子节点，继续递归调用
    				insert(e, node.right);
    			} else {
    				Node<E> rightNode = new Node<E>(e, null,
    				null, 2);
    			// 创建单向的父子节点关系，父节点right指向子节点;
    				node.right = rightNode;
    
    			System.out.println("父节点为" + node.value
    			+ "===作为右子节点:" + rightNode.value);
    
    				return rightNode;
    			}
    		} else {
    			if (node.left != null) {
    				// 左边有子节点，继续递归调用
    				insert(e, node.left);
    			} else {
    				Node<E> leftNode = new Node<E>(e, null,
    				null, 1);
    			// 创建单向的父子节点关系，父节点left指向子节点;
    				node.left = leftNode;
    
    				// 插入一次节点，做一次平衡操作
    
    			System.out.println("父节点为" + node.value
    			+ "===作为左子节点:" + leftNode.value);
    
    				return leftNode;
    			}
    		}
    		return node;
    	}
    
    	/**
    	 * 2.1、外部方法，查找节点
    	 * 
    	 * @param node
    	 */
    	public Node<E> findNode(E e) {
    		if (root == null) {
    			return null;
    		}
    
    		if (e.compareTo(root.value) == 0) {
    			return root;
    		}
    		return findNode(e, root);
    	}
    
    	/**
    	 * 2.2、内部方法，查找节点
    	 */
    	public Node<E> findNode(E e, Node<E> node) {
    
    		if (e.compareTo(node.value) == 0) {
    			return node;
    		}
    		// 大于从右边继续找
    		if (e.compareTo(node.value) > 0) {
    
    			if (node.right != null) {
    				return findNode(e, node.right);
    			} else
    				return null;
    		}
    		// 小于从左边继续找
    		else if (e.compareTo(node.value) < 0) {
    
    			if (node.left != null) {
    				return findNode(e, node.left);
    			} else
    				return null;
    		} else
    			return null;
    	}
    
    	/**
    	 * 3.1、对外遍历节点方法
    	 * 
    	 * 前序遍历：先遍中节点，然后左子节点、右子节点
    	 * 
    	 * 中序遍历：左、中、右
    	 * 
    	 * 后续遍历：左、右、中
    	 * 
    	 * @param node
    	 */
    	public void getAllNode() {
    		if (root == null) {
    			return;
    		}
    		getAllNode(root);
    	}
    
    	/**
    	 * 3.2、内部方法，前序遍历节点
    	 */
    	private void getAllNode(Node<E> e) {
    		if (e.left != null) {
    		System.out.println("父节点：" + e.value);
    		System.out.println("左子节点：" + e.left.value);
    		getAllNode(e.left);
    		}
    		if (e.right != null) {
    		System.out.println("父节点：" + e.value);
    		System.out.println("右子节点：" + e.right.value);
    		getAllNode(e.right);
    		}
    	}
    
    	/**
    	 * 3.3、对外提供方法，遍历节点，顺便打印出结构
    	 */
    	public void getAllNodeWithParent() {
    		System.out.println("根节点" + root.value);
    		getAllNodeWithParent(root);
    	}
    
    	/**
    	 * 3.4、内部方法，遍历节点，顺便打印出结构
    	 */
    	private void getAllNodeWithParent(Node<E> node) {
    
    		if (node.left == null && node.right == null) {
    		System.out.println("叶子节点值:" + node.value);
    		} else {
    		System.out.println("父节点值:" + node.value);
    		}
    
    		if (node.left != null) {
    		System.out.println(node.value + "的左子节点值:"
    		+ node.left.value);
    		getAllNodeWithParent(node.left);
    		}
    		if (node.right != null) {
    		System.out.println(node.value + "的右子节点值:"
    		+ node.right.value);
    		getAllNodeWithParent(node.right);
    		}
    	}
    
    	/**
    	 * 4.1、找到父节点
    	 */
    	public Node<E> findParentNode(E e) {
    		return findParentNode(root, e);
    	}
    
    	/**
    	 * 4.2、内部方法，找到父节点
    	 */
    	private Node<E> findParentNode(Node<E> node, E e) {
    
    	// 父节点为空，或者该节点为root节点，那么root的父节点就不存在了
    	if (root == null || root.value.compareTo(e) == 0) {
    		return null;
    	} else {// 当前节点的左子节点或右子节点值等于e，返回当前节点
    		if (node.left != null
    			&& node.left.value.compareTo(e) == 0
    			|| node.right != null
    			&& node.right.value.compareTo(e) == 0) {
    			return node;
    		}
    		// 递归继续从左边查找
    		else if (node != null
    			&& node.value.compareTo(e) > 0) {
    			return findParentNode(node.left, e);
    		} // 递归继续从右边查找
    		else if (node != null
    			&& node.value.compareTo(e) < 0) {
    			return findParentNode(node.right, e);
    		} else
    			return null;
    		}
    
    	}
    
    	/**
    	 * 5.1、删除节点
    	 * 
    	 * @return
    	 */
    
    	public boolean deleteNode(E e) {
    		if (root == null) {
    			return false;
    		}
    		Node<E> node = findNode(e);
    		// a、先查找此节点是否存在
    		if (node == null) {
    			return false;
    		}
    	// b、节点存在，则需要找到它的父节点
    		else {
    	Node<E> parentNode = findParentNode(root, e);
    	System.out.println(e + "的父亲节点是:"
    	+ parentNode.value + "(在删除方法中)");
    	if (parentNode != null) {
    	// c、如果需要删除的节点恰好是叶子节点（没有左右子节点了）
    		if (node.left == null
    		&& node.right == null) {
    	// d、如果要删除的节点是他父亲节点的左边子节点
    			if (parentNode.left != null
    			&& parentNode.left.value.
    			compareTo(node.value) == 0) {
    				parentNode.left = null;
    
    			return true;
    			}
    		// e、如果要删除的节点是他父亲节点的右边子节点
    		else
    			parentNode.right = null;
    
    			// 删除一次节点，做一次平衡操作
    
    			return true;
    		}
    
    		// f、如果需要删除的节点有一个左子节点
    		if (node.left != null
    				&& node.right == null) {
    			// 如果需要删除的节点是一个左节点
    			// 则让父亲节点左边指向他的左子节点
    			if (parentNode.isLeftRight == 1) {
    				parentNode.left = node.left;
    				// 删除一次节点，做一次平衡操作
    
    				return true;
    			}
    			// 如果需要删除的节点是一个右节点
    			// 则让父亲节点右边指向他的左子节点
    			else if (parentNode.isLeftRight == 2) {
    				parentNode.right = node.left;
    
    				// 删除一次节点，做一次平衡操作
    
    				return true;
    			}
    		}
    
    		// g、如果需要删除的节点有一个右子节点
    		if (node.right != null
    				&& node.left == null) {
    			// 如果需要删除的节点是一个左节点
    			// 则让父亲节点左边指向他的右子节点
    			if (parentNode.isLeftRight == 1) {
    				parentNode.left = node.right;
    				// 删除一次节点，做一次平衡操作
    				return true;
    			}
    			// 如果需要删除的节点是一个右节点
    			// 则让父亲节点右边指向他的右子节点
    			else if (parentNode.isLeftRight == 2) {
    				parentNode.right = node.right;
    
    				// 删除一次节点，做一次平衡操作
    
    				return true;
    			}
    		}
    
    		// h、如果需要删除的节点有两个子节点
    		// （删除根节点时也适用）
    		if (node.left != null
    				&& node.right != null) {
    			// 删除右子树中最小节点，获取到最小节点的值;
    			// 把最小节点的值，赋值给要删除节点的值;
    			// （实际上并不是删除该节点，只是改变赋值）;
    			// 一般右边最小节点值，位于右子节点
    			// 下面的最左的子节点;
    
    			Node<E> minNode = deleteGetMin(
    					node.right);
    			// 找到该最小节点的父节点
    			Node<E> minNodeParent = 
    			findParentNode(minNode.value);
    			// 找到了最小的左节点，不可能再有左子节点
    			if (minNode.right != null) {
    				// 然后把找到的最小值minNode.value
    				// 赋值给要删除的节点
    				// 最小节点肯定是左子节点
    				node.value = minNode.value;
    				// 如果左最小节点minNode是一个右节点
    				// （右边全是右节点）
    				if (minNode.isLeftRight == 2) {
    					minNodeParent.right = 
    					minNode.right;
    				// 删除一次节点，做一次平衡操作
    						return true;
    				}
    				// 如果左最小节点minNode是一个左节点
    				else {
    				// 最小节点的父节点,的左子节点
    				//则指向最小节点的右子节点
    				minNodeParent.left = 
    					minNode.right;
    				// 删除一次节点，做一次平衡操作
    				return true;
    			    }
    			}
    			// 得到的右子树最小节点，已经是一个叶子
    			// 节点了，直接赋值
    			else {
    				// 如果左最小节点minNode是一个右节点
    				// （右边全是右节点）
    				if (minNode.isLeftRight == 2) {
    				node.value = minNode.value;
    				// 最小节点的父节点,的右子节点
    				// 则指向空
    				minNodeParent.right = null;
    				// 删除一次节点，做一次平衡操作
    				return true;
    				} else {
    				// 然后把找到的最小值minNode.value
    				//赋值给要删除的节点
    				// 最小节点肯定是左子节点
    				node.value = minNode.value;
    				// 最小节点的父节点,的左子节点则指向空
    				minNodeParent.left = null;
    				// 删除一次节点，做一次平衡操作
    				return true;
    					}
    				}
    			}
    		}
    	}
    		return false;
    }
    
    	/**
    	 * 5.2、获取右边最小节点值，位于右子节点下面的最左的子节点;
    	 * 
    	 * @param right
    	 * @return
    	 */
    	private Node<E> deleteGetMin(Node<E> node) {
    
    		// 如果左边一直有节点，那么一直找到最小的
    		// 非递归写法
    		while (node.left != null) {
    			node = node.left;
    		}
    		return node;
    		//
    		// //递归写法
    		// if (node.left != null) {
    		// return deleteGetMin(node.left);
    		// }
    		// return node;
    
    	}
    
    	/**
    	 * 6.1、判断该节点是属于左节点(返回1)还是右节点(返回2)
    	 * 
    	 * 也可用Node内部类isLeftRight判断
    	 */
    
    	public int isLeftRight(E e) {
    		// 根节点返回0
    		if (root.value.compareTo(e) == 0) {
    			return 0;
    		}
    		return isLeftRight(root, e);
    	}
    
    	/**
    	 * 6.2、判断该节点是属于左节点(返回1)还是右节点(返回2)
    	 * 
    	 * 也可用Node内部类isLeftRight判断
    	 */
    
    	private int isLeftRight(Node<E> node, E e) {
    
    		// 是node的左子节点
    		if (node.left != null
    		&& node.left.value.compareTo(e) == 0) {
    		return 1;
    		} // 是node的右子节点
    		if (node.right != null
    		&& node.right.value.compareTo(e) == 0) {
    		return 2;
    		}
    		// 子节点nodeSon比node节点小，往左边递归
    		if (node.left != null
    		&& e.compareTo(node.value) < 0) {
    		return isLeftRight(node.left, e);
    		}
    		// 子节点nodeSon比node节点大，往右边递归
    		if (node.right != null
    		&& e.compareTo(node.value) > 0) {
    		return isLeftRight(node.right, e);
    		}
    		return -1;
    
    	}
    
    	/**
    	 * 7.1求树子节点的高度
    	 * 
    	 * 在Node内部类里面有height方法可用，求高度
    	 */
    
    	public int heigth(E e) {
    		if (e == null) {
    			return 0;
    		}
    		// 先找到节点
    		Node<E> node = findNode(e);
    		// 递归它的子树的高度，加上自己的高度
    		return heigth(node) + 1;
    
    	}
    
    	/**
    	 * 7.2求树子节点的高度
    	 * 
    	 * 在Node内部类里面有height方法可用，求高度
    	 */
    
    	private int heigth(Node<E> node) {
    		if (node == null) {
    			return -1;
    		}
    		return Math.max(
    			node.left == null ? 0
    			: heigth(node.left) + 1,
    			node.right == null ? 0
    			: heigth(node.right) + 1);
    	}
    
    	/**
    	 * 左左情况一之向右旋转
    	 * 
    	 * 8.1树右旋转
    	 */
    
    	private void rightRotate(Node<E> node) {
    
    		// （a）、创建一个新的节点，值等于当前节点的值
    		Node<E> newNode = new Node<E>(node.value, null,
    				null, 0);
    		// （b）、把新节点的右子树设置为当前节点的右子树
    		if (node.right != null) {
    			newNode.right = node.right;
    		}
    		// （c）、把新节点左子树设置为当前节点的左子树的右子树
    		if (node.left.right != null) {
    			newNode.left = node.left.right;
    		}
    		// （d）、当前节点的值变成它的左子树的值
    		node.value = node.left.value;
    		// （e）、当前的左子节点变为当前节点的左子节点的左子节点
    		node.left = node.left.left;
    		// （f）、当前节点的右节点指向新节点
    		node.right = newNode;
    	}
    
    	/**
    	 * 8.2树左旋转
    	 */
    
    	private void leftRotate(Node<E> node) {
    	// （a）、创建一个新的节点，值等于当前节点的值
    	Node<E> newNode = new Node<E>(node.value, null,
    	null, 0);
    	// （b）、把新节点的左子树设置为当前节点的左子树
    	if (node.left != null) {
    	newNode.left = node.left;
    	}
    	// （c）、把新节点右子树设置为当前节点的右子树的左子树
    	if (node.right.left != null) {
    		newNode.right = node.right.left;
    	}
    	// （d）、当前节点的值变成它的右子树的值
    	node.value = node.right.value;
    	// （e）、当前的右子节点变为当前节点的右子节点的右子节点
    	node.right = node.right.right;
    	// （f）、当前节点的左节点指向新节点
    	node.left = newNode;
    	}
    
    	/**
    	 * 9.1求节点的高度
    	 * 
    	 * @param left
    	 * @return
    	 */
    	public int height(Node<E> left) {
    		if (left == null) {
    			return 0;
    		}
    		return Math.max(
    		left.left == null ? 0 : height(left.left),
    		left.right == null ? 0 : height(left.right))
    		+ 1;
    	}
    
    	/**
    	 * 9.2求左子树的高度
    	 * 
    	 * @主要用于求与右树差值，做树的旋转操作
    	 * @param node
    	 * @return
    	 */
    	public int leftHeight(Node<E> node) {
    
    		if (node == null) {
    			return 0;
    		}
    		return height(node.left);
    	}
    
    	/**
    	 * 9.3求右子树的高度
    	 * 
    	 * @主要用于求与左树差值，做树的旋转操作
    	 * @param node
    	 * @return
    	 */
    	public int rightHeight(Node<E> node) {
    		if (node == null) {
    			return 0;
    		}
    		return height(node.right);
    	}
    
    	/**
    	 * 10.1平衡操作，旋转
    	 *
    	 * 左左向右单旋转
    	 *
    	 * 左左向左先旋转，再向右的双旋转
    	 *
    	 * 右右向左单旋转
    	 *
    	 * 右右向右先旋转，再向左的双旋转
    	 *
    	 * @param node
    	 */
    	public void reBalance(Node<E> node) {
    
    		System.out.println("旋转值节点：" + node.value);
    
    		System.out.println("旋转值节点左高：" + 
    		leftHeight(node));
    
    		System.out.println("旋转值节点右高：" + 
    		rightHeight(node));
    
    		// 左左情况，该进行右旋转
    		if (leftHeight(node) - rightHeight(node) > 1) {
    		// 在进行右旋转的时候，如果该节点左边的子树
    		// 的左高度比右高度小，那么需要先把该节点左边
    		// 的子树进行一次左旋转，然后对该节点再进行右旋转
    		// 这里就是双旋转了，先左旋转，再右旋转；
    		if (node.left != null && leftHeight(
    			node.left) < rightHeight(node.left)) {
    
    		System.out.println(
    		"双旋转开始，左旋:" + node.left.value);
    		System.out.println("双旋转开始，右旋:"
    		+ node.value);
    
    		leftRotate(node.left);
    		rightRotate(node);
    		} else {
    		// 如果只执行这一步操作，就是单旋转，右旋转
    
    		System.out.println("单旋转开始，右旋:"
    		+ node.value);
    
    		rightRotate(node);
    	     }
    
    		}
    
    		// 同样，相反方向的右右情况，该进行左旋转
    
    		// 右右情况，该进行左旋转
    		if (rightHeight(node) - leftHeight(node) > 1) {
    		// 在进行左旋转的时候，如果该节点右边的子树
    		// 的右高度比左高度小，那么需要先把该节点右边
    		// 的子树进行一次右旋转，然后对该节点再进行左旋转
    		// 这里就是双旋转了，先右旋转，再左旋转；
    		if (node.right != null && rightHeight(
    		node.right) < leftHeight(node.right)) {
    		rightRotate(node.right);
    		leftRotate(node);
    		} else {
    		// 如果只执行这一步操作，就是单旋转，左旋转
    			leftRotate(node);
    		}
    
    		}
    	}
    
    	public static void main(String[] args) {
    
    		// 这组元素用来新增、删除、查询测试用
    		// Integer integerArray[] = { 20, 10, 30, 7, 
    		// 5, 8, 6, 15, 17, 16, 24, 25, 36,
    		// 23, 22, 33, 38, 31, 32, 37 };
    
    		// 这组不平衡树，用来做旋转测试用
    		Integer integerArray[] = { 20, 10, 30, 7, 5, 11 };
    
    		// Integer integerArray[] = { 5, 4, 3, 1 };
    
    		AVLTree<Integer> tree = new AVLTree<Integer>();
    
    		// 1、插入节点
    		for (int i = 0; i < integerArray.length; i++) {
    			tree.addNode(integerArray[i]);
    		}
    
    		// 旋转根节点（疑问，到底在哪个时候旋转比较好）
    		tree.reBalance(tree.root);
    		// 可以递归旋转其他节点
    
    		// 2、查找节点
    		// AVLTree.Node<Integer> node = 
    		// tree.findNode(30);
    		// System.out.println(node.value);
    
    		// 3、遍历节点
    		tree.getAllNodeWithParent();
    
    		 4、查找父节点
    		// int findParentValue = 10;
    		// AVLTree.Node<Integer> parentNode =
    		//  tree.findParentNode(findParentValue);
    		// if (parentNode != null) {
    		// System.out.println(findParentValue + 
    		// " 's parentNode is:" +
    		// parentNode.value);
    		// }
    		// // 5、删除节点
    		// int deleteValue = 36;
    		// boolean isDel=tree.deleteNode(deleteValue);
    		// System.out.println(isDel );
    
    	}
    }

[红黑树详解][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70]: /images/20211224/e6b3281361b94614b630a87e86c9146f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 1]: /images/20211224/536711f996034f90b071b60dd497e6bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 2]: /images/20211224/c9fd281997fb4e8db6eff6ca8b519e6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 3]: /images/20211224/b8498c3617004cbf996f647efe531119.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 4]: /images/20211224/a7f9ec2fa36844438075deafb24e8253.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 5]: /images/20211224/a6efe6a0c3e94d28bd412ab68f3dab23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 6]: /images/20211224/94d7926a6aaf4dff91bb0b4b0673065b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 7]: /images/20211224/809b4990fc0d4ad888dc3e52ba817023.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 8]: /images/20211224/b1cd8de130c24768b80f7fc5f49cad34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 9]: /images/20211224/f1dfcb08887849bda8582d1a042862c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 10]: /images/20211224/ff01538236794958aeffa010d917e906.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 11]: /images/20211224/599dfd2d1e4e42d0a60e4c148f6abd27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 12]: /images/20211224/cbda43b302e24d0c99c4d2a5f2fbdeb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 13]: /images/20211224/d7273a1416174d8eb9d5e770be95a4f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 14]: /images/20211224/fc264beb13064269b06d9aba0b1e9b15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 15]: /images/20211224/499b336d1cbe48a68755b21d54daea22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 16]: /images/20211224/849eb27521fc440bb72957c0d01a8802.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 17]: /images/20211224/060d7903052442398e9ae95f5d054112.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 18]: /images/20211224/2079321686e14b07953741400c93a36b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 19]: /images/20211224/0ad479d45691412a982073a14e76c970.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 20]: /images/20211224/e895916840f148238eae42feca51ec69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 21]: /images/20211224/6f87257979c04edd8786923c4607c943.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 22]: /images/20211224/693b9f93a3884ad7a2bc4dcbb09aa158.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 23]: /images/20211224/843f09bcef9441beb547f7812c42eed1.png
[Link 1]: https://blog.csdn.net/lejustdoit/article/details/95588894