Learning is endless, and you are encouraged.
Related series
- Data structure series (1) – Arrays
- Data structure series (2) – Linked lists
- Data structure series (3) – stack
- Data structure series (4) – Queues
- Data structure series (6) – Heap
What is a tree
A tree is a data structure consisting of nodes joined by edges. Each tree has N nodes and n-1 edges.
- Root: The nodes at the top of the tree are called roots;
- Path: The sequence of nodes traversed from one node to another is called a path;
- Parent node: a node other than the root node that points to itself is called its parent node (there is only one node);
- Child node: The node to which the current node points is called its child node (there can be more than one);
- Siblings: Siblings are siblings that have the same parent.
- Leaf node: the node without child node is called “leaf node”, referred to as “leaf node”.
- Subtree: Each node can be called the root of a subtree. It and the nodes below it form a subtree.
- Layer: the number of generations from the root node to this node;
Binary tree
A binary tree is a tree structure with a maximum of two subtrees per node. Subtrees are often referred to as “left subtrees” and “right subtrees” and are commonly used to implement binary query trees and binary heaps. Here we will focus on binary query trees;
Binary query tree
This article mainly explains the content of binary query tree, binary query tree has the following features:
- If the left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node.
- If the right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node.
- The left and right subtrees are binary query trees respectively.
- There are no nodes with equal keys;
Node information
In addition to data, a binary query tree node contains references to its left and right child nodes
private static class TreeNode<E> {
E data;
TreeNode<E> leftChild;
TreeNode<E> rightChild;
public TreeNode(E data, TreeNode<E> leftChild, TreeNode<E> rightChild) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
Copy the codeThe query
- In the while loop, the comparison starts at the root node and returns if the values are the same
- Those smaller than the contrast node are compared with the left child node of the contrast node;
- Those larger than the contrast node are compared with the right child node of the contrast node;
- If the child node does not exist, the query fails.
public TreeNode<E> find(E data) {
TreeNode<E> curNode = root;
int compareResult;
while (true) {
compareResult = data.compareTo(curNode.data);
if (compareResult == 0) {
break;
}
if (compareResult < 0) {
curNode = curNode.leftChild;
} else {
curNode = curNode.rightChild;
}
if (curNode == null) {
return null;
}
}
return curNode;
}
Copy the codeinsert
The newly inserted node is always a leaf node (there are no children), so just find the parent node to insert and point the left or right child of the parent node to the newly inserted node. If the current tree is empty, insert at the root node.
/ * *
* While loop to insert data,
* Better than recursion
* /
public void insert(E data) {
TreeNode<E> newNode = new TreeNode<>(data, null.null);
if (root == null) {
this.root = newNode;
return;
}
TreeNode<E> parentNode = root;
int compare;
while (true) {
compare = data.compareTo(parentNode.data);
/ / the left node
if (compare < 0) {
if (parentNode.leftChild == null) {
parentNode.leftChild = newNode;
return;
} else {
parentNode = parentNode.leftChild;
}
} else if (compare > 0) {
/ / right node
if (parentNode.rightChild == null) {
parentNode.rightChild = newNode;
return;
} else {
parentNode = parentNode.rightChild;
}
} else {
System.out.println(String.format("The same element [%s] already exists", data));
return;
}
}
}
Copy the codedelete
- The node to be deleted is first obtained
// Delete the parent node of the node
TreeNode<E> parentNode;
TreeNode<E> delNode = root;
// Whether the node to be deleted is a left child node
boolean isLeftNode = true;
int compareResult;
// Find the node to delete
while (true) {
parentNode = delNode;
compareResult = data.compareTo(delNode.data);
if (compareResult == 0) {
break;
}
if (compareResult < 0) {
isLeftNode = true;
delNode = delNode.leftChild;
} else {
isLeftNode = false;
delNode = delNode.rightChild;
}
if (delNode == null) {
System.out.println(String.format("Delete failed, no current data [%s]", data));
return false;
}
}
Copy the code- Delete leaf node (no child node)
If the root node is deleted, set the root node to NULL
Otherwise, set the left or right child node corresponding to the parent node to NULL
// Delete the leaf node
if (delNode.leftChild == null && delNode.rightChild == null) {
// Delete the root directory
if (delNode == root) {
this.root = null;
return true;
}
if (isLeftNode) {
parentNode.leftChild = null;
} else {
parentNode.rightChild = null;
}
}
Copy the code- The node to be deleted has a child node
If the root node is deleted, direct the root node to the child node of the deleted node.
Otherwise, the left or right child of the parent node of the deleted node points to the child node of the deleted node
// If there is only one child node, get the non-empty child node
TreeNode<E> childNode = delNode.leftChild == null ? delNode.rightChild:delNode.leftChild;
if (delNode == root) {
root = childNode;
} else {
if (isLeftNode) {
parentNode.leftChild = childNode;
} else {
parentNode.rightChild = childNode;
}
}
Copy the code- The node to be deleted has two child nodes
Generally, the position of the deleted node is replaced by the minimum worthy node of the right subtree of the deleted node, which is called the successor node.
If the successor node has a right child, the left child of the stepfather node points to the right child.
The left child of the successor node points to the left child of the deleted node.
// There are two child nodes, first get the successor node to replace the deleted node
TreeNode<E> successor = getSuccessor(delNode);
if (delNode == root) {
root = successor;
} else {
if (isLeftNode) {
parentNode.leftChild = successor;
} else {
parentNode.rightChild = successor;
}
}
/ * *
* @paramDelNode Specifies the element to delete
* @returnThe subsequent nodes
* /
private TreeNode<E> getSuccessor(TreeNode<E> delNode) {
// Subsequent nodes
TreeNode<E> successor = delNode;
// The parent of the successor node
TreeNode<E> successorParent = delNode;
TreeNode<E> curNode = delNode.rightChild;
while(curNode ! =null) {
successorParent = successor;
successor = curNode;
curNode = curNode.leftChild;
}
// The right node of the deleted node has a left child node
if(successor ! = delNode.rightChild) {
// Move up the right child of the next node
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
// The left child of the successor node points to the left child of the deleted node
successor.leftChild = delNode.leftChild;
return successor;
}
Copy the codePerformance optimization
When the inserted data is ordered, the resulting tree becomes a single-branch tree, with all nodes in a straight line and no branches, which is equivalent to a linked list (portal: linked list), and its time complexity becomes O(n). In view of this situation, we can use balance tree to deal with, such as ALV tree, red black tree.
Access to the source code
All the code in this series is uploaded to Github for easy access
>>>>>> Data structure – binary query tree <<<<<<
Daily for praise
Creation is not easy, if you feel helpful, please support
Please focus on
