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

二叉树

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

目录

1、二叉树的概念：

（1）、简介

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

2、二叉树的插入操作

（1）、静态内部类属性

（2）、插入：

3、遍历查找等简单操作

（1）、遍历

（2）、查找：

（3）、查找父节点：

4、二叉树的删除：

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

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

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

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

5、树的旋转：

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

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

（3）、双旋转 ：

6、Java代码实现：

---

 

 

1、二叉树的概念：

（1）简介

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

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

为了方便后续删除等操作，同时在插入节点的时候，我们会为这颗节点标记为左节点（值为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，有助于帮助垃圾回收；

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

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

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

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

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

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

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

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

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

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

5、树的旋转：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

（3）双旋转 ：

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

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

 

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

需要旋转的节点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 );
 
	}
}

 

下一篇：

红黑树详解