Writing in the front
This article focuses on common tree operations, such as find, add, delete, and so on. It is easier to understand through the way of GIFs.
Binary search tree
Binary search Tree (BST, Binary Sort Tree), also called Binary Sort Tree, or Binary search Tree. A binary search tree satisfies the following conditions:
- All values of the left subtree are less than the root node
- All values of the right subtree are greater than the root node
- The left and right subtrees also satisfy both of these
Colloquially, it’s a binary tree with nodes smaller on the left and larger on the right.
The insert
An insert operation on a binary lookup tree if the value x is inserted from the root node:
- If the value of x is less than the value of this node, continue in the left subtree
- If the value of x is greater than the value of this node, continue in the right subtree
- If the node is a leaf and the X value is less than the node value, insert the left child node, otherwise insert the right node
In the binary sort tree above, if we insert a node with a value of 80, we do the following:
Find operations
The search operation of a binary search tree if the search value x starts at the root node:
- If x is less than the root node, the search continues in the left subtree
- If x is greater than the root, the search continues in the right subtree
- If the value of x is equal to the root node, the node is returned
- If neither is found, null is returned
In the above binary sort tree, if we need to find the node whose node value is 10, the detailed operations are as follows:
Traverse the tree
There are three ways to traverse a tree. Preorder, inorder, and Postorder.
The former sequence traversal
In the sequence traversal
After the sequence traversal
Maximum and minimum
Minimum: The left child node of the root node is found, and the node with no left child node is the minimum node
Maximum: Find the right child node of the root node, and keep searching right until the node with no right child node is the smallest node
Delete operation
This node is a leaf node
If the node is a leaf node, delete it directly and set the reference from the parent node to the child node to NULL.
Delete a binary lookup tree if the value x to delete starts at the root node:
- If the value of the node is equal to x, it is deleted
- If the value of x is less than the value of this node, continue in the left subtree
- If the value of x is greater than the value of this node, continue in the right subtree
If we delete a node whose value is 80, we do the following:
This node has a child node
A node has a child node, divided into two cases, judge is the left child node or the right child node of the parent node, the reference of the parent node to the child node of the node (child node should also be divided into left and right child nodes, equivalent to a total of four cases)
Left left-left: the node to be deleted is left of the root node, the node to be deleted is left of its parent node, and the child node to be deleted is left child node
Left-right: The node to be deleted is left of the root node, right of its parent node, and the child node to be deleted is left child node
Right Right Right: The node to be deleted is to the right of the root node, the node to be deleted is to the right of its parent node, and the child node to be deleted is to the right child node
Left-right: The node to be deleted is to the right of the root node, the node to be deleted is to the left of its parent node, and the child node of the node to be deleted is the right child node
This node has two children
Due to the characteristics of binary search tree, the value of the left subtree of a node is guaranteed to be less than that of the node, and the value of the right subtree is guaranteed to be greater than that of the node. Only the maximum value in the left subtree or the minimum value in the right subtree (also known as the middle continuation node) can be found to replace the node, so as to ensure that the node will be a binary search tree after deletion.
The subsequent nodes
In a binary search tree, nodes are arranged in the way of small on the left and large on the right. For any node, the node whose value is higher than that of the node is its middle successor, or successor node for short. Since the left node is always smaller than the right node and its parent node, the successor node has no left child node and may have a right child node. By replacing the node with a successor node, the node can be guaranteed to remain a binary search tree after deletion.
There are two kinds of search methods
Use the maximum value in the left subtree
Use the minimum value of the right subtree (the successor node) to replace
Code implementation
public class BSTTree {
/**
* 节点
*/
public static class Node {
//数据，为简化代码，本程序默认节点里存储一个int变量，实际程序里可以存储自定义类型变量
int data;
//左子节点
Node leftChild;
//右子节点
Node rightChild;
public Node(int data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", leftChild=" + leftChild +
", rightChild=" + rightChild +
'}';
}
}
/**
* 新增节点 采用递归的方式
*
* @param root 根节点
* @param data 插入的数据
* @return
*/
public static Node insert(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
//若插入的数据小于根节点，插入到其左子树
if (data <= root.data) {
root.leftChild = insert(root.leftChild, data);
} else {
//插入到其右子树
root.rightChild = insert(root.rightChild, data);
}
return root;
}
/**
* 前序遍历
*
* @param root
*/
public static void preOrder(Node root) {
if (root != null) {
System.out.println(root.data + "->");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
}
/**
* 中序遍历
*
* @param root
*/
public static void inOrder(Node root) {
if (root != null) {
inOrder(root.leftChild);
System.out.print(root.data + "->");
inOrder(root.rightChild);
}
}
/**
* 后序遍历
*
* @param root
*/
public static void postOrder(Node root) {
if (root != null) {
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.print(root.data + "->");
}
}
/**
* 查找数据
*
* @param data
* @return
*/
public static Node find(Node root, int data) {
//若查找的数据小于根节点，则向左查找（也可以采用递归的方式查找）
Node current = root;
while (current != null) {
if (data < current.data) {
current = current.leftChild;
} else if (data > current.data) {
//向右查找
current = current.rightChild;
} else {
return current;
}
}
return null;
}
/**
* 最小值
*
* @param root
* @return
*/
public static Node minimum(Node root) {
if (root == null) {
return null;
}
while (root.leftChild != null) {
root = root.leftChild;
}
return root;
}
/**
* 最大值
*
* @param root
* @return
*/
public static Node maximum(Node root) {
if (root == null) {
return null;
}
while (root.rightChild != null) {
root = root.rightChild;
}
return root;
}
/**
* 删除节点
* 1.该节点是叶子节点，即没有子节点
* 2.该节点有一个子节点
* 3.该节点有两个子节点（通过该节点的中续后继节点来代替需要删除的节点，
* 因为后继节点比删除节点的右节点都小，比删除节点的左节点都大）
* 中续后继节点：比该节点值次高的节点为中续后继节点，如节点2的后继节点为3
* 4
* / \
* 2 6
* / \ / \
* 1 3 5 8
*
* @param root
* @param data 要删除的节点的值
*/
public static boolean delete(Node root, int data) {
//用来表示要删除节点的父节点
Node parent = null;
//需要删除的节点是否为父节点的左子节点
boolean ifLeftChild = true;
//需要删除的节点
Node current = root;
//定位删除节点的位置及其父节点
while (true) {
if (data == current.data) {
break;
} else if (data < current.data) {
ifLeftChild = true;
parent = current;
current = current.leftChild;
} else if (data > current.data) {
ifLeftChild = false;
parent = current;
current = current.rightChild;
}
//若找不到直接返回fasle
if (current == null) {
return false;
}
}
//1.该节点是叶子节点
if (current.leftChild == null && current.rightChild == null) {
//若为根节点,删除整棵树
if (current == root) {
root = null; //GC
}
//若为左子节点
if (ifLeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
}
//2.该节点有一个子节点
if (current.leftChild != null && current.rightChild == null) {//若删除节点的左子节点不为null
//如果该节点为根节点，将根节点的左子节点变为根节点
if (current == root) {
root = current.leftChild;
}
if (ifLeftChild) {
//左左左：若该节点为父节点的左子节点，则该节点的左子节点变为父节点的左子节点
parent.leftChild = current.leftChild;
} else {
//左右左：若该节点为父节点的左子节点，则该节点的左子节点变为父节点的右子节点
parent.rightChild = current.leftChild;
}
} else if (current.leftChild == null && current.rightChild != null) {
if (current == root) {
root = current.rightChild;
}
if (ifLeftChild) {
//右左右：若该节点为父节点的左子节点，则该节点的右子节点变为父节点的左子节点
parent.leftChild = current.rightChild;
} else {
//右右右：若该节点为父节点的右子节点，则该节点的右子节点变为父节点的右子节点
parent.rightChild = current.rightChild;
}
}
//3.该节点有两个子节点，这里通过后继节点的方式删除
if (current.leftChild != null && current.rightChild != null) {
//获取删除节点且重新构建的后继结点
Node successor = getSuccessor(current);
if (root == current) {
root = successor;
} else if (ifLeftChild) {
parent.leftChild = successor;
} else {
parent.rightChild = successor;
}
}
return true;
}
/**
* @param node 要删除的节点(假设此时该节点存在右子节点)
* @return 删除节点的后继节点
*/
public static Node getSuccessor(Node node) {
//node节点的左子节点
Node leftChild = node.leftChild;
//定义后继节点的父节点
Node successorParent = node;
//定义后继节点
Node successor = node;
//定义一个临时变量current，先获取删除节点的右子节点，然后再获取右子节点的最小值
Node current = node.rightChild;
//这一步就是查找删除节点的后继节点
while (current != null) {
//找到后继几点的父节点
successorParent = successor;
successor = current;
//获取右子节点的最小值,直左子树的左子节点为null说明该节点就是删除节点的右子节点的最小值
current = current.leftChild;
}
//找到后继节点之后重新构建后继节点树
if (current != node.rightChild) {
/* 后继节点的父节点的左子节点由原来的后继节点变为原来后继点的右子节点（因为左子节点的值始终小于父节点的值）
* 如下55若为后继节点提出去后，58就变为了60的左子节点
* 60 55
* / \ \
* 55 80 ---重新构建--- 60
* \ / \
* 58 58 80
*/
successorParent.leftChild = successor.rightChild;
successor.rightChild = node.rightChild;
successor.leftChild = leftChild;
}
return successor;
}
public static void main(String[] args) {
/*
* 新增操作
* 4
* / \
* 2 6
* / \ / \
* 1 3 5 8
* /
* 7
*/
Node root = null;
root = insert(root, 4);
root = insert(root, 2);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 6);
root = insert(root, 5);
root = insert(root, 8);
root = insert(root, 7);
// root = insert(root, 50);
// root = insert(root, 25);
// root = insert(root, 15);
// root = insert(root, 35);
// root = insert(root, 5);
// root = insert(root, 20);
// root = insert(root, 30);
// root = insert(root, 40);
//delete(root, 25);
inOrder(root);
// System.out.println("---------");
// //查找操作 4
// Node node = find(root, 4);
// printTree(node);
// System.out.println("---------");
// //删除操作
// Node delete = delete(root, 4);
// printTree(delete);
}
/**
* 打印
*
* @param root
*/
public static void printTree(Node root) {
System.out.println("根节点" + root.data);
if (root.leftChild != null) {
System.out.print("左子节点:");
printTree(root.leftChild);
}
if (root.rightChild != null) {
System.out.print("右子节点:");
printTree(root.rightChild);
}
}
}
Copy the codeBalanced binary tree (AVL)
A balanced binary tree (AVL) is a binary sorting tree in which the absolute value of the height difference (or balance factor, BF) between the left and right subtrees of any node is less than 1, and the left and right subtrees are also satisfied.
Why use balanced binary trees
Through the search operation of binary search tree, it can be found that the search efficiency of a binary search tree depends on the height of the tree. If the height of the tree is minimized, the search efficiency of the tree will be higher.
For example, the following binary tree is composed of all right subtrees
In this case, the binary tree is like a linked list, and the search time is O(n), while the search time of AVL tree is O(logn). We’ve seen before that order logn time is less than order n, as follows:
Reference: Time complexity of common data structures
Balance binary tree adjustment
An insert operation on a balanced binary tree has two results:
If the balance is not upset, i.e. BF=1 at any node, no adjustment is required
If the balance is broken, the node needs to be adjusted by rotation, and the node is unbalanced
An unbalanced binary tree can be rebalanced by the following adjustments:
Left-handed: take a node as the pivot (rotation node), its right child node becomes the parent of the rotation node, the left child node of the right child node becomes the right child node of the rotation node, and the left child node remains unchanged
Right-rotation: take a node as the pivot (rotation node), its left child node becomes the parent of the rotation node, the right child node of the left child node becomes the left child node of the rotation node, and the right child node remains unchanged
The unbalance adjustment is realized by rotating the minimum unbalance subtree:
When a new node is added to a balanced binary tree, the node whose absolute value of the first balanced factor exceeds 1 (BF>1) is the root subtree is called the least unbalanced subtree. In other words, if one tree is out of balance, many subtrees may be out of balance at the same time, and you only need to adjust the least unbalanced subtree.
It will be clear to go back and look at the least off-balance subtree rotation after looking at the rotation pattern below
LL rotation
Insert the new node into the left child (L) of the left subtree (L)
The inserted node is on the left side of the left subtree of the unbalanced node, and the balance can be reached after a right rotation, as follows
- Insert new node 5. The old root node 40 is out of balance
- The old root 40 is the right subtree of the new root 20
- The right subtree 30 of the new root 20 is the left subtree of the old root 40
Spinning process
The RR rotation
The inserted node is on the right side of the right subtree of the unbalanced node, and the balance can be reached after a left turn, as follows
- Insert new node 60 and old root node 20
- The old root 20 is the left subtree of the new root 40
- The left subtree 30 of the new root 40 is the right subtree of the old root 20
Spinning process
LR rotation
Insert the node to the right of the left subtree of the off-balance node, first left, then right, as follows
Spinning process
RL rotation
Insert the node to the left of the right subtree of the off-balance node, first right, then left, as follows
Spinning process
Code implementation
Public class AVLTree {public static class Node {int data; // Data Node leftChild; // Left child Node rightChild; // Right child int height; Public Node(int data) {this.data = data; Public static int getHeight(Node p){return p == null? -1 : p.height; Public static void main(String[] args) {Node root = null; root = insert(root,40); root = insert(root,20); root = insert(root,50); root = insert(root,10); root = insert(root,30); Root = insert(root,5); // Insert (root,5); PrintTree (root) printTree(root) printTree(root); } public static void printTree(Node root) { System.out.println(root.data); if(root.leftChild ! =null){ System.out.print("left:"); printTree(root.leftChild); } if(root.rightChild ! =null){ System.out.print("right:"); printTree(root.rightChild); Public static Node insert(Node root, int data) {if (root == null) {root = new Node(data); return root; } if (data <= root.data) {// insert into the left subtree root.leftChild = insert(root.leftChild, data); If (getHeight(root.leftChild) -getheight (root.rightChild) > 1) {if (data <= root.leftChild.data) {// System.out.println("LL rotation "); root = LLRotate(root); }else{// insert the node on the right side of the left subtree of the unbalance node system.out.println ("LR rotation "); root = LRRotate(root); RightChild = insert(root.rightChild, data); If (getHeight(root.rightChild) -getheight (root.leftChild) > 1){if(data <= Root.rightchild.data){// Insert the node to the left of the right subtree of the unbalanced node system.out.println ("RL rotation "); root = RLRotate(root); }else{system.out.println ("RR rotation "); Root = RRRotate(root); root = RRRotate(root); Height = math.max (getHeight(root.leftChild), getHeight(root.rightChild)) + 1; return root; } public static Node LRRotate(Node p){p.leftChild = RRRotate(p.leftChild); Return LLRotate(p); return LLRotate(p); Public static Node RLRotate(Node p){p.raychild = public static Node RLRotate(Node p){p.raychild = LLRotate(p.rightChild); Return RRRotate(p); return RRRotate(p); } /* * LL rotation * right-rotate (right-rotate node 20) * 40 20 * / \ / \ * 20 50 10 40 * / \ * 10 30 5 30 50 */ * 5 */ public static Node LLRotate(Node p){// 40 = Node lsubtree = p.leftChild; // the root of the left subtree is 20 as the new node p.leftChild = lsubtree.rightChild; // Make the right subtree of the new node 30 into the left subtree of the unbalance point 40 lsubtree. RightChild = p; Max (getHeight(p.leftChild), getHeight(p.rightChild)) + 1; Max (p.leftChild) + 1; lsubtree.height = Math.max(getHeight(lsubtree.leftChild), p.height) + 1; return lsubtree; // The new root node replaces the original imbalance point} /* * RR rotation * left rotation (left rotation of node 20) * 20 40 * / \ / \ * 10 40 20 50 * / \ \ * RR rotation / \ \ * 30 50 10 30 60 * \ * 60 */ public static Node RRRotate(Node p){// 20 = Node rsubtree = p.raychild; P.ightchild = rsubtree. LeftChild; // Make the left subtree of the new node 30 the right subtree of the imbalance point 20 rsubtree.leftChild = p; Max (getHeight(p.leftChild), getHeight(p.rightChild)) + 1; Max (p.leftChild) + 1; rsubtree.height = Math.max(getHeight(rsubtree.leftChild), getHeight(rsubtree.rightChild)) + 1; return rsubtree; // The new root node replaces the original imbalance point}}Copy the codeconclusion
Anyone who can see this, it’s tough. It’s not that hard, but just to understand the concepts of left-handed and right-handed, I think it’s pretty clear. This article also took me a whole day, and I basically studied it from 0 to 1. If you are interested, you can do more research.
Update record
| Modify the time | Modify the content |
|---|---|
| The 2021-7-20 | Binary sort tree delete operation (code logic error) |
| The 2021-7-21 | Left-handed and right-handed (wrong concept interpretation, fixed) |