Prelude
This article is dedicated to binary search trees. Recently, I wrote an article about There, I didn’t pay much attention to binary trees, as the methods of searching, inserting, and deleting were not relevant. Now I’ve decided to write an article specifically about trees. Let’s begin.
A tree is a data structure consisting of nodes connected by edges. It can be said that a tree is a specific case of a graph. Here’s an example of a tree:
This is not a binary search tree! All details below!
Terminology
Root
The root of the tree is the topmost node. In the example, it’s node A. From the root to any other node, there can only be one path! In fact, any node can be considered as the root of the corresponding subtree. Parents/children
All nodes except the root have exactly one edge connecting them upward to another node. The node located above the current one is called the
parent of this node. The node located below the current one and connected to it is called a child of this node. Let’s take an example. If we take node B, then its parent will be node A, and its children will be nodes D, E, and F. Leaf
A node with no children will be called a leaf of the tree. In the example, the leaves will be nodes D, E, F, G, I, J, K.
This is the basic terminology. Other concepts will be discussed further. So, a binary tree is a tree in which each node has no more than two children. As you might have guessed, the tree in the example is not binary, as nodes B and H have more than two children. Here’s an example of a binary tree:
Any information can be contained in the nodes of the tree. A binary search tree is a binary tree with the following properties:
Both subtrees — left and right — are binary search trees.
- All nodes of the left subtree of any node X have data key values less than the key value of node X itself.
- All nodes of the right subtree of any node X have data key values greater than or equal to the key value of node X itself.
- Key
— some characteristic of the node (for example, a number). The key is needed to identify the element of the tree corresponding to this key. Example of a binary search tree: Tree representation
Tree representation
As we progress, I will provide some (possibly incomplete) snippets of code to enhance your understanding. The complete code will be at the end of the article.
A tree consists of nodes. The structure of a node:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//... other node methods
}
Each node has two descendants (it’s possible that the descendants leftChild and/or rightChild may have the value null). You probably understood that in this case, data refers to the information stored in the node, while key refers to the node's key.
Now that we've understood the node, let's talk about the pressing issues related to trees. Here and further, I will refer to the concept of a binary search tree when I say 'tree'. The structure of a binary tree:
public class BinaryTree<T> {
private Node<T> root;
// tree methods
}
As a class field, we only need the root of the tree, because from the root, using the methods getLeftChild() and getRightChild(), you can reach any node in the tree.
Algorithms in the tree
Search
Let's assume you have a constructed tree. How do you find the element with the key key? You need to move sequentially from the root down through the tree and compare the value key with the key of each node: if key is less than the key of the current node, move to the left child of the node; if it’s greater, move to the right; if the keys are equal, the desired node is found! The corresponding code:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
If current becomes equal to null, this means that the traversal has reached the end of the tree (at a conceptual level, you are in a nonexistent area of the tree — a child of a leaf).
Let's consider the efficiency of the search algorithm on a balanced tree (a tree in which nodes are distributed more or less evenly). Then the efficiency of the search will be O(log(n)), where the logarithm is base 2. Note: if there are n elements in a balanced tree, then this means that there will be log(n) base 2 levels of the tree. In the search, with each iteration of the loop, you descend one level.
Insertion
If you grasp the essence of the search, then understanding the insertion will not be difficult for you. You just need to go down to the leaf of the tree (following the descent rules outlined in the search) and become its descendant — left or right, depending on the key. Implementation:
public void insert(T insertData, int key) {
Node current = root;
Node parent;
Node newNode = new Node(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
In this case, it is necessary to store information about the parent of the current node, in addition to the current node itself. When current becomes null, the parent variable will hold the leaf we need.
The efficiency of insertion will obviously be the same as that of the search — O(log(n)).
Deletion
Deletion is the most complex operation that will need to be performed with the tree. It is clear that first we need to find the element we intend to delete. But what happens next? If we simply assign its reference a null value, we will lose information about the subtree whose root is this node. Deletion methods for trees can be divided into three cases.
First case. The node to be deleted has no descendants
If the node to be deleted has no descendants, this means that it is a leaf. Therefore, we can simply assign the leftChild or rightChild fields of its parent a null value.
Second case. The node to be deleted has one descendant
This case is not too difficult either. Let's return to our example. Suppose we need to delete the element with key 14. It is clear that since it is the right descendant of the node with key 10, any of its descendants (in this case, the right one) will have a key greater than 10, so we can easily 'cut' it from the tree, connecting its parent directly to the descendant of the deleted node, i.e., connecting the node with key 10 to the node 13. A similar situation would arise if we needed to delete a node that is the left descendant of its parent. Think about this yourself — it's an exact analogy.
Third case. The node has two descendants
The most complicated case. Let's examine it with a new example.
Searching for a successor
Suppose we need to remove a node with key 25. Who will take its place? Someone from its followers (descendants or descendants' descendants) should become the successor(the one who will occupy the place of the removed node).
How can we determine who should be the successor? Intuitively, it is clear that this is a node in the tree whose key is the next largest from the removed node. The algorithm is as follows. We need to move to its right descendant (always to the right, because it has already been mentioned that the successor's key is greater than the key of the removed node), and then follow the chain of left descendants of this right descendant. In our example, we should go to the node with key 35, and then walk down to the leaf along the chain of its left descendants — in this case, this chain consists only of the node with key 30. Strictly speaking, we are looking for the smallest node in the set of nodes greater than the sought node.
The code for the successor search method:
public Node getSuccessor(Node deleteNode) {
Node parentSuccessor = deleteNode; // parent of the successor
Node successor = deleteNode; // successor
Node current = successor.getRightChild(); // just a "running" node
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// at the end of the loop, we have the successor and its parent
if (successor != deleteNode.getRightChild()) { // if the successor does not match the right child of the removed node
parentSuccessor.setLeftChild(successor.getRightChild()); // then its parent takes the successor's child to not lose it
successor.setRightChild(deleteNode.getRightChild()); // link the successor to the right child of the removed node
}
return successor;
}
The complete code for the delete method:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // Depending on whether the deleted node is the left or right child of its parent, the boolean variable isLeftChild will take the value true or false accordingly.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) { // Case one
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) { // Case two
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else { // Case three
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
The complexity can be approximated to O(log(n)).
Finding the maximum/minimum in the tree
It is clear how to find the minimum/maximum value in the tree — you need to sequentially traverse the chain of left/right elements of the tree respectively; when you reach a leaf, it will be the minimum/maximum element.
public Node getMinimum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
The complexity is O(log(n))
Symmetrical traversal
Traversal — visiting each node of the tree to perform some action with it.
Algorithm for recursive symmetrical traversal:
- Perform the action with the left child
- Perform the action with itself
- Perform the action with the right child
Code:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " "); // You can put anything here
inOrder(current.getRightChild());
}
}
Conclusion
Finally! If I missed anything or you have any comments, I’m waiting for them in the comments section. As promised, here’s the complete code.
Node.java:
public class Node {
private T data;
private int key;
private Node leftChild;
private Node rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node newNode) {
leftChild = newNode;
}
public void setRightChild(Node newNode) {
rightChild = newNode;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
P.S.
Degenerating to O(n)
Many of you may have noticed: what if we make the tree unbalanced? For example, adding nodes with increasing keys: 1, 2, 3, 4, 5, 6… Then the tree would resemble a linked list. And yes, the tree will lose its tree structure, and consequently, its efficiency in data access. The complexity of search, insertion, and deletion operations will be like that of a linked list: O(n). This highlights, in my opinion, one of the major drawbacks of binary trees.
Only registered users can participate in the survey. , please.
I haven't been on Habr for long, and I would like to know what topics you would like to see more articles about?
Data Structures
Algorithms (DP, recursion, data compression, etc.)
Application of data structures and algorithms in real life
Programming Android applications in Java
Programming web applications in Java
2 users voted. 1 user abstained.
Source: habr.com
