平衡二叉树的原理及java代码实现

好容易等到一个周末，本来想补上平衡二茶树的知识，但这两天一天睡觉，一天玩游戏，一转眼就到了周日夜里，想着这周不能什么事都不干，还是补完平衡二茶树再睡吧。

个人认为这一块的内容属于那种重要但不难的知识，所以，以思路分析为主，讲解为辅，相信只要大家能够按照博主的思路理一下，很容易就能理解了。

好了，以下就是纯干货环节：

要理解平衡二茶树，首先我们要从他的性质入手。这里我会从平衡二茶树两个性质着手，一步步分析出它的实现原理。

相信大家在学习平衡二叉树最大的难点就是左旋右旋了吧，但只要利用好这两个性质，并展开分析就会变得很简单。

这里我共列出了左旋，右旋，先坐旋后右旋以及先右旋后左旋的8种情况，不出意外，我已经列出所有的可能性了，博主运用排列组合的方式给出自认为的最全的情况。

首先是左旋的两种情况（图片标题写错了这是左旋）：

哈哈，画完图才傻傻发现自己写错标题了，大家就当他是左旋哈，这里有两种情况。

第一种就是上面那个没有多余子节点的情况，此时把旋转开始节点的右子节点变成根节点，根节点变为左子节点就行了

第二种比较复杂，是有子节点的情况，首先我们从A节点下探，A的左子树的深度为2，A的右子树的深度为4,4-2=2>1,因此我们需要左旋，将A节点变为C节点的左子节点，把C节点变为根节点，此时我们会发现多出一个节点D无处安放，而根据二叉查找的树的性质我们可以知道D节点是以A为根节点情况下右边最小的节点，也就是说D在A的右子树里最小，在左子树里最大，并且比A大，那么在变换后很显然只能放在C的左子树的最右边，此时也就是A的右子节点，比A大，比C小。
这就是左旋的两种情况，我觉得也应该就这两种了，代码实现方式是一样的。下面上代码：

		//左旋public void leftRomate(RBTree root) {//获得左旋节点的右子节点RBTree right = root.getRightNode();//获得左旋节点的父亲节点RBTree parent = null;if(root.getParentNode() != null) {parent = root.getParentNode();}//将左旋节点的右子节点的父亲节点变为左旋节点的父亲节点right.setParentNode(parent);if(parent != null) {if(parent.getLeftNode() == root) {parent.setLeftNode(right);}else {parent.setRightNode(right);}}//将左旋节点的右子节点的右子节点变为它右节点的左节点if(right.getLeftNode() != null) {right.getLeftNode().setParentNode(root);}root.setRightNode(right.getLeftNode());//左旋节点的右节点的左节点变为左旋节点right.setLeftNode(root);root.setParentNode(right);}
 

介绍完左旋，现在介绍右旋吧，具体原理就不说了，和左旋一样直接看实现吧，嗯。。。我先放张手绘，和上面图片一样左右旋写反了，嘻嘻。

//右旋public void rightRomate(RBTree root) {//获得右旋节点的左子节点RBTree left = root.getLeftNode();//获得右旋节点的父亲节点RBTree parent = null;if(root.getParentNode() != null) {parent = root.getParentNode();}//将右旋节点的左子节点的父亲节点变为右旋节点的父亲节点left.setParentNode(parent);if(parent != null) {if(parent.getLeftNode() == root) {parent.setLeftNode(left);}else {parent.setRightNode(left);}}if(left.getRightNode() != null) {//将右旋节点的左子节点设为它的左子节点的右子节点left.getRightNode().setParentNode(root);}root.setLeftNode(left.getRightNode());//将右旋节点的左子节点的右子节点设为右旋节点left.setRightNode(root);root.setParentNode(left);}
 

下面再来先右旋后左旋的情况，因为实在很简单，直接上图给代码：
其实从图中很直接就能看到，先对E节点右旋，再对A节点进行左旋

	//先右旋再左旋private static void rightAndLeftRomate(RBTree root) {//先右旋RBTree rightRomate = root;while(rightRomate.getRightNode() != null) {rightRomate = rightRomate.getRightNode(); }rightRomate(rightRomate);//再左旋leftRomate(root);}
 

最后是先左旋后右旋的情况：

	//先左旋再右旋private static void leftAndRightRomate(RBTree root) {//先左旋RBTree leftRomate = root;while(leftRomate.getLeftNode() != null) {leftRomate = leftRomate.getLeftNode();}//再右旋rightRomate(root);}
 

这些准备工作，其实就是平衡二叉树的难点所在做完后就可以来实现增删了，先来写增加节点吧

	public void insert(RBTree root,RBTree e) {//找到根节点getRoot(root); //找到要插入节点的地方RBTree point = root;while((point.getLeftNode() != null && point.getValue() > e.getValue()) || (point.getRightNode() != null && point.getValue() < e.getValue())) {if(point.getValue() > e.getValue())  {point = point.getLeftNode();}else {point = point.getRightNode();}}//插入if(point.getValue() > e.getValue()) {point.setLeftNode(e);e.setParentNode(point);}else if(point.getValue() < e.getValue()) {point.setRightNode(e);e.setParentNode(point);}else {point.setKey(e.getKey());}//判断是否是平衡二叉树RBTree p = isBlance(e);//不平衡，需要变换if(p != null) {int i = getHight(p.getLeftNode())-getHight(p.getRightNode()); RBTree l = p;if(i == 2) {while(l.getLeftNode() != null) {l = l.getLeftNode();}if(l.getRightNode() == null) {rightRomate(p);}else {leftAndRightRomate(p);}}else {while(l.getRightNode() != null) {l = l.getRightNode();}if(l.getLeftNode() == null) {leftRomate(p);}else {rightAndLeftRomate(p);}}}}public int getHight(RBTree node) {if(node == null) return 0;int lHeight=getHight(node.getLeftNode());int rHeight=getHight(node.getRightNode());return Math.max(lHeight, rHeight)+1;}public RBTree isBlance(RBTree e) {RBTree root = e.getParentNode();int p = 0;while(p != 2 && p != -2) {if(root.getParentNode() != null) {root = root.getParentNode();}else {return null;}p=getHight(root.getLeftNode())-getHight(root.getRightNode());	}return root;}//找到根节点public RBTree getRoot(RBTree root) {	RBTree root1 = root;while(root1.getParentNode() != null) {root1 = root.getParentNode();}return root1;}
 

最后是删除操作，其实平衡二叉树的删除比插入简单的多，就是前一篇博客的二叉查找树的删除再加上上面插入元素的代码里的平衡操作，这里就偷个懒不写代码了。

测试（这里我用的中序遍历，这样只要结果是从小到大来排序的说明代码就是对的）：

	//中序遍历public void inorderTraversal(RBTree root) {if(root == null) return;if(root.getLeftNode() != null) {inorderTraversal(root.getLeftNode());}System.out.print(root.getKey() + root.getValue()+"..");if(root.getRightNode() != null) {inorderTraversal(root.getRightNode());}}//测试方法public void test(RBTree e) {RBTree root = getRoot(e);inorderTraversal(root);}//主函数
 public class RTBtreeTest {public static void main(String[] args) {RBTree A = new RBTree(2, "A");RBTree B = new RBTree(1, "B");RBTree C = new RBTree(4, "C");RBTree D = new RBTree(3, "D");RBTree E = new RBTree(5, "E");RBTree F = new RBTree(6, "F");RBTree G = new RBTree(7, "G");RBTree H = new RBTree(13, "H");RBTree I = new RBTree(8, "I");RBTree J = new RBTree(9, "J");RBTree K = new RBTree(10, "K");RBTree L = new RBTree(11, "L");RBTree M = new RBTree(12, "M");AVlRTree tree = new AVlRTree();tree.insert(A, C);tree.insert(C, F);tree.insert(C, M);tree.insert(C, B);tree.insert(C, E);tree.insert(C, F);tree.insert(C, H);tree.insert(C, G);tree.insert(C, I);tree.insert(C, L);tree.insert(C, K);tree.insert(C, D);tree.insert(C, J);tree.test(C);}
 

这里我一共创建了从1-13的数字，打乱了顺序挨个插入（这里为了表示重复元素的插入不变还重复插入了F节点），最后打印出结果为：
可见平衡二叉树的插入是完成了。