详解Java数据结构之平衡二叉树
目录
- 什么是二叉搜索树
- 平衡二叉搜索树
- 平衡二叉搜索树建树程序
- 计算每个节点的高度
- 计算每个节点的平衡因子
- 合并二叉树
- 旋转调整函数
- 整体代码
什么是二叉搜索树
简单来说，就是方便搜索的二叉树，是一种具备特定结构的二叉树，即，对于节点n，其左子树的所有节点的值都小于等于其值，其右子树的所有节点的值都大于等于其值。
以序列2,4,1,3,5,10,9,8为例，如果以二叉搜索树建树的方式，我们建立出来的逐个步骤应该为
第一步：
第二步：
第三步：
第四步：
第五步：
第六步：
第七步：
第八步：
按照不平衡的普通方法生成的二叉搜索树就是这么一个样子。其实现代码如下：
package com.chaojilaji.book.searchtree;
import com.chaojilaji.auto.autocode.utils.Json;
import java.util.Objects;
public class SearchTreeUtils {
public static SearchTree buildTree(SearchTree searchTree, Integer value) {
if (value >= searchTree.getValue()) {
if (Objects.isNull(searchTree.getRightChild())) {
SearchTree searchTree1 = new SearchTree();
searchTree1.setValue(value);
searchTree.setRightChild(searchTree1);
} else {
buildTree(searchTree.getRightChild(), value);
}
} else {
if (Objects.isNull(searchTree.getLeftChild())) {
SearchTree searchTree1 = new SearchTree();
searchTree1.setValue(value);
searchTree.setLeftChild(searchTree1);
} else {
buildTree(searchTree.getLeftChild(), value);
}
}
return searchTree;
}
public static void main(String[] args) {
int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8};
SearchTree searchTree = new SearchTree();
searchTree.setValue(a[0]);
for (int i = 1; i < a.length; i++) {
searchTree = buildTree(searchTree,a[i]);
}
System.out.println(Json.toJson(searchTree));
}
}
运行的结果如下：
{
"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 SearchTree {
private Integer value;
private SearchTree leftChild;
private SearchTree rightChild;
private Integer balanceNumber = 0;
private Integer height = 0;
}
值，高度，平衡因子，左子树，右子树
计算每个节点的高度
这是计算二叉搜索树中每个平衡因子的基础，我们设最低层为高度1，则计算节点高度的代码为：
public static Integer countHeight(SearchTree searchTree) {
if (Objects.isNull(searchTree)) {
return 0;
}
searchTree.setHeight(Math.max(countHeight(searchTree.getLeftChild()),
countHeight(searchTree.getRightChild())) + 1);
return searchTree.getHeight();
}
这里有个半动态规划的结论：当前节点的高度，等于左右子树的最大高度+1；这里的写法有点树形DP的味道。
计算每个节点的平衡因子
public static void countBalanceNumber(SearchTree searchTree, MaxNumber max, SearchTree fatherTree, Integer type) {
if (Objects.nonNull(searchTree.getValue())) {
if (Objects.isNull(searchTree.getLeftChild())
&& Objects.nonNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(-searchTree.getRightChild().getHeight());
}
if (Objects.nonNull(searchTree.getLeftChild())
&& Objects.isNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight());
}
if (Objects.isNull(searchTree.getLeftChild())
&& Objects.isNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(0);
}
if (Objects.nonNull(searchTree.getLeftChild())
&& Objects.nonNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight()
- searchTree.getRightChild().getHeight());
}
}
if (Objects.nonNull(searchTree.getLeftChild())) {
countBalanceNumber(searchTree.getLeftChild(), max, searchTree, 1);
}
if (Objects.nonNull(searchTree.getRightChild())) {
countBalanceNumber(searchTree.getRightChild(), max, searchTree, 2);
}
}
本质上讲，平衡因子就是左子树高度减去右子树高度，注意这里左右子树都有可能不存在，所以加入了一堆特判。
判断当前二叉树是否平衡
static class MaxNumber {
public Integer max;
public SearchTree childTree;
public SearchTree fatherTree;
public Integer flag = 0; // 0 代表自己就是根,1代表childTree是左子树，2代表childTree是右子树
}
public static MaxNumber checkBalance(SearchTree searchTree) {
MaxNumber max = new MaxNumber();
max.max = 0;
countBalanceNumber(searchTree, max, null, 0);
return max;
}
public static void countBalanceNumber(SearchTree searchTree, MaxNumber max, SearchTree fatherTree, Integer type) {
if (Objects.nonNull(searchTree.getValue())) {
if (Objects.isNull(searchTree.getLeftChild())
&& Objects.nonNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(-searchTree.getRightChild().getHeight());
}
if (Objects.nonNull(searchTree.getLeftChild())
&& Objects.isNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight());
}
if (Objects.isNull(searchTree.getLeftChild())
&& Objects.isNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(0);
}
if (Objects.nonNull(searchTree.getLeftChild())
&& Objects.nonNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight()
- searchTree.getRightChild().getHeight());
}
}
if (Objects.nonNull(searchTree.getLeftChild())) {
countBalanceNumber(searchTree.getLeftChild(), max, searchTree, 1);
}
if (Objects.nonNull(searchTree.getRightChild())) {
countBalanceNumber(searchTree.getRightChild(), max, searchTree, 2);
}
if (Math.abs(searchTree.getBalanceNumber()) >= Math.abs(max.max)) {
if (Math.abs(searchTree.getBalanceNumber()) == Math.abs(max.max)
&& max.childTree == null) {
max.childTree = searchTree;
max.fatherTree = fatherTree;
max.flag = type;
max.max = searchTree.getBalanceNumber();
}
if (Math.abs(searchTree.getBalanceNumber()) > Math.abs(max.max)) {
max.childTree = searchTree;
max.fatherTree = fatherTree;
max.flag = type;
max.max = searchTree.getBalanceNumber();
}
}
}
其中，MaxNumber类是为了保存第一棵不平衡的子树而存在的结构，为了使这棵子树平衡之后能重新回到整棵树中，需要在MaxNumber中存储当前子树父节点，同时标明当前子树是父节点的左子树还是右子树，还是本身。
合并二叉树
public static void getAllValue(SearchTree tree, Set<Integer> sets) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getValue())) {
sets.add(tree.getValue());
}
if (Objects.nonNull(tree.getLeftChild())) {
getAllValue(tree.getLeftChild(), sets);
}
if (Objects.nonNull(tree.getRightChild())) {
getAllValue(tree.getRightChild(), sets);
}
}
/**
* 合并两棵二叉搜索树
*
* @param a
* @param b
* @return
*/
public static SearchTree mergeTree(SearchTree a, SearchTree b) {
Set<Integer> vals = new HashSet<>();
getAllValue(b, vals);
for (Integer c : vals) {
a = buildTree(a, c);
}
return a;
}
将一棵树转成数字集合，然后通过建树的方式建到另外一棵树上即可。
旋转调整函数
1.左左型旋转
/**
* 左左
*
* @param searchTree
* @return
*/
public static SearchTree leftRotate1(SearchTree father, SearchTree searchTree) {
SearchTree b = father;
SearchTree newRight = mergeTree(father.getRightChild(), searchTree.getRightChild());
newRight = buildTree(newRight, b.getValue());
countHeight(newRight);
while (Math.abs(checkBalance(newRight).childTree.getBalanceNumber()) >= 2) {
newRight = rotate(checkBalance(newRight).childTree);
countHeight(newRight);
}
searchTree.setRightChild(newRight);
return searchTree;
}
2.右右型旋转
/**
* 右右
* @param father
* @param searchTree
* @return
*/
public static SearchTree rightRotate1(SearchTree father, SearchTree searchTree) {
SearchTree b = father;
SearchTree newLeft = mergeTree(father.getLeftChild(), searchTree.getLeftChild());
newLeft = buildTree(newLeft, b.getValue());
countHeight(newLeft);
while (Math.abs(checkBalance(newLeft).childTree.getBalanceNumber()) >= 2) {
newLeft = rotate(checkBalance(newLeft).childTree);
countHeight(newLeft);
}
searchTree.setLeftChild(newLeft);
return searchTree;
}
3.左右型旋转
/**
* 左右
*
* @param searchTree
* @return
*/
public static SearchTree rightRotate2(SearchTree father, SearchTree searchTree) {
SearchTree a1 = father;
SearchTree a2 = searchTree;
SearchTree a3 = searchTree.getRightChild();
SearchTree 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.setLeftChild(newLeft);
a1.setLeftChild(a3);
return a1;
}
4.右左型旋转
/**
* 右左
*
* @param searchTree
* @return
*/
public static SearchTree leftRotate2(SearchTree father, SearchTree searchTree) {
SearchTree a1 = father;
SearchTree a2 = searchTree;
SearchTree a3 = searchTree.getLeftChild();
SearchTree 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);
}
a3.setRightChild(newRight);
a1.setRightChild(a3);
return a1;
}
旋转调用函数：
public static SearchTree rotate(SearchTree searchTree) {
int a = searchTree.getBalanceNumber();
if (Math.abs(a) < 2) {
return searchTree;
}
int b = Objects.isNull(searchTree.getLeftChild()) ? 0
: searchTree.getLeftChild().getBalanceNumber();
int c = Objects.isNull(searchTree.getRightChild()) ? 0
: searchTree.getRightChild().getBalanceNumber();
if (a > 0) {
if (b > 0) {
// TODO: 2022/1/13 左左
searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
} else {
// TODO: 2022/1/13 左右
searchTree = rightRotate2(searchTree, searchTree.getLeftChild());
searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
}
} else {
if (c > 0) {
// TODO: 2022/1/13 右左
searchTree = leftRotate2(searchTree, searchTree.getRightChild());
searchTree = rightRotate1(searchTree, searchTree.getRightChild());
} else {
// TODO: 2022/1/13 右右
searchTree = rightRotate1(searchTree, searchTree.getRightChild());
}
}
return searchTree;
}
整体代码
package com.chaojilaji.book.searchtree;
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.HashSet;
import java.util.Objects;
import java.util.Set;
public class SearchTreeUtils {
static class MaxNumber {
public Integer max;
public SearchTree childTree;
public SearchTree fatherTree;
public Integer flag = 0; // 0 代表自己就是根,1代表childTree是左子树，2代表childTree是右子树
}
public static SearchTree rotate(SearchTree searchTree) {
int a = searchTree.getBalanceNumber();
if (Math.abs(a) < 2) {
return searchTree;
}
int b = Objects.isNull(searchTree.getLeftChild()) ? 0 : searchTree.getLeftChild().getBalanceNumber();
int c = Objects.isNull(searchTree.getRightChild()) ? 0 : searchTree.getRightChild().getBalanceNumber();
if (a > 0) {
if (b > 0) {
// TODO: 2022/1/13 左左
searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
} else {
// TODO: 2022/1/13 左右
searchTree = rightRotate2(searchTree, searchTree.getLeftChild());
searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
}
} else {
if (c > 0) {
// TODO: 2022/1/13 右左
searchTree = leftRotate2(searchTree, searchTree.getRightChild());
searchTree = rightRotate1(searchTree, searchTree.getRightChild());
} else {
// TODO: 2022/1/13 右右
searchTree = rightRotate1(searchTree, searchTree.getRightChild());
}
}
return searchTree;
}
public static void getAllValue(SearchTree tree, Set<Integer> sets) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getValue())) {
sets.add(tree.getValue());
}
if (Objects.nonNull(tree.getLeftChild())) {
getAllValue(tree.getLeftChild(), sets);
}
if (Objects.nonNull(tree.getRightChild())) {
getAllValue(tree.getRightChild(), sets);
}
}
/**
* 合并两棵二叉搜索树
*
* @param a
* @param b
* @return
*/
public static SearchTree mergeTree(SearchTree a, SearchTree b) {
Set<Integer> vals = new HashSet<>();
getAllValue(b, vals);
for (Integer c : vals) {
a = buildTree(a, c);
}
return a;
}
/**
* 左左
*
* @param searchTree
* @return
*/
public static SearchTree leftRotate1(SearchTree father, SearchTree searchTree) {
SearchTree b = father;
SearchTree newRight = mergeTree(father.getRightChild(), searchTree.getRightChild());
newRight = buildTree(newRight, b.getValue());
countHeight(newRight);
while (Math.abs(checkBalance(newRight).childTree.getBalanceNumber()) >= 2) {
newRight = rotate(checkBalance(newRight).childTree);
countHeight(newRight);
}
searchTree.setRightChild(newRight);
return searchTree;
}
/**
* 右左
*
* @param searchTree
* @return
*/
public static SearchTree leftRotate2(SearchTree father, SearchTree searchTree) {
SearchTree a1 = father;
SearchTree a2 = searchTree;
SearchTree a3 = searchTree.getLeftChild();
SearchTree 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.setRightChild(newRight);
a1.setRightChild(a3);
return a1;
}
/**
* 右右
* @param father
* @param searchTree
* @return
*/
public static SearchTree rightRotate1(SearchTree father, SearchTree searchTree) {
SearchTree b = father;
SearchTree newLeft = mergeTree(father.getLeftChild(), searchTree.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));
}
searchTree.setLeftChild(newLeft);
return searchTree;
}
/**
* 左右
*
* @param searchTree
* @return
*/
public static SearchTree rightRotate2(SearchTree father, SearchTree searchTree) {
SearchTree a1 = father;
SearchTree a2 = searchTree;
SearchTree a3 = searchTree.getRightChild();
SearchTree 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.setLeftChild(newLeft);
a1.setLeftChild(a3);
return a1;
}
public static MaxNumber checkBalance(SearchTree searchTree) {
MaxNumber max = new MaxNumber();
max.max = 0;
countBalanceNumber(searchTree, max, null, 0);
return max;
}
public static Integer countHeight(SearchTree searchTree) {
if (Objects.isNull(searchTree)) {
return 0;
}
searchTree.setHeight(Math.max(countHeight(searchTree.getLeftChild()), countHeight(searchTree.getRightChild())) + 1);
return searchTree.getHeight();
}
public static void countBalanceNumber(SearchTree searchTree, MaxNumber max, SearchTree fatherTree, Integer type) {
if (Objects.nonNull(searchTree.getValue())) {
if (Objects.isNull(searchTree.getLeftChild()) && Objects.nonNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(-searchTree.getRightChild().getHeight());
}
if (Objects.nonNull(searchTree.getLeftChild()) && Objects.isNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight());
}
if (Objects.isNull(searchTree.getLeftChild()) && Objects.isNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(0);
}
if (Objects.nonNull(searchTree.getLeftChild()) && Objects.nonNull(searchTree.getRightChild())) {
searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight() - searchTree.getRightChild().getHeight());
}
}
if (Objects.nonNull(searchTree.getLeftChild())) {
countBalanceNumber(searchTree.getLeftChild(), max, searchTree, 1);
}
if (Objects.nonNull(searchTree.getRightChild())) {
countBalanceNumber(searchTree.getRightChild(), max, searchTree, 2);
}
if (Math.abs(searchTree.getBalanceNumber()) >= Math.abs(max.max)) {
if (Math.abs(searchTree.getBalanceNumber()) == Math.abs(max.max) && max.childTree == null) {
max.childTree = searchTree;
max.fatherTree = fatherTree;
max.flag = type;
max.max = searchTree.getBalanceNumber();
}
if (Math.abs(searchTree.getBalanceNumber()) > Math.abs(max.max)) {
max.childTree = searchTree;
max.fatherTree = fatherTree;
max.flag = type;
max.max = searchTree.getBalanceNumber();
}
}
}
public static SearchTree buildTree(SearchTree searchTree, Integer value) {
if (Objects.isNull(searchTree)) {
searchTree = new SearchTree();
}
if (Objects.isNull(searchTree.getValue())) {
searchTree.setValue(value);
return searchTree;
}
if (value >= searchTree.getValue()) {
if (Objects.isNull(searchTree.getRightChild())) {
SearchTree searchTree1 = new SearchTree();
searchTree1.setValue(value);
searchTree.setRightChild(searchTree1);
} else {
buildTree(searchTree.getRightChild(), value);
}
} else {
if (Objects.isNull(searchTree.getLeftChild())) {
SearchTree searchTree1 = new SearchTree();
searchTree1.setValue(value);
searchTree.setLeftChild(searchTree1);
} else {
buildTree(searchTree.getLeftChild(), value);
}
}
return searchTree;
}
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};
SearchTree searchTree = new SearchTree();
for (int i = 0; i < a.length; i++) {
searchTree = buildTree(searchTree, a[i]);
countHeight(searchTree);
MaxNumber maxNumber = checkBalance(searchTree);
SearchTree searchTree1 = maxNumber.childTree;
if (Math.abs(searchTree1.getBalanceNumber()) >= 2) {
searchTree1 = rotate(searchTree1);
if (maxNumber.flag == 0) {
maxNumber.fatherTree = searchTree1;
searchTree = searchTree1;
} else if (maxNumber.flag == 1) {
maxNumber.fatherTree.setLeftChild(searchTree1);
} else if (maxNumber.flag == 2) {
maxNumber.fatherTree.setRightChild(searchTree1);
}
countHeight(searchTree);
}
}
System.out.println("最终为\n" + Json.toJson(searchTree));
}
}
以序列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平衡二叉树的资料请关注我们其它相关文章！
相关推荐
-
Java数据结构之平衡二叉树的原理与实现
目录 1 平衡二叉树的概述 2 平衡二叉树的实现原理 2.1 单旋转 2.2 双旋转 2.3 总结 3 平衡二叉树的构建 3.1 类架构 3.2 查找的方法 3.3 检查是否平衡的方法 3.4 插入的方法 3.5 查找最大值和最小值 3.6 删除的方法 4 平衡二叉树的总结 平衡二叉树(AVL树),顾名思义,是一颗很“平衡”的树,它的平衡是相对于排序二叉树来说的.为了避免极端情况下二叉搜索树节点分布不均匀,甚至退化为链表,影响查找效率,我们引入了平衡二叉树,即让树的结构看起来尽量“均匀”,左右子
-
Java实现红黑树(平衡二叉树)的详细过程
目录 前言 红黑二叉查找树 2-3树 2-3树的插入操作 实现红黑二叉树 结尾 前言 在实现红黑树之前,我们先来了解一下符号表. 符号表的描述借鉴了Algorithms第四版,详情在:https://algs4.cs.princeton.edu/home/ 符号表有时候被称为字典,就如同英语字典中,一个单词对应一个解释,符号表有时候又被称之为索引,即书本最后将术语按照字母顺序列出以方便查找的那部分.总的来说,符号表就是将一个键和一个值联系起来,就如Python中的字典,JAVA中的HashMap
-
Java源码解析之平衡二叉树
一.平衡二叉树的定义 平衡二叉树是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1 .它是一种高度平衡的二叉排序树.意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1 .我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor),那么平衡二叉树上所有结点的平衡因子只可能是-1 .0 和1. 这里举个栗子: 仔细看图中值为18的节点,18的节点的深度为2 .而它的右子树的深度为0,其差
-
详解Java数据结构之平衡二叉树
目录 什么是二叉搜索树 平衡二叉搜索树 平衡二叉搜索树建树程序 计算每个节点的高度 计算每个节点的平衡因子 合并二叉树 旋转调整函数 整体代码 什么是二叉搜索树 简单来说,就是方便搜索的二叉树,是一种具备特定结构的二叉树,即,对于节点n,其左子树的所有节点的值都小于等于其值,其右子树的所有节点的值都大于等于其值. 以序列2,4,1,3,5,10,9,8为例,如果以二叉搜索树建树的方式,我们建立出来的逐个步骤应该为 第一步: 第二步: 第三步: 第四步: 第五步: 第六步: 第七步: 第八步:
-
详解java数据结构与算法之双链表设计与实现
在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因
-
详解Java数据结构和算法（有序数组和二分查找）
一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默
-
Java数据结构之平衡二叉树的实现详解
目录 定义 结点结构 查找算法 插入算法 LL 型 RR 型 LR 型 RL 型 插入方法 删除算法 概述 实例分析 代码 完整代码 定义 动机:二叉查找树的操作实践复杂度由树高度决定,所以希望控制树高,左右子树尽可能平衡. 平衡二叉树(AVL树):称一棵二叉查找树为高度平衡树,当且仅当或由单一外结点组成,或由两个子树形 Ta 和 Tb 组成,并且满足: |h(Ta) - h(Tb)| <= 1,其中 h(T) 表示树 T 的高度 Ta 和 Tb 都是高度平衡树 即:每个结点的左子树和右子树的高
-
详解Java集合中的基本数据结构
集合中三大数据结构 数组 内存地址连续 可以通过下标的成员访问,下标访问的性能高 增删操作有较大的性能消耗(需要动态扩容) 链表(双向链表) 灵活的空间要求,存储空间不要求连续 不支持下标访问,支持顺序遍历搜索 针对增删操作找到对应的节点改变链表的头尾指针指向即可,无需移动元数据存储位置 树(Java中二叉树特性) 某节点的左子树节点仅包含小于该节点的值 某节点的右子树节点仅包含大于该节点的值 节点必须是二叉树 顺序排列 存在问题:树可以认为是介于数组和链表二者之间的一种数据结构,拥有较快的查询
-
详解Java实现数据结构之并查集
一.什么是并查集 对于一种数据结构,肯定是有自己的应用场景和特性,那么并查集是处理什么问题的呢? 并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题,常常在使用中以森林来表示.在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受:即使在空
-
详解Java 二叉树的实现和遍历
目录 什么是二叉树 二叉树建树 前序建树 中序建树 后序建树 二叉树的遍历 什么是二叉树 简单理解为对于一个节点来说,最多拥有一个上级节点,同时最多具备左右两个下级节点的数据结构. 由于很多排序算法都是基于二叉树实现的,多叉树也是二叉树延伸过去的,所以二叉树的建树和遍历就显得非常重要. 二叉树建树 一般情况是给你一个串,要求让你以前序,中序,后序的方式建树.那么此时我们就需要首先了解三个概念: 前序遍历 中序遍历 后序遍历 我们来看看一棵二叉树的结构: 0 1 2 3 4 5 6 0就是整个二叉
-
详解Java 二叉树的实现和遍历
目录 什么是二叉树 二叉树建树 前序建树 中序建树 后序建树 二叉树的遍历 什么是二叉树 简单理解为对于一个节点来说,最多拥有一个上级节点,同时最多具备左右两个下级节点的数据结构. 由于很多排序算法都是基于二叉树实现的,多叉树也是二叉树延伸过去的,所以二叉树的建树和遍历就显得非常重要. 二叉树建树 一般情况是给你一个串,要求让你以前序,中序,后序的方式建树.那么此时我们就需要首先了解三个概念: 前序遍历 中序遍历 后序遍历 我们来看看一棵二叉树的结构: 0 1 2 3 4 5 6 0就是整个二叉
-
详解Java中hashCode的作用
详解Java中hashCode的作用 以下是关于HashCode的官方文档定义: hashcode方法返回该对象的哈希码值.支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表. hashCode 的常规协定是: 在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改.从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致. 如果根据