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

This article mainly explains "how to use the balanced binary tree of Java". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to use the balanced binary tree of Java".

Possible problems of binary sort tree

Given a sequence of data {1, 2, 3, 4, 5, 6}, it is required to create a binary sort tree (BST) and analyze the problem.

Problem analysis:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

The left subtree is all empty, which is more like a single linked list in form.

Insertion speed has no effect.

The query speed slows down significantly (because a comparison is needed) and does not take advantage of BST. Because each time we have to compare the left subtree, its query speed is slower than that of a single linked list.

Solution-balanced binary Tree (ALV)

Basic introduction

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Balanced binary tree, also known as balanced binary search tree (Self-balancing binary search tree), also known as AVL tree, can ensure high query efficiency.

It has the following characteristics: it is an empty tree or the absolute value of the height difference between its left and right subtrees is not more than 1, and both left and right subtrees are a balanced binary tree. The common implementation methods of balanced binary tree are red-black tree, AVL, scapegoat tree, Treap, stretching tree and so on.

For example, the first two are balanced binary trees, the absolute value of the height difference of the first left and right subtree is 1, the absolute value of the height difference of the second left and right subtree is 0, and the absolute value of the height difference of the third left and right subtree is 2, so the third is not a balanced binary tree.

Left rotation of balanced binary tree

Steps:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Create a new node newNode with a value equal to that of the current root node.

Set the left subtree of the new node to the left subtree of the current node.

Sets the right subtree of the new node to the left subtree of the right subtree of the current node.

Change the value of the current node to the value of the current right child node.

Sets the right subtree of the current node to the right subtree of the right subtree.

Sets the left subtree of the current node to the new node.

Right rotation of balanced binary tree

Steps:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Create a new node with a value equal to the value of the current root node.

Set the right subtree of the new node to the right subtree of the current node.

Sets the left subtree of the new node to the right subtree of the left subtree of the current node.

Transplaces the value of the current node into the value of the left child node.

Sets the left subtree of the current node to the left subtree of the left subtree.

Sets the right subtree of the current node to the new node.

Double rotation of balanced binary tree

In some cases, a single rotation can not complete the transformation of the balanced binary tree, and two rotations are needed.

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

If the height of the left subtree of its right subtree is greater than that of the right subtree, the right subtree needs to be rotated right first, and then the current node needs to be rotated left.

If the right subtree height of its left subtree is greater than the left subtree height of its left subtree

The left subtree needs to be rotated left first, and then the current node needs to be rotated right.

Code case package com.xie.avl; public class AVLTreeDemo {public static void main (String [] args) {int [] arr = {4, 3, 6, 5, 7, 8}; AVLTree avlTree = new AVLTree (); for (int I = 0; I)

< arr.length; i++) { avlTree.add(new Node(arr[i])); } System.out.println("中序遍历"); avlTree.infixOrder(); System.out.println("在没有平衡处理前~~"); System.out.println("树的高度=" + avlTree.getRoot().height()); System.out.println("树的左子树的高度=" + avlTree.getRoot().leftHeight()); System.out.println("树的右子树的高度=" + avlTree.getRoot().rightHeight()); } } class AVLTree { private Node root; public Node getRoot() { return root; } public void setRoot(Node root) { this.root = root; } //查找要删除的节点的父节点 public Node searchParent(Node node) { if (root != null) { return root.searchParent(node); } else { return null; } } //查找要删除的节点 public Node search(int value) { if (root == null) { return null; } else { return root.search(value); } } /** * 找到以node 根的二叉排序树的最小值，并删除以node 为根节点的二叉排序树的最小节点 * * @param node 传入节点（当做二叉排序树的根节点) * @return 返回以node为根节点的二叉排序树的最小节点值 */ public int delRightTreeMin(Node node) { Node target = node; //循环查找左节点 while (target.left != null) { target = target.left; } //删除最小节点 delNode(target.value); return target.value; } /** * 找到以node 根的二叉排序树的最大值，并删除以node 为根节点的二叉排序树的最大节点 * * @param node 传入节点（当做二叉排序树的根节点) * @return 返回以node为根节点的二叉排序树的最大节点值 */ public int delLeftTreeMax(Node node) { Node target = node; while (target.right != null) { target = target.right; } //删除最大节点 delNode(target.value); return target.value; } //删除节点 public void delNode(int value) { if (root == null) { return; } else { Node targetNode = search(value); if (targetNode == null) { return; } if (targetNode == root) { root = null; return; } Node parentNode = searchParent(targetNode); if (targetNode.left == null && targetNode.right == null) { //如果要删除的节点是叶子节点 if (parentNode.left != null && parentNode.left.value == targetNode.value) { parentNode.left = null; } if (parentNode.right != null && parentNode.right.value == targetNode.value) { parentNode.right = null; } } else if (targetNode.left != null && targetNode.right != null) { //如果要删除的节点是有两个子树的节点 int minValue = delRightTreeMin(targetNode.right); targetNode.value = minValue; //上下代码删除效果一样 //int maxValue = delLeftTreeMax(targetNode.left); //targetNode.value = maxValue; } else { //要删除的节点是只有左子节点 if (targetNode.left != null) { if (parentNode != null) { if (parentNode.left == targetNode) { parentNode.left = targetNode.left; } else { parentNode.right = targetNode.left; } } else { //如果父节点是空，让root换位 root = targetNode.left; } } else {//要删除的节点是只有右子节点 if (parentNode != null) { if (parentNode.left == targetNode) { parentNode.left = targetNode.right; } else { parentNode.right = targetNode.right; } } else { //如果父节点是空，让root换位 root = targetNode.right; } } } } } //添加节点 public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } //中序遍历 public void infixOrder() { if (root != null) { root.infixOrder(); } else { System.out.println("二叉排序为空，不能遍历"); } } } class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } /** * 返回左子树的高度 * * @return */ public int leftHeight() { if (left == null) { return 0; } return left.height(); } /** * 返回右子树的高度 * * @return */ public int rightHeight() { if (this.right == null) { return 0; } return right.height(); } /** * 返回以该节点为根节点的树的高度 * * @return */ public int height() { return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1; } /** * 左旋转 */ public void leftRotate() { //创建新的节点，以当前根节点的值 Node newNode = new Node(value); //把新的节点的左子树设置为当前节点的左子树 newNode.left = left; //把新的右子树设置为当前节点的右子树的左子树 newNode.right = right.left; //把当前节点的值替换成右子节点的值 value = right.value; //把当前节点的右子树设置成当前节点的右子节点的右子树 right = right.right; //把当前的节点的左子节点(左子树),设置成新的节点 left = newNode; } /** * 右旋转 */ public void rightRotate() { //创建新的节点，以当前根节点的值 Node newNode = new Node(value); //把新的节点的右子树设置成当前节点的右子树 newNode.right = right; //把新的节点的左子树设置为当前节点左子树的右子树 newNode.left = left.right; //把当前节点的值换为左子节点的值 value = left.value; //把当前节点左子树设置成左子树的左子树 left = left.left; //把当前节点的右子树设置新节点 right = newNode; } /** * 查找要删除节点的父节点 * * @param node 要删除的节点 * @return 要删除节点的父节点 */ public Node searchParent(Node node) { //如果当前节点就是要删除节点的父节点就返回 if ((this.left != null && this.left.value == node.value) || (this.right != null && this.right.value == node.value)) { return this; } else { if (this.left != null && node.value < this.value) { //如果查找的节点的值小于当前节点的值，向左子树递归查找 return this.left.searchParent(node); } else if (this.right != null && value >

= this.value) {/ / if the value of the node you are looking for is less than that of the current node, recursively look for return this.right.searchParent (node) in the left subtree;} else {return null } / * find the node to delete * * @ param value the value of the node to be deleted * @ return deleted node * / public Node search (int value) {if (value = = this.value) {return this;} else if (value)

< this.value) { if (this.left != null) { return this.left.search(value); } else { return null; } } else { if (this.right != null) { return this.right.search(value); } else { return null; } } } //递归的形式添加节点，满足二叉排序树的要求 public void add(Node node) { if (node == null) { return; } if (node.value < this.value) { if (this.left == null) { this.left = node; } else { //递归向左子树添加 this.left.add(node); } } else { if (this.right == null) { this.right = node; } else { //递归向右子节点添加 this.right.add(node); } } //当添加完一个节点后，如果（右子树高度-左子树高度）>

1. Rotate if (rightHeight ()-leftHeight () > 1) {/ / if the height of the left subtree of its right subtree is greater than the height of the right subtree of its right subtree, you need to rotate the right subtree first, and then rotate the current node if (right! = null & right.leftHeight () > right.rightHeight ()) {right.rightRotate (). LeftRotate ();} else {/ / directly rotate the left to leftRotate ();} return } / / after adding a node, if (left subtree height-right subtree height) > 1, rotate if (leftHeight ()-rightHeight () > 1) {/ / if the right subtree height of its left subtree is greater than the left subtree height of its left subtree. The left subtree needs to be rotated left first, and then the current node needs to be rotated right if (left! = null & & left.rightHeight () > left.leftHeight ()) {left.leftRotate () RightRotate ();} else {/ / directly rotate to the right to rightRotate ();} / / traverse public void infixOrder () {if (this.left! = null) {this.left.infixOrder () } System.out.println (this); if (this.right! = null) {this.right.infixOrder ();} @ Override public String toString () {return "Node {" + "value=" + value +'}' }} Thank you for reading, the above is the content of "how to use the balanced binary tree of Java". After the study of this article, I believe you have a deeper understanding of how to use the balanced binary tree of Java, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.