Это третья из серии статей о реализации структур данных в JavaScript. Если вы новичок в структурах данных, обязательно начните сначала с Стеки.
Анализ
Двоичное дерево поиска (BST) - это древовидная структура данных на основе узлов, в которой каждый узел может иметь не более двух дочерних элементов. BST поддерживает несколько методов, общих для любого дерева поиска, таких как contains, insert и depthFirstLog, и delete. Мы поговорим об этом позже! Есть два основных способа представления BST. Я собираюсь сосредоточиться на методе с использованием узловых объектов, которые имеют ссылки на своих дочерних элементов.
Как следует из названия, BST - это просто двоичное дерево, только со следующими ограничениями, наложенными на то, куда могут идти узлы.
- Для каждого узла (node1) каждое значение, найденное в левом поддереве node1, меньше или равно значению, найденному в node1 .
- Для каждого узла (node1) каждое значение, найденное в правом поддереве node1, больше или равно значению, найденному в node1 .
Это не так сложно представить себе, но позвольте мне повторить. BST - это просто дерево, в котором каждый левый дочерний элемент имеет значение меньше родительского значения, а правый дочерний элемент имеет значение, которое больше или равно родительскому значению.
Методы
У BST есть четыре основных метода:
- insert (value): принимает значение и размещает в дереве в правильной позиции.
- содержит (значение): принимает значение и возвращает логическое значение, отражающее, содержится ли значение в дереве.
- depthFirstLog (обратный вызов): принимает обратный вызов и выполняет его для каждого значения, содержащегося в дереве.
и иногда содержит:
- delete (значение): принимает значение и удаляет это конкретное значение в BST.
Давайте углубимся в методы BST
Вставлять
Метод вставки выполняет двоичный поиск на корневом узле, перемещаясь к левому дочернему элементу, если n меньше текущего узла, или вправо, если n больше текущего узла. . Это продолжается до тех пор, пока левый или правый дочерний элемент не перестанет существовать, и именно сюда будет вставлен новый узел.
Содержит
Операция поиска выполняет двоичный поиск во многом аналогично операции вставки, чтобы определить, существует ли n.
Глубина первого журнала
Метод depthFirstLog принимает обратный вызов и применяет обратный вызов к каждому значению в BST. Это означает, что нам нужна (должна) рекурсия для обхода каждого BST, чтобы применить функцию обратного вызова к каждому узлу.
Если вы не чувствуете себя комфортно с рекурсией, я настоятельно рекомендую вам прочитать эту статью и ежедневно уделять время практике. Вы будете использовать рекурсию для решения сложных задач гораздо чаще, чем вы думаете!
Псевдокод
Псевдокод для этого очень сложный и подробный, так как я не хотел экономить на каждой строке, поэтому не торопитесь, чтобы медленно просмотреть каждую и понять, что происходит.
Create BST constructor
define value, right child and left child
Define insert method on prototype (value)
Create new node with passed in value
Create recursive function
If current node value > value && left child is undefined
Insert node as left child
If current node value > value
Recurse current node left child
If current node value <value && right child is undefined
Insert node as right child
If current node value <value
Recurse current node right child
Call recursive function on root node
Define contains method on prototype (value)
Create variable to hold found node
Create recursive function
If current node value is equal to value
Set variable equal to true
else if BST left child is !undefined && value < BST value
recurse with current node's left child
else if BST right child is !undefined && value > BST value
recurse with current node's right child
Call recursive function on root node
Return variable of found node
Define depthFirstLog method on prototype (callback)
Create recursive function
Use call with callback on BST and BST value
If left child is not undefined
Recurse through left child
If right child is not undefined
Recurse through right child
Call recursive function on root node
Сложность времени
Если вы мало знаете о временной сложности, потратьте немного времени и изучите основы, прежде чем двигаться дальше.
Методы в BST всегда начинаются с корневого узла и постепенно спускаются вниз, поэтому максимальное время, которое занимает каждая операция, зависит от высоты дерева. Например, для дерева с n узлами, у которого нет правильных дочерних элементов, потребуется O (n) времени, однако полный BST (каждый уровень, кроме последний полностью заполнен, с узлами на последнем как можно левее) имеет время наихудшего случая O (log n).
- delete: Linear - O (n) или O (log n) в среднем случае
- insert: Linear - O (n) или O (log n) в среднем случае
- содержит: Linear - O (n) или O (log n) в среднем случае
- depthFirstLog: Linear - O (n) или O (log n) в среднем случае
Код
Этот пост написал один из инструкторов Banyan Codecamp, нового учебного курса по программированию, разработанного с единственной целью: превратить начинающих программистов в способных инженеров под руководством старших инженеров. Получи высшее образование, сделай шестизначное число и учись на прекрасном острове Бали. Чтобы узнать больше, посетите www.codeinbali.com.
Вопросы на собеседовании о деревьях двоичного поиска
Будущие ответы :)
