Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to realize Java balanced binary tree". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to realize the Java balanced binary tree".

What is a binary search tree?

To put it simply, a binary tree that is convenient to search is a binary tree with a specific structure, that is, for node n, the values of all nodes in the left subtree are less than or equal to their values, and the values of all nodes in the right subtree are greater than or equal to their values.

Taking the sequence 2, 4, 1, 1, 3, 5, 10, 9, 8 as an example, if we build a tree with a binary search tree, the step by step we have established should be

Step one:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Step 8:

This is what the binary search tree generated according to the unbalanced common method looks like. In fact, the code is as follows:

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)

The last goal of the left-left type is that the second node becomes the root node and the first node becomes the right node of the second node.

So the pseudo code is used to show it (let a1magentin a2maga3 be the three nodes from top to bottom in the picture)

Right subtree of a2 = (merge (right subtree of a2, right subtree of A1) + A1 vertex value) to form a binary search tree

Return to a2

two。 Left and right type (a > 0 & & b = 2) {newRight = rotate (checkBalance (newRight) .childTree); countHeight (newRight);} searchTree.setRightChild (newRight); return searchTree;}

two。 Right-right rotation

/ * * right right * @ 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. Left and right rotation

/ * * around * * @ 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. Right and left rotation

/ * * right and left * * @ 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;}

Rotate the calling function:

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 left left searchTree = leftRotate1 (searchTree, searchTree.getLeftChild ());} else {/ / TODO: around 2022-1-13 searchTree = rightRotate2 (searchTree, searchTree.getLeftChild ()); searchTree = leftRotate1 (searchTree, searchTree.getLeftChild ()) }} else {if (c > 0) {/ / TODO: 2022-1-13 right and left searchTree = leftRotate2 (searchTree, searchTree.getRightChild ()); searchTree = rightRotate1 (searchTree, searchTree.getRightChild ());} else {/ / TODO: 2022-1-13 right searchTree = rightRotate1 (searchTree, searchTree.getRightChild ()) }} return searchTree;} overall code 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 means you are the root, 1 means childTree is the left subtree, 2 means childTree is the right subtree} 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 >

< 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 ("eventually\ n" + Json.toJson (searchTree));}}

Taking the sequence 2, 4, 1, 3, 5, 10, 9, 8, 6, 7 as an example, the balanced binary search tree structure is

{"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} so far I believe you have a deeper understanding of "how to achieve Java balanced binary tree". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.