详解Java数据结构之平衡二叉树

目录

什么是二叉搜索树

简单来说，就是方便搜索的二叉树，是一种具备特定结构的二叉树，即，对于节点n，其左子树的所有节点的值都小于等于其值，其右子树的所有节点的值都大于等于其值。​

以序列2,4,1,3,5,10,9,8为例，如果以二叉搜索树建树的方式，我们建立出来的逐个步骤应该为

第一步：

第二步：

第三步：

第四步：

第五步：

第六步：

第七步：

第八步：

按照不平衡的普通方法生成的二叉搜索树就是这么一个样子。其实现代码如下：

package com.chaojilaji.book.archtree;import com.chaojilaji.auto.autocode.utils.json;import java.util.objects;public class archtreeutils {  public static archtree buildtree(archtree archtree, integer value) {    if (value >= archtree.getvalue()) {      if (objects.isnull(archtree.getrightchild())) {        archtree archtree1 = new archtree();        archtree1.tvalue(value);        archtree.trightchild(archtree1);      } el {        buildtree(archtree.getrightchild(), value);      }    } el {      if (objects.isnull(archtree.getleftchild())) {        archtree archtree1 = new archtree();        archtree1.tvalue(value);        archtree.tleftchild(archtree1);      } el {        buildtree(archtree.getleftchild(), value);      }    }    return archtree;  }  public static void main(string[] args) {    int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8};    archtree archtree = new archtree();    archtree.tvalue(a[0]);    for (int i = 1; i < a.length; i++) {      archtree = buildtree(archtree,a[i]);    }    system.out.println(json.tojson(archtree));  }}

运行的结果如下：

{    "value": 2,    "left_child": {        "value": 1,        "left_child": null,        "right_child": null    },    "right_child": {        "value": 4,        "left_child": {            "value": 3,            "left_child": null,            "right_child": null        },        "right_child": {            "value": 5,            "left_child": null,            "right_child": {                "value": 10,                "left_child": {                    "value": 9,                    "left_child": {                        "value": 8,                        "left_child": null,                        "right_child": null                    },                  实践比学习更重要  "right_child": null                },                "right_child": null            }        }    }}

与我们的目标结果是一致的。

好了，那我们本节就完毕了。可是转过头可能你也发现了，直接生成的这个二叉搜索树似乎有点太长了，层数有点太多了，一般来说，一个长度为8的序列，四层结构的二叉树就可以表现出来了，这里却使用了六层，显然这样的结果不尽人意，同时太深的层数，也增加了查找的时间复杂度。

这就给我们的树提了要求，我们需要将目前构造出来的树平衡一下，让这棵二叉搜索树的左右子树“重量”最好差不多。

平衡二叉搜索树

首先需要掌握两个概念

平衡因子就是对于这棵二叉搜索树的每个节点来说，其左子树的高度减去右子树的高度即为该节点的平衡因子，该数值能很快的辨别出该节点究竟是左子树高还是右子树高。在平衡二叉树中规定，当一个节点的平衡因子的绝对值大于等于2的时候，我们就认为该节点不平衡，需要进行调整。那么这种调整的手段称之为节点与节点的旋转，通俗来说，旋转就是指的节点间的指向关系发生变化，在c语言中就是指针指向的切换。

在调用旋转之前，我们需要判断整棵树是否平衡，即，这棵二叉搜索树的所有平衡因子是否有绝对值大于等于2的，如果有，就找出最小的一棵子树。可以确定的是，如果前一次二叉搜索树是平衡的，那么此时如果加一个节点进去，造成不平衡，那么节点从叶子开始回溯，找到的第一个大于等于2的节点势必为最小不平衡子树的根节点。

对于这棵最小不平衡的子树，我们需要得到两个值，即根节点的平衡因子a，以及左右子树根节点中平衡因子绝对值较大者的平衡因子b。
我们可以将需要旋转的类型抽象为以下四种：​

1.左左型（正正型，即 a>0 && b>0）

左左型最后想要达到的目标是第二个节点成为根节点，第一个节点成为第二个节点的右节点。

所以用伪代码展示就是（设a1，a2，a3分别为图里面从上到下的三个节点）

a2的右子树 = (合并(a2的右子树,a1的右子树) + a1顶点值) 一起构成的二叉搜索树;

返回 a2

2.左右型（正负型，即 a>0 && b<0）

设a1，a2，a3分别为图里面从上到下的三个节点

首先应该通过将a3和a2调换上下位置，使之变成左左型，然后再调用左左型的方法就完成了。

从左右型调换成左左型，即将a2及其左子树成为a3左子树的一部分，然后将a1的左子树置为a3即可。

伪代码如下：

a3的左子树 = a2及其左子树与a3的左子树合并成的一棵二叉搜索树;

a1的左子树 = a3;

3.右右型（负负型，即 a<0 && b<0）

设a1，a2，a3分别为图里面从上到下的三个节点

右右型与左左型类似，要达到的目的就是a1成为a2左子树的一部分，伪代码为：

a2的左子树 = （合并a2的左子树和a1的左子树）+ a1顶点的值构成的二叉搜索树;

返回a2

4.右左型（负正型，即 a<0 && b>0）

设a1，a2，a3分别为图里面从上到下的三个节点

右左型需要先转换成右右型，然后在调用右右型的方法即可。

从右左型到右右型，即需要将a2及其右子树成为a3右子树的一部分，然后将a1的右子树置为a3即可。

伪代码如下：

a3的右子树 = a2及其右子树与a3的右子树合并成的一棵二叉搜索树;

a1的右子树 = a3;

从上面的分析可以得出，我们不仅仅需要实现旋转的方法，还需要实现合并二叉树等方法，这些方法都是基础方法，读者需要确保会快速写出来。

请读者朋友们根据上面的内容，先尝试写出集中平衡化的方法。

平衡二叉搜索树建树程序

平衡二叉搜索树建树，需要在二叉搜索树建树的基础上加上平衡的过程，即子树之间指针转换的问题，同时，由于这种指针转换引起的子树的子树也会产生不平衡，所以上面提到的四种旋转调整方式都是递归的。

首先，先构建节点基础结构：

public class archtree {  private integer value;  private archtree leftchild;  private archtree rightchild;  private integer balancenumber = 0;  private integer height = 0;}

值，高度，平衡因子，左子树，右子树

计算每个节点的高度

这是计算二叉搜索树中每个平衡因子的基础，我们设最低层为高度1，则计算节点高度的代码为：

public static integer countheight(archtree archtree) {    if (objects.isnull(archtree)) {        return 0;    }    archtree.theight(math.max(countheight(archtree.getleftchild()),                                  countheight(archtree.getrightchild())) + 1);    return archtree.getheight();}

这里有个半动态规划的结论：当前节点的高度，等于左右子树的最大高度+1；这里的写法有点树形dp的味道。

计算每个节点的平衡因子

public static void countbalancenumber(archtree archtree, maxnumber max, archtree fathertree, integer type) {  if (objects.nonnull(archtree.getvalue())) {    if (objects.isnull(archtree.getleftchild())      && objects.nonnull(archtree.getrightchild())) {      archtree.tbalancenumber(-archtree.getrightchild().getheight());    }    if (objects.nonnull(archtree.getleftchild())      && objects.isnull(archtree.getrightchild())) {      archtree.tbalancenumber(archtree.getleftchild().getheight());    }    if (objects.isnull(archtree.getleftchild())      && objects.isnull(archtree.getrightchild())) {      archtree.tbalancenumber(0);    }    if (objects.nonnull(archtree.getleftchild())      && objects.nonnull(archtree.getrightchild())) {      archtree.tbalancenumber(archtree.getleftchild().getheight()                    - archtree.getrightchild().getheight());    }  }  if (objects.nonnull(archtree.getleftchild())) {    countbalancenumber(archtree.getleftchild(), max, archtree, 1);  }  if (objects.nonnull(archtree.getrightchild())) {    countbalancenumber(archtree.getrightchild(), max, archtree, 2);  }}

本质上讲，平衡因子就是左子树高度减去右子树高度，注意这里左右子树都有可能不存在，所以加入了一堆特判。

判断当前二叉树是否平衡

static class maxnumber {  public integer max;  public archtree childtree;  public archtree fathertree;  public integer flag = 0; // 0 代表自己就是根,1代表childtree是左子树，2代表childtree是右子树}public static maxnumber checkbalance(archtree archtree) {  maxnumber max = new maxnumber();  max.max = 0;  countbalancenumber(archtree, max, null, 0);  return max;}public static void countbalancenumber(archtree archtree, maxnumber max, archtree fathertree, integer type) {  if (objects.nonnull(archtree.getvalue())) {    if (objects.isnull(archtree.getleftchild())      && objects.nonnull(archtree.getrightchild())) {      archtree.tbalancenumber(-archtree.getrightchild().getheight());    }    if (objects.nonnull(archtree.getleftchild())      && objects.isnull(archtree.getrightchild())) {      archtree.tbalancenumber(archtree.getleftchild().getheight());    }    if (objects.isnull(archtree.getleftchild())      && objects.isnull(archtree.getrightchild())) {      archtree.tbalancenumber(0);    }    if (objects.nonnull(archtree.getleftchild())      && objects.nonnull(archtree.getrightchild())) {      archtree.tbalancenumber(archtree.getleftchild().getheight()                    - archtree.getrightchild().getheight());    }  }  if (objects.nonnull(archtree.getleftchild())) {    countbalancenumber(archtree.getleftchild(), max, archtree, 1);  }  if (objects.nonnull(archtree.getrightchild())) {    countbalancenumber(archtree.getrightchild(), max, archtree, 2);  }  if (math.abs(archtree.getbalancenumber()) >= math.abs(max.max)) {    if (math.abs(archtree.getbalancenumber()) == math.abs(max.max)      && max.childtree == null) {      max.childtree = archtree;      max.fathertree = fathertree;      max.flag = type;      max.max = archtree.getbalancenumber();    }    if (math.abs(archtree.getbalancenumber()) > math.abs(max.max)) {      max.childtree = archtree;      max.fathertree = fathertree;      max.flag = type;      max.max = archtree.getbalancenumber();    }  }}

其中，maxnumber类是为了保存第一棵不平衡的子树而存在的结构，为了使这棵子树平衡之后能重新回到整棵树中，需要在maxnumber中存储当前子树父节点，同时标明当前子树是父节点的左子树还是右子树，还是本身。

合并二叉树

public static void getallvalue(archtree tree, t<integer> ts) {  if (objects.isnull(tree)) return;  if (objects.nonnull(tree.getvalue())) {    ts.add(tree.getvalue());  }  if (objects.nonnull(tree.getleftchild())) {    getallvalue(tree.getleftchild(), ts);  }  if (objects.nonnull(tree.getrightchild())) {    getallvalue(tree.getrightchild(), ts);  }}/**  * 合并两棵二叉搜索树  *  * @param a  * @param b  * @return  */public static archtree mergetree(archtree a, archtree b) {  t<integer> v扶老奶奶过马路als = new hasht<>();  getallvalue(b, vals);  for (integer c : vals) {    a = buildtree(a, c);  }  return a;}

将一棵树转成数字集合，然后通过建树的方式建到另外一棵树上即可。

旋转调整函数

1.左左型旋转/**     * 左左     *     * @param archtree     * @return     */public static archtree leftrotate1(archtree father, archtree archtree) {    archtree b = father;    archtree newright = mergetree(father.getrightchild(), archtree.getrightchild());    newright = buildtree(newright, b.getvalue());    countheight(newright);    while (math.abs(checkbalance(newright).childtree.getbalancenumber()) >= 2) {        newright = rotate(checkbalance(newright).childtree);        countheight(newright);    }    archtree.trightchild(newright);    return archtree;}

2.右右型旋转

/**     * 右右     * @param father     * @param archtree     * @return     */public static archtree rightrotate1(archtree father, archtree archtree) {    archtree b = father;    archtree newleft = mergetree(father.getleftchild(), archtree.getleftchild());    newleft = buildtree(newleft, b.getvalue());    countheight(newleft);    while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {        newleft = rotate(checkbalance(newleft).childtree);        countheight(newleft);    }    archtree.tleftchild(newleft);    return archtree;}

3.左右型旋转

/**     * 左右     *     * @param archtree     * @return     */public static archtree rightrotate2(archtree father, archtree archtree) {    archtree a1 = father;    archtree a2 = archtree;    archtree a3 = archtree.getrightchild();    archtree newleft = mergetree(a2.getleftchild(), a3.getleftchild());    newleft = buildtree(newleft, a2.getvalue());    countheight(newleft);    while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {        newleft = rotate(checkbalance(newleft).childtree);        countheight(newleft);    }    a3.tleftchild(newleft);    a1.tleftchild(a3);    return a1;}

4.右左型旋转

/**     * 右左     *     * @param archtree     * @return     */public static archtree leftrotate2(archtree father, archtree archtree) {    archtree a1 = father;    archtree a2 = archtree;    archtree a3 = archtree.getleftchild();    archtree newright = mergetree(a2.getrightchild(), a3.getrightchild());    newright = buildtree(newright, a2.getvalue());    countheight(newright);    while (math.abs(checkbalance(newright).childtree.getbalancenumb金锁记er()) >= 2) {        newright = rotate(checkbalance(newright).childtree);        countheight(newright);    }    a3.trightchild(newright);    a1.trightchild(a3);    return a1;}

旋转调用函数：

public static archtree rotate(archtree archtree) {    int a = archtree.getbalancenumber();    if (math.abs(a) < 2) {        return archtree;    }    int b = objects.isnull(archtree.getleftchild()) ? 0         : archtree.getleftchild().getbalancenumber();    int c = objects.isnull(archtree.getrightchild()) ? 0         : archtree.getrightchild().getbalancenumber();    if (a > 0) {        if (b > 0) {            // todo: 2022/1/13 左左            archtree = leftrotate1(archtree, archtree.getleftchild());        } el {            // todo: 2022/1/13 左右            archtree = rightrotate2(archtree, archtree.getleftchild());            archtree = leftrotate1(archtree, archtree.getleftchild());        }    } el {        if (c > 0) {            // todo: 2022/1/13 右左            archtree = leftrotate2(archtree, archtree.getrightchild());            archtree = rightrotate1(archtree, ar面包是什么意思chtree.getrightchild());        } el {            // todo: 2022/1/13 右右            archtree = rightrotate1(archtree, archtree.getrightchild());        }    }    return archtree;}

整体代码

package com.chaojilaji.book.archtree;import com.chaojilaji.auto.autocode.utils.json;import com.chaojilaji.book.tree.handle;import com.chaojilaji.book.tree.tree;import org.omg.corba.obj_adapter;import java.util.hasht;import java.util.objects;import java.util.t;public class archtreeutils {static class maxnumber {public integer max;public archtree childtree;public archtree fathertree;public integer flag = 0; // 0 代表自己就是根,1代表childtree是左子树，2代表childtree是右子树}public static archtree rotate(archtree archtree) {int a = archtree.getbalancenumber();if (math.abs(a) < 2) {return archtree;}int b = objects.isnull(archtree.getleftchild()) ? 0 : archtree.getleftchild().getbalancenumber();int c = objects.isnull(archtree.getrightchild()) ? 0 : archtree.getrightchild().getbalancenumber();if (a > 0) {if (b > 0) {// todo: 2022/1/13 左左archtree = leftrotate1(archtree, archtree.getleftchild());} el {// todo: 2022/1/13 左右archtree = rightrotate2(archtree, archtree.getleftchild());archtree = leftrotate1(archtree, archtree.getleftchild());}} el {if (c > 0) {// todo: 2022/1/13 右90年代歌曲左archtree = leftrotate2(archtree, archtree.getrightchild());archtree = rightrotate1(archtree, archtree.getrightchild());} el {// todo: 2022/1/13 右右archtree = rightrotate1(archtree, archtree.getrightchild());}}return archtree;}public static void getallvalue(archtree tree, t<integer> ts) {if (objects.isnull(tree)) return;if (objects.nonnull(tree.getvalue())) {ts.add(tree.getvalue());}if (objects.nonnull(tree.getleftchild())) {getallvalue(tree.getleftchild(), ts);}if (objects.nonnull(tree.getrightchild())) {getallvalue(tree.getrightchild(), ts);}}/*** 合并两棵二叉搜索树** @param a* @param b* @return*/public static archtree mergetree(archtree a, archtree b) {t<integer> vals = new hasht<>();getallvalue(b, vals);for (integer c : vals) {a = buildtree(a, c);}return a;}/*** 左左** @param archtree* @return*/public static archtree leftrotate1(archtree father, archtree archtree) {archtree b = father;archtree newright = mergetree(father.getrightchild(), archtree.getrightchild());newright = buildtree(newright, b.getvalue());countheight(newright);while (math.abs(checkbalance(newright).childtree.getbalancenumber()) >= 2) {newright = rotate(checkbalance(newright).childtree);countheight(newright);}archtree.trightchild(newright);return archtree;}/*** 右左** @param archtree* @return*/public static archtree leftrotate2(archtree father, archtree archtree) {archtree a1 = father;archtree a2 = archtree;archtree a3 = archtree.getleftchild();archtree newright = mergetree(a2.getrightchild(), a3.getrightchild());newright = buildtree(newright, a2.getvalue());countheight(newright);while (math.abs(checkbalance(newright).childtree.getbalancenumber()) >= 2) {newright = rotate(checkbalance(newright).childtree);countheight(newright);//            system.out.println(json.tojson(newright));}a3.trightchild(newright);a1.trightchild(a3);return a1;}/*** 右右* @param father* @param archtree* @return*/public static archtree rightrotate1(archtree father, archtree archtree) {archtree b = father;archtree newleft = mergetree(father.getleftchild(), archtree.getleftchild());newleft = buildtree(newleft, b.getvalue());countheight(newleft);//         todo: 2022/1/13 合并后的也有可能有问题while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {newleft = rotate(checkbalance(newleft).childtree);countheight(newleft);//            system.out.println(json.tojson(newleft));}archtree.tleftchild(newleft);return archtree;}/*** 左右** @param archtree* @return*/public static archtree rightrotate2(archtree father, archtree archtree) {archtree a1 = father;archtree a2 = archtree;archtree a3 = archtree.getrightchild();archtree newleft = mergetree(a2.getleftchild(), a3.getleftchild());newleft = buildtree(newleft, a2.getvalue());countheight(newleft);while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {newleft = rotate(checkbalance(newleft).childtree);countheight(newleft);}a3.tleftchild(newleft);a1.tleftchild(a3);return a1;}public static maxnumber checkbalance(archtree archtree) {maxnumber max = new maxnumber();max.max = 0;countbalancenumber(archtree, max, null, 0);return max;}public static integer countheight(archtree archtree) {if (objects.isnull(archtree)) {return 0;}archtree.theight(math.max(countheight(archtree.getleftchild()), countheight(archtree.getrightchild())) + 1);return archtree.getheight();}public static void countbalancenumber(archtree archtree, maxnumber max, archtree fathertree, integer type) {if (objects.nonnull(archtree.getvalue())) {if (objects.isnull(archtree.getleftchild()) && objects.nonnull(archtree.getrightchild())) {archtree.tbalancenumber(-archtree.getrightchild().getheight());}if (objects.nonnull(archtree.getleftchild()) && objects.isnull(archtree.getrightchild())) {archtree.tbalancenumber(archtree.getleftchild().getheight());}if (objects.isnull(archtree.getleftchild()) && objects.isnull(archtree.getrightchild())) {archtree.tbalancenumber(0);}if (objects.nonnull(archtree.getleftchild()) && objects.nonnull(archtree.getrightchild())) {archtree.tbalancenumber(archtree.getleftchild().getheight() - archtree.getrightchild().getheight());}}if (objects.nonnull(archtree.getleftchild())) {countbalancenumber(archtree.getleftchild(), max, archtree, 1);}if (objects.nonnull(archtree.getrightchild())) {countbalancenumber(archtree.getrightchild(), max, archtree, 2);}if (math.abs(archtree.getbalancenumber()) >= math.abs(max.max)) {if (math.abs(archtree.getbalancenumber()) == math.abs(max.max) && max.childtree == null) {max.childtree = archtree;max.fathertree = fathertree;max.flag = type;max.max = archtree.getbalancenumber();}if (math.abs(archtree.getbalancenumber()) > math.abs(max.max)) {max.childtree = archtree;max.fathertree = fathertree;max.flag = type;max.max = archtree.getbalancenumber();}}}public static archtree buildtree(archtree archtree, integer value) {if (objects.isnull(archtree)) {archtree = new archtree();}if (objects.isnull(archtree.getvalue())) {archtree.tvalue(value);return archtree;}if (value >= archtree.getvalue()) {if (objects.isnull(archtree.getrightchild())) {archtree archtree1 = new archtree();archtree1.tvalue(value);archtree.trightchild(archtree1);} el {buildtree(archtree.getrightchild(), value);}} el {if (objects.isnull(archtree.getleftchild())) {archtree archtree1 = new archtree();archtree1.tvalue(value);archtree.tleftchild(archtree1);} el {buildtree(archtree.getleftchild(), value);}}return archtree;}public static void main(string[] args) {//        int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8};int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8, 6, 7};archtree archtree = new archtree();for (int i = 0; i < a.length; i++) {archtree = buildtree(archtree, a[i]);countheight(archtree);maxnumber maxnumber = checkbalance(archtree);archtree archtree1 = maxnumber.childtree;if (math.abs(archtree1.getbalancenumber()) >= 2) {archtree1 = rotate(archtree1);if (maxnumber.flag == 0) {maxnumber.fathertree = archtree1;archtree = archtree1;} el if (maxnumber.flag == 1) {maxnumber.fathertree.tleftchild(archtree1);} el if (maxnumber.flag == 2) {maxnumber.fathertree.trightchild(archtree1);}countheight(archtree);}}system.out.println("最终为\n" + json.tojson(archtree));}}

以序列2, 4, 1, 3, 5, 10, 9, 8, 6, 7为例，构造的平衡二叉搜索树结构为

{"value": 4,"left_child": {"value": 2,"left_child": {"value": 1,"left_child": null,"right_child": null,"balance_number": 0,"height": 1},"right_child": {"value": 3,"left_child": null,"right_child": null,"balance_number": 0,"height": 1},"balance_number": 0,"height": 2},"right_child": {"value": 8,"left_child": {"value": 6,"left_child": {"value": 5,"left_child": null,"right_child": null,"balance_number": 0,"height": 1},"right_child": {"value": 7,"left_child": null,"right_child": null,"balance_number": 0,"height": 1},"balance_number": 0,"height": 2},"right_child": {"value": 10,"left_child": {"value": 9,"left_child": null,"right_child": null,"balance_number": 0,"height": 1},"right_child": null,"balance_number": 1,"height": 2},"balance_number": 0,"height": 3},"balance_number": -1,"height": 4}

以上就是详解java数据结构之平衡二叉树的详细内容，更多关于java平衡二叉树的资料请关注www.887551.com其它相关文章！