Реализация двоичного дерева поиска в Javascript

В этой статье мы будем реализовывать структуру данных дерева двоичного поиска в Javascript. Дерево - это набор узлов, соединенных некоторыми ребрами. Дерево - это нелинейная структура данных. Дерево двоичного поиска - это двоичное дерево, в котором узлы с меньшим значением хранятся слева, а узлы с более высоким значением хранятся справа.
Теперь давайте посмотрим на пример узла дерева двоичного поиска:

Как и в приведенном выше фрагменте кода, мы определяем класс узла, имеющий три данных свойства, left и right , Left и right - указатели на левый и правый узел в дереве двоичного поиска. Данные инициализируются данными, которые передаются при создании объекта для этого узла, а для left и right установлено значение null.

Теперь давайте посмотрим на пример класса двоичного дерева поиска.

В приведенном выше примере показана структура класса дерева двоичного поиска, который содержит частную переменную root, которая содержит корень дерева, она инициализируется нулевым значением.
Теперь давайте реализуем каждую из этих функций:

1. insert (data) - вставляет новый узел в дерево со значением data

   // helper method which creates a new node to // be inserted and calls insertNode insert(data) { // Creating a node and initailising // with data var newNode = new Node(data); // root is null then node will // be added to the tree and made root. if ( this .root === null ) this .root = newNode; else // find the correct position in the // tree and add the node this .insertNode( this .root, newNode); } // Method to insert a node in a tree // it moves over the tree to find the location // to insert a node with a given data insertNode(node, newNode) { // if the data is less than the node // data move left of the tree if (newNode.data < node.data) { // if left is null insert node here if (node.left === null ) node.left = newNode; else // if left is not null recur until // null is found this .insertNode(node.left, newNode); } // if the data is more than the node // data move right of the tree else { // if right is null insert node here if (node.right === null ) node.right = newNode; else // if right is not null recur until // null is found this .insertNode(node.right,newNode); } }

   В приведенном выше коде у нас есть два метода insert (data) и insertNode (node, newNode) . Давайте разберемся с ними по порядку: -

   • insert (data) - он создает новый узел со значением data, если дерево пусто, он добавляет этот узел в дерево и делает его корнем, в противном случае он вызывает insert (node, data) .
   • insert (node, data) - он сравнивает заданные данные с данными текущего узла и перемещается влево или вправо соответственно и повторяется, пока не найдет правильный узел с нулевым значением, куда можно добавить новый узел.
2. remove (data) - эта функция удаляет узел с заданными данными.

   // helper method that calls the // removeNode with a given data remove(data) { // root is re-initialized with // root of a modified tree. this .root = this .removeNode( this .root, data); } // Method to remove node with a // given data // it recur over the tree to find the // data and removes it removeNode(node, key) { // if the root is null then tree is // empty if (node === null ) return null ; // if data to be delete is less than // roots data then move to left subtree else if (key < node.data) { node.left = this .removeNode(node.left, key); return node; } // if data to be delete is greater than // roots data then move to right subtree else if (key > node.data) { node.right = this .removeNode(node.right, key); return node; } // if data is similar to the root's data // then delete this node else { // deleting node with no children if (node.left === null && node.right === null ) { node = null ; return node; } // deleting node with one children if (node.left === null ) { node = node.right; return node; } else if (node.right === null ) { node = node.left; return node; } // Deleting node with two children // minumum node of the rigt subtree // is stored in aux var aux = this .findMinNode(node.right); node.data = aux.data; node.right = this .removeNode(node.right, aux.data); return node; } }

   В приведенном выше коде у нас есть два метода remove (данные) и removeNode (узел, данные) , давайте разберемся с ними один за другим:

   • remove (data) - это вспомогательные методы, которые вызывают removeNode, передавая корневой узел и заданные данные, и обновляют корень дерева значением, возвращаемым функцией.
   • removeNode (node, data) - ищет узел с заданными данными, а затем выполняет определенные шаги для его удаления.

   При удалении узла из дерева возможны три различных сценария: -

   • Удаление листового узла - поскольку листовой узел не имеет дочерних элементов, их можно легко удалить, и родительскому узлу возвращается null.
   • Удаление узла с одним дочерним элементом - если у узла есть левый дочерний элемент, мы обновляем указатель родительского узла на левый дочерний элемент удаляемого узла, и аналогично, если у узла есть правый дочерний элемент, мы обновляем указатель родительского узла. родительский узел справа от удаляемого узла
   • Удаление узла с двумя дочерними узлами - чтобы удалить узел с двумя дочерними элементами, мы находим узел с минимальным значением в его правом поддереве и заменяем этот узел узлом с минимальным значением и удаляем узел с минимальным значением из дерева.

   В приведенном выше коде мы использовали findMinNode (node) , он определен в разделе вспомогательного метода.
   Рекомендация: двоичное дерево поиска | Набор 2 (Удалить) Он содержит подробное объяснение и видеоурок по удалению узла из двоичного дерева поиска.

Обход дерева

Теперь давайте разберемся с различными способами обхода двоичного дерева поиска.

1. inorder (узел) - выполняет обход дерева в порядке, начиная с заданного узла
   Алгоритм для заказа:

   Пройдите по левому поддереву, т.е. выполните упорядочение по левому поддереву
    Посетите корень
    Пройдите по правому поддереву, т. Е. Выполните упорядочение по правому поддереву
   

   // Performs inorder traversal of a tree inorder(node) { if (node !== null ) { this .inorder(node.left); console.log(node.data); this .inorder(node.right); } }

2. preorder (узел) - выполняет предварительный обход дерева, начиная с заданного узла .
   Алгоритм предзаказа:

   Посетите корень
    Пройдите по левому поддереву, т.е. выполните предварительный заказ на левом поддереве
    Пройдите по правому поддереву, т.е. выполните предварительный заказ на правом поддереве
   

   // Performs preorder traversal of a tree preorder(node) { if (node !== null ) { console.log(node.data); this .preorder(node.left); this .preorder(node.right); } }

3. postorder (узел) - выполняет обратный обход дерева, начиная с заданного узла .
   Алгоритм постзаказов:

   Пройдите по левому поддереву, т.е. выполните поступорядочение на левом поддереве
    Пройдите по правому поддереву, т.е. выполните поступорядочение по правому поддереву
    Посетите корень
   

   // Performs postorder traversal of a tree postorder(node) { if (node !== null ) { this .postorder(node.left); this .postorder(node.right); console.log(node.data); } }

Вспомогательные методы

Объявим некоторый вспомогательный метод, который пригодится при работе с двоичным деревом поиска.

1. findMinNode (узел) - ищет узел с минимальным значением, начиная с узла .

   // finds the minimum node in tree // searching starts from given node findMinNode(node) { // if left of a node is null // then it must be minimum node if (node.left === null ) return node; else return this .findMinNode(node.left); }

   Как показано в приведенном выше методе, мы начинаем с узла и продолжаем двигаться к левому поддереву, пока не найдем узел, левый дочерний элемент которого равен нулю. Как только мы найдем такой узел, мы его вернем.

2. getRootNode () - возвращает корневой узел дерева.

   // returns root of the tree getRootNode() { return this .root; }

3. search (data) - ищет узел со значением data во всем дереве.

   // search for a node with given data search(node, data) { // if trees is empty return null if (node === null ) return null ; // if data is less than node's data // move left else if (data < node.data) return this .search(node.left, data); // if data is less than node's data // move left else if (data > node.data) return this .search(node.right, data); // if data is equal to the node data // return node else return node; }

Примечание. В соответствии с требованиями в классе BinarySearchTree можно объявить другой вспомогательный метод.
Реализация
Теперь давайте воспользуемся классом BinarySearchTree и его различными методами, описанными выше.

Дополнительные сведения о двоичных деревьях см. В следующей статье: Структура данных двоичного дерева

Эта статья предоставлена Сумитом Гошем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью с помощью provide.geeksforgeeks.org или отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.