Data Structures: Binary Tree in Java

Hi Hi! It's difficult to be a strong programmer without basic knowledge. And here we mean not only knowledge of the syntax of the native programming language, but also the fundamentals and concepts of programming in general. One of these foundations is algorithms and data structures. As a rule, some are more knowledgeable on this issue, some less, but there is some basic information that everyone should know. Among the databases for data structures, it is definitely worth understanding binary search trees. Actually, today we will look at the structure itself with its features and find out how you can implement a binary tree in Java . First, let's figure out what a binary tree is. A binary tree is a data structure in which each node (parent) has at most two children (right and left heir). In practice, two types of binary trees are commonly used - binary search tree and pyramid (heap). Today we will look at a binary search tree.

Benefits of Binary Tree

What is the advantage of storing data as a binary search tree? Imagine that we have a 100-page reference book and we need to find a specific page that will contain the data we need. We also know from the content which specific page we need. If we follow the usual path, we will have to turn over one page at a time until we get to the one we need. That is, we will go through from 1 to 100 pages until we find ourselves in the right place. For example, if we need page 77, then we will have 77 searches. If we talk about time complexity, then it will be O(N) . But this can be done more efficiently, right? Let's try to do the same thing, but using binary search :

1. We divide the directory into two parts, the first - from 1 to 50, the second - 51-100. We know exactly which of these parts our page is in: if we take page 77 again, it’s in the second part of the book.
2. Next, we consider the second part and divide it into two - from 51 to 75, from 76 to 100. In this case, our page will again be in the second half, in the range 76-100.
3. Next, we divide this interval by 2 and get 76-88 and 89-100. The page fits into the first gap, so we discard the second.
4. Next are the intervals: 76-81 and 82-88, take the first one.
5. 76-78 and 79-81, take the first one.
6. 76 and 77-78, take the second one.
7. 77 and 78, take the first one and get our page - 77.

Instead of 77 steps, we only needed 7! The time complexity of this search will be O(log(N)) .

Rules for constructing a binary search tree

The binary search tree is built according to certain rules:

• each node has at most two children;
• every value less than the node's value becomes the left child or the child of the left child;
• every value greater than or equal to the node's value becomes the right child or the child of the right child.

For example, we have a series of numbers from 1 to 10. Let's see what the binary search tree for this series will look like: Let's think about whether all the conditions of a binary tree are met here:

• all nodes have no more than two heirs, the first condition is met;
• if we consider, for example, a node with the value 7 (or any other), we will see that all the values ​​of the elements in the left subtree will be less, and in the right - more. This means that conditions 2 and 3 are met.

Let's look at how the basic operations occur - insertion, deletion, search.

Search for an element

When searching for an element with a given value, we start at the root element:

1. If it is equal to the sought value, the root element is the sought one; if not, we compare the values ​​of the root and the sought one.
2. If the element we are looking for is larger, we move to the right child; if not, we move to the left child.
3. If the element is not found, apply steps 1 and 2, but to the child (right or left) until the element is found.

For example, in the binary search tree shown above, we want to find the element with the value 5:

• we compare it with the root element, we see that the root element is larger, so we move to the left child, which has a value of 3;
• we compare the one we are looking for and the element with value 3, we see that the one we are looking for is larger, so we need the right descendant of the element in question, namely, the element with value 5;
• We compare this descendant with the one we are looking for and see that the values ​​are equal - the element is found.

Inserting an element

The insertion algorithm is also very, very simple:

1. We compare the new one with the root one (if it doesn’t exist, the new element is the root one).

2. If a new element:

   • is less, then we go to the left heir; if there is none, the new element takes the place of the left heir, and the algorithm is completed;
   • is greater than or equal to the root, then we move on to the right heir. And similarly, if this element does not exist, then a new element will take the place of the right element and the algorithm is completed.

3. For the new element in question, which was right or left from the previous step, repeat steps 1 and 2 until the inserted element is in place.

   As an example, we will want to insert into the tree considered above, an element with the value 11:

   • we compare with the root element 7 and see that the root element is smaller, so we move on to the right heir;
   • the next element under consideration has a value of 9, which is less than the new 11, so we move on to the right heir;
   • the right heir has a value of 10, which is again less, so we go to the first element, and since it is not there, a new element with a value of 11 is placed in this place.
   ↓

Removing an element

Perhaps, of all the operations with binary search trees, deletion is the most difficult. First of all, there is a search for the element to be deleted, after which a stage follows, which can have three variations:

1. The node to be deleted is a leaf node (has no children).

   Perhaps the simplest. It all comes down to the fact that we simply cut it off from the tree, without unnecessary manipulation. For example, from our tree we remove the node with the value 8:

   ↓

2. The node being deleted has one child.

   In this case, we delete the selected node and put its descendant in its place (in essence, we simply cut the selected node from the chain). As an example, let’s remove a node with value 9 from the tree:

   ↓

3. The node being deleted has two children.

   The most interesting part. After all, if the node being deleted has two children at once, you cannot simply replace it with one of these children (especially if the child has its own children).

   Example: In the tree above, which node should be the left child of node 3?

   If you think about it a little, it becomes obvious that this should be a node with a value of 4. But what if the tree is not so simple? If it holds hundreds of values, will it be that easy to figure out who the successor will be?

   It's clear that no. Therefore, we need our own small receiver search algorithm:

   1. First we must go to the right child of the selected node, whose value must be greater than the value of the node.
   2. Then we go to the left child of the right child (if one exists), then to the left child of the left child, etc., following down the chain of left children.
   3. Accordingly, the last left child on this path will be the successor of the original node.

   Let's generalize this little algorithm a little: in the subtree of the right child of the source node, all nodes are larger than the one being deleted, which can be understood from the basic rules of the binary search tree. In this subtree we are looking for the smallest value.

   In other words, we are looking for the smallest node in a set of nodes larger than the original node. This smallest node among the larger ones will be the most suitable successor.

   What the tree will look like after removing the node with value 3:

   ↓

Now it's time to move from practice to theory. Let's take a look at how we can map this data structure in Java. Single node class:

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет meaning :" + value);
   }

   public int getValue() {
       return this.value;
   }

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

Nothing too complicated: each element has a link to its left and right child. And now, perhaps, the most important class is the tree class:

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент or не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового element
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // or движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим meaningм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём How текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное meaning расстояния между elementми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков element
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его meaning в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего element
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между elementми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

Again, nothing too complicated. The binary search tree operations described earlier are present, plus a method for displaying the tree in the console. Well, now let's take a look at the tree in action:

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

Search/insert/delete operations in a binary search tree have time complexity of O(log(N)) . But that's the best case scenario. In general, the time complexity of operations ranges from O(log(N)) to O(N) . It depends on the degree of degeneracy of the tree.

What is a degenerate tree?

This is the tree in which the elements fell when added to the position of the leftmost node (smallest number) or the largestmost node (largest). This can happen if, for example, the entire left tree is empty at each level, there are only right trees, in which case the tree degenerates into a list (going to the right). Yes, this is how a degenerate tree effectively becomes a singly linked list, in which each element only knows about the one next to it. In this case, all operations on this structure approach the time complexity of O(N) .

In what case can a tree become degenerate?

For example, if you add a list of sorted elements. If the list is sorted in ascending order, then the root will be the first, respectively the smallest. The next one after him will take the position of the right child. And the one that comes after will be larger than the second and will take the position of its right successor, and so on... If the list is in descending order, then the same thing will happen, but with the leftmost elements. To avoid this, after receiving a number of elements, you can simply mix them. Then the sorting will disappear, and the numbers will be more or less evenly scattered throughout the tree. That's all for today, thank you for your attention!