Базовые знания подобны фундаменту здания, они определяют нашу техническую высоту. Чтобы сделать что-то быстро, обязательным условием должно быть то, что базовые способности отличные, а «внутренняя сила» должна быть на месте. —— Красота структур данных и алгоритмов
Структуры данных и алгоритмы являются основой всех компьютерных языков и одной из важных переменных, определяющих, насколько далеко программист может зайти в программировании. Эта статья является кратким изложением статьи «Изучение структур данных и алгоритмов JavaScript» и посвящена тому, чтобы показать вам, что такое распространенные структуры данных и их реализации в js. Поэтому, хотя эта статья немного длинная, ее нетрудно понять.
Учитель Сяоган
Обозначение большого O
Нотация Big O означает нотацию сложности времени Big O, которая указывает на тенденцию изменения времени выполнения кода с ростом размера данных. Нотация Big O используется для грубой оценки эффективности выполнения алгоритма, поэтому нотация big O фокусируется только на коде с наибольшей величиной (обычно на коде с наибольшим количеством циклов).
- O(1): в коде нет операторов цикла и рекурсивных операторов, даже если есть тысячи строк, сложность также O(1);
- O(n): в коде есть операторы цикла и рекурсивные операторы, а именно:
const print = n => {
for (let i = 0; i< n; i++) {
console.log(i)
}
}
В этом методеprintметодforЦикл выполненияnраз, поэтому временная сложность равна O(n).
- O(logn): в коде есть цикл, но условие цикла:
const print = n => {
let i = 1
while (i <= n) {
i = i * 2
console.log(i)
}
}
Переменная условия цикла в кодеiУмножьте на 2 для каждой петли, когдаiЦикл завершается, когда оно больше 2. Таким образом, количество циклов кода равно x на следующем рисунке:
Подсчитано, что большинство людей забыли ряды пропорциональных чисел, которые они изучали в средней школе, и они забыли, что такое логарифмы.
В методе представления логарифмической временной сложности мы игнорируем «основание» логарифма и выражаем его единообразно какO(logn).
еслиprintметод выполняется в циклеnраз, то временная сложность равнаO(nlogn).
- O(m*n) и O(m+n): если в коде две петли, зацикливать отдельно
mвторой иnВторосортный. Если между этими двумя циклами есть гнездование, его сложностьO(m*n)Если нет вложенных отношений, их сложностьO(m+n).
множество
Массив представляет собой линейную структуру данных таблицы. Он использует набор смежных пространств памяти для хранения набора данных одного типа. —— Красота структур данных и алгоритмов
js изначально не имеет реального массива, потому что массив js может хранить разные типы данных, а пространство для хранения, необходимое для разных типов данных, разное, что делает невозможным, чтобы адреса памяти, используемые для хранения массива, были непрерывными. Поэтому массив js хранится в методе, похожем на хеш-карту, и операции чтения и записи массива таким образом относительно неэффективны.
Движок v8 оптимизирует массивы.Если все типы в массиве одинаковы, то в памяти создается непрерывное пространство для хранения массива. Но если в массив добавить другой тип, движок v8 перестроит массив по-старому, что будет менее эффективно.
Что нового в ES6ArrayBuffer, который может создать массив смежных пространств памяти. Очевидно, сквозьArrayBufferПросматривается созданный массив, что происходит быстрее.
Массив — очень важная структура данных в программировании, и большинство языков изначально реализуют структуру данных массива. Массив js является более гибким, и он нативно реализует многие методы работы с массивами, эти методы должны использоваться часто и должны быть хорошо знакомы.
В дополнение к методам, указанным в таблице выше, массивы имеют:Array.prototype.falt() Array.of() Array.form()и т.д., см.здесь.
структура данных стека
Стеки и очереди тоже по своей сути являются массивами, и это два специальных массива.
Стек — это упорядоченная коллекция в порядке поступления, например стек выполнения js.
Вновь добавленные элементы помещаются на вершину стека, а удаляемые элементы также должны быть удалены с вершины стека, как картридж только с одним портом:
Реализация стека
Автор книги использует es6WeakMapНапишите функцию стека:
По сути, использование экземпляраthisКак мост, чтобы получить стек.
let Stack = (function(){
let items = new WeakMap()
class Stack {
constructor () {
items.set(this, [])
}
pop () { // 出栈
return items.get(this).pop()
}
push (v) { // 入栈
items.get(this).push(v)
}
peek () { // 获取当前栈顶
return items.get(this)[items.get(this).length - 1]
}
size () { // 栈长度
return items.get(this).length
}
isEmpty () { // 栈是否为空
return items.get(this).length === 0
}
clear () { // 清空栈
items.get(this).length = 0
}
}
return Stack
})()
Давайте сначала представим es6WeakMap.WeakMapВ качестве имен ключей принимаются только типы объектов, а имена ключей являются слабыми ссылочными типами. Слабые ссылки — это тип, который легко восстанавливается механизмом сборки мусора, если механизм сборки мусора находит объект.только поссылается на слабый ссылочный тип, то объект будет переработан. в коде вышеthisсам по себе является сильным ссылочным типом, ноthisрассматривается какWeakMapИмя ключа слабой ссылки . Поэтому, когдаthisКогда экземпляр уничтожен,thisАдрес памяти объекта, на который первоначально указывалось, существует толькоWeakMapСлабая ссылка , поэтому,WeakMapСоответствующие пары ключ-значение будут уничтожены при запуске механизма сборки мусора.
До сих пор не понимаюWeakMapВзгляните на слабые ссылкиэта статья.
Эта функция стека используетсяWeakMapОтличный пример слабых ссылок:
Как показано на рисунке, переменнаяa、bСоздаются два экземпляра стека, и в каждый стек добавляется числовой элемент. Закрытие в это времяitemsЕсть два стека в . затем поместите переменнуюbустановить какnull, то переменнаяbСозданный объект экземпляра стека потерял свою сильную ссылку, оставив толькоWeakMapСлабая ссылка на имя ключа, но печатаетсяitemsВ стеке по-прежнему два, потому что механизм сборки мусора в это время не работает. Через десять секунд срабатывает механизм сборки мусора браузера Chrome, иitemsНедопустимый стек очищается, и в это время он распечатывается.itmesОстался только один стек. (P.S. После тестирования выяснилось, что текущая версия механизма сборки мусора движка V8 очищается не чаще, чем раз в десять секунд)
приложение стека
Преобразовать десятичное число в двоичное означает разделить десятичное число на 2, и каждый раз результат округлять в меньшую сторону и продолжать делить на 2, пока в результате не получится 0. Тогда обратный порядок массива, образованного результатом каждого деления, является двоичным результатом:
10 / 2 => 5...0
5 / 2 => 2...1
2 / 2 => 1...0
1 / 2 => 0...1
// 二进制转换最终结果为 1010
Ниже приведена реализация, которую нельзя использовать для преобразования в шестнадцатеричный формат, поскольку шестнадцатеричный содержит буквы:
function baseConverter(number, base = 2) {
let remStack = new Stack()
let baseResult = ''
while (number > 0) {
remStack.push(number % base) // 将除余结果存入执行栈中
number = Math.floor(number / base)
}
while (!remStack.isEmpty()) {
baseResult += remStack.pop() // 删除栈顶并存入字符串拼接
}
return baseResult
}
baseConverter(10, 2) // 1010
Выше приведено применение структуры данных стека. В нашем повседневном интерфейсном кодировании трудно встретить структуры данных, которые должны обрабатываться стеками, потому что в основном достаточно нативных массивов. Но если вы столкнулись со структурой данных, которая требует [первым поступил, первым обслужен] для строгости и демонстрации вашего профессионализма, пожалуйста, используйте очередь!
структура данных очереди
Структура данных очереди представляет собой упорядоченную коллекцию, которая следует в порядке очереди, например очередь задач js.
По сравнению с очередью стек подобен цилиндру только с одним портом, последний входит первым, а очередь подобна трубе с двумя портами, один конец которой входит, а другой — выходит.
Как следует из названия, очередь задач в js — это структура данных очереди.
А очереди в нашей повседневной жизни - это очереди.Те, кто впереди очереди, будут обслужены первыми, например, кассиры, туалеты и т.д.:
нормальная очередь
let Queue = (function() {
let items = new WeakMap()
class Queue {
constructor () {
items.set(this, [])
}
enqueue (v) { // 入列
items.get(this).push(v)
}
dequeue () { // 出列
return items.get(this).shift()
}
front () { // 获取当前队列首位
return items.get(this)[0]
}
size () { // 栈长度
return items.get(this).length
}
isEmpty () { // 栈是否为空
return items.get(this).length === 0
}
clear () { // 清空栈
items.get(this).length = 0
}
}
return Queue
})()
Метод реализации такой же, как и у структуры данных стека, но конкретный метод реализации отличается. Выталкивание стека - это массивpop, реализация удаления из очереди представляет собой массивshift.
приоритетная очередь
Очередь с приоритетом — это структура данных, которая ставится в очередь в соответствии с рангом. Например, обычные билеты в очереди в аэропорту ставятся в очередь за обычной очередью, вип-очереди ставятся в очередь за вип-очередью, а обычная очередь ставится в очередь за вип-очередью.
// 该例level越小等级越高：0 > 1 > 2
let PriorityQueue = (function() {
let items = new WeakMap()
let QueueElement = function (value, level) {
this.value = value
this.level = level
}
class PriorityQueue {
constructor () {
items.set(this, [])
}
enqueue (value, level) { // 入列
let queueElement = new QueueElement(value, level)
let arr = items.get(this)
let added = arr.some((item, index) => {
if (level < item.level) { // 如果要添加的元素的level低于item的，就添加到该节点之前
arr.splice(index, 0, queueElement)
return true
}
})
if (!added) arr.push(queueElement)
}
dequeue () { // 出列
return items.get(this).shift()
}
front () { // 获取当前队列首位
return items.get(this)[0]
}
size () { // 栈长度
return items.get(this).length
}
isEmpty () { // 栈是否为空
return items.get(this).length === 0
}
clear () { // 清空栈
items.get(this).length = 0
}
}
return Queue
})()
приложение очереди
Давайте воспользуемся общей очередью, чтобы реализовать игру с барабанным боем и передачей цветов. Передача цветов барабанным боем означает, что все образуют круг.В начале игры передайте цветы следующему человеку как можно скорее.В конце игры тот, у кого есть цветы, выбывает. Пока последний оставшийся не станет победителем.
function hotPotato (nameList) {
let queue = new Queue()
nameList.map(name => queue.enqueue(name))
return function (num) {
if (queue.isEmpty()) {
console.log('游戏已经结束')
return
}
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue())
}
let outer = queue.dequeue()
console.log(outer + '出局了')
if (queue.size() === 1) {
let winner = queue.dequeue()
queue = null // 让垃圾回收机制能自动清除弱引用内存
console.log(winner + '获胜')
return winner
} else {
return outer
}
}
}
let nameList = ['鼠', '牛', '虎', '兔', '龙', '蛇', '马', '羊', '猴', '鸡', '狗', '猪']
let game = hotPotato(nameList)
game(12) // 鼠出局了
game(22) // 牛出局了
...
game(32) // 龙获胜
Будь то стек или очередь, по сути это вариант использования массива. Благодаря инкапсуляции только тех методов, которые должны быть в структуре, гарантируется стабильность и безопасность структуры данных.
связанный список
Хотя массивы удобны для доступа к элементам, стоимость вставки или удаления элементов в начале и середине массива очень высока, поскольку массив хранится в непрерывном пространстве памяти, а вставка узла изменяет точку вставки и все последующие элементы. положение. Стоимость вставки элемента становится очевидной, когда в массиве достаточно элементов.
Одним из преимуществ связанных списков по сравнению с традиционными массивами является то, что элементы добавляются или удаляются без перемещения других элементов. Связанный список также представляет собой набор хранимых упорядоченных элементов, но элементы в связанном списке не размещаются в памяти последовательно, а имеют указатель на следующий соседний элемент. Поэтому, хотя вставка и удаление узлов в связанном списке выполняется быстро, запрос узлов выполняется очень медленно, поскольку запрос необходимо пройти от начала до конца. В массиве запросы к узлам выполняются быстро, а вставка и удаление узлов — медленнее.
Существует много типов связанных списков:
Односвязный список
Как следует из названия, односвязный список означает, что толькоnextнетprevСтруктура данных связанного списка. Односвязный список подробно реализован следующим образом:
const LinkedList = (function() {
const Node = function (element) { // 构造新节点
this.element = element
this.next = null
}
class LinkedList {
constructor () { // 初始化时候生成头节点 head 和链表长度 length
this.head = null
this.length = 0
}
append (element) { // 从尾部添加节点
let newNode = new Node(element)
if (!this.head) { // 没有头节点，就将新节点设为头节点
this.head = newNode
} else { // 存在头节点，就在链表尾部添加新节点
let current = this.head
while (current.next) { // 遍历找到链表尾部
current = current.next
}
current.next = newNode
}
this.length++
}
insert (position, element) { // 按位置插入节点
if (position < 0 || position > this.length) { // 边界判断
return false
}
let newNode = new Node(element)
if (position === 0) { // 往链表首部添加新节点
newNode.next = this.head
this.head = newNode
} else { // 非链表首部添加新节点
let index = 0, previous , current = this.head // index 索引判断是否是当前 position
while (index++ < position) { // 如果 index 小于 position，递增并将变量移动到下一个节点
previous = current
current = current.next
}
newNode.next = current
previous.next = newNode
}
this.length++
return true
}
removeAt (position) { // 按照位置删除节点
if (position < 0 || position > this.length) {
return null
}
let index = 0, previous , current = this.head
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
}
toString (symbol) { // 将链表的值字符串化
let current = this.head, str = ''
while (current) {
str += current.element
current = current.next
if (current) {
str += symbol ? symbol : ','
}
}
return str
}
indexOf (element) { // 找到值第一次出现的位置
let current = this.head, index = 0
while (current) {
if (current.element === element) {
return index
}
current = current.next
index++
}
return -1
}
find (element) { // 找到第一次出现该值的节点
let current = this.head
while (current) {
if (current.element === element) {
return current
}
current = current.next
}
return false
}
isEmpty () { // 判断链表是否为空
return this.length === 0
}
size () { // 返回链表长度
return this.length
}
getHead () { // 获取链表头节点
return this.head
}
}
return LinkedList
})()
Двусвязный список
В дополнение к узлу двустороннего связанного спискаnextуказать на следующий узел иprevуказывает на предыдущий узел. Преимущество двусвязного списка в том, что его можно повторять как от начала до конца, так и от конца к началу. Если вы хотите пройти от конца к началу при переходе от начала к концу в среднее положение, вы также можете это сделать.
Хотя двусвязный список занимает больше памяти, чем односвязный, самое большое преимущество двусвязного списка заключается в том, что при удалении заданного указателя ему не нужно снова перемещаться, чтобы найти его.prevУзел указывает на, поэтому временная сложность односвязного списка операции удаления в это время составляетO(n), временная сложность двусвязного списка равнаO(1).
const DoubleLinkedList = (function(){
let Node = function (element) {
this.element = element
this.prev = this.next = null
}
class DoubleLinkedList {
constructor () {
this.head = this.tail = null
this.length = 0
}
append (element) {
let newNode = new Node(element)
if (!this.head) {
this.head = this.tail = newNode
} else {
let current = this.head
while (current) {
current = current.next
}
current = this.tail
current.next = this.tail = newNode
newNode.prev = current
}
}
insert (position, element) {
if (position < 0 || position > this.length) {
return false
}
let newNode = new Node(element)
let previous, current = this.head, index = 0
if (position === 0) {
if (!this.head) {
this.head = this.tail = newNode
} else {
newNode.next = current
current.prev = newNode
this.head = newNode
}
} else if (position === this.length) {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
} else {
while (index++ < position) {
previous = current
current = newNode
}
previous.next = newNode
newNode.prev = previous
newNode.next = current
current.prev = newNode
}
this.length++
return true
}
removeAt (position) {
if (position < 0 || position >= this.length) {
return false
}
let previous, current = this.head, index = 0
if (position === 0) {
this.head = current.next
if (this.length === 1) {
this.tail = null // 若只有一项，则 current.next 为 null ，所以只需要将尾部设为 null
} else {
this.head.prev = null
}
} else if (position === this.length - 1) {
current = this.tail
this.tail = current.prev
this.tail.next = null
} else {
while (index++ < positon) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--
return current.element
}
// 删除指定节点
removeByNode (node) {
if (!node.prev) {
this.head = node.next
this.head.prev = null
return
}
if (!node.next) {
return
}
let prev = node.prev
let next = node.next
prev.next = next
next.prev = prev
}
// 其他方法实现和单向链表相同
}
return DoubleLinkedList
})
Круговой связанный список
Циклический связанный список означает, что между головой и хвостом связанного списка существует взаимная ссылка, образующая цикл.
Односторонний круговой связанный список:
Метод реализации односвязного списка почти такой же, как и у односвязного списка, но нужно обращать внимание на настройки при добавлении головных и хвостовых узлов.current.next = this.head, который здесь не повторяется из-за нехватки места.
Двусвязный список:
Метод реализации двусвязного списка аналогичен методу реализации двусвязного списка и здесь повторяться не будет.
Список Js не является структурой данных акустической реализации, по сравнению с массивом, связанный список в большей эффективности при добавлении и удалении элементов. Поэтому нужно добавлять и удалять большое количество элементов, лучший вариант — перечислить.
Коллекции и словари
Наборы и словари используются для хранения различных значений. Элементы в наборах и словарях могут быть любого типа.
собирать
Набор представляет собой структуру данных, состоящую из набора неупорядоченных и уникальных элементов.Поскольку нет повторений, ключом в наборе является значение.
Подобно множествам в математике, множества в js могут выполнять операции «объединения», «пересечения», «разности» и «подмножества».
Объединение — это сочетание элементов двух множеств, пересечение — это элементы, общие для обоих множеств, различие — это элементы, которых нет в другом множестве, а подмножество — это то, что элементы из a присутствуют в b.
Поскольку es6 изначально реализует коллекцииSetclass, поэтому мы можем воспользоваться преимуществами наследования вSetНа базе класса реализованы четыре операции коллекции:
class MySet extends Set {
constructor (...args) {
super(...args)
}
union (otherSet) { // 并集
return new MySet([...this, ...otherSet])
}
intersection (otherSet) { // 交集
// return new Set([...this].filter(x => otherSet.has(x))) // 标记 aa
let newSet = new MySet()
for (let a of this) {
if (otherSet.has(a)) {
newSet.add(a)
}
}
return newSet
}
difference (otherSet) { // 差集
// return new Set([...this].filter(x => !otherSet.has(x))) // 标记 bb
let newSet = new MySet()
for (let x of this) {
if (!otherSet.has(x)) {
newSet.add(x)
}
}
return newSet
}
isSubOf (otherSet) { // 子集
if (this.size > otherSet.size) {
return false
} else {
// return [...this].every(item => otherSet.has(item)) // 标记 cc
for (let x of this) {
if (!otherSet.has(item)) {
return false
}
}
return true
}
}
}
var a = new MySet([1, 2, 3, 4])
var b = new MySet([3, 4, 5, 6])
var c = new MySet([1,2])
a.intersection(b) // Set(2) {3, 4}
a.difference(b) // Set(2) {1, 2}
a.union(b) // Set(6) {1, 2, 3, 4, 5, 6}
c.isSubOf(a) // true
c.isSubOf(b) // false
«aa bb cc», отмеченный в приведенном выше коде, может выполнять свою функцию в одной строке кода, но его временная сложность составляет O (n²), по сравнению с временной сложностью кода под ним — O (n). потому что[...this]Сначала переместите все элементы коллекции в массив, а затем используйтеeveryПеребрать элементы в массиве.
Словарь
Как следует из названия, словарь — это структура данных для запроса значений на основе ключей, которые мы часто называем «парами ключ-значение».
Структура данных словаря реализована в es6 какMap.Mapа такжеObjectТо же самое состоит из пар ключ-значение, и ключ-значение не может повторяться. Но разница в томObjectключи могут быть только строками и неупорядочены; иMapКлючи могут быть значениями любого типа, включая объекты, и упорядочены.
let o = { 2: 2, 1: 1 }
Object.keys(o) // ['1', '2'] 键只能是无序的字符串
let map = new Map()
map.set(o, 1)
map.set(2, 2)
for (let key of map) console.log(key) // [{…}, 1] [2, 2] 键可以是任意类型，且根据添加的顺序遍历
Обратите внимание, что поскольку элементы в коллекциях и словарях могут быть любого типа, если вы добавите объект без ссылки, вы больше не сможете получить объект:
let a = new MySet()
a.add({})
a.has({}) // false
let b = new Map()
b.set({}, 1)
b.get({}) // undefined
WeakSet и WeakMap
В реализации стеков и очередей мы используемWeakMapкласс, на самом делеWeakMap WeakSetкласс почти иMap SetКлассы одинаковые, со следующими небольшими отличиями:
- В качестве ключей можно использовать только объекты
- ключи имеют слабый ссылочный тип
-
WeakMap WeakSetНет итератора, поэтому его нельзя вызватьkeys()、values()、entries()метод, ниsizeсвойства иclear()метод, существует не более четырех методов добавления, удаления, модификации и поиска.get()、set()、has()、delete()
WeakMap WeakSetФункция слабой ссылки упоминалась ранее, если вы все еще что-то не понимаете, обратитесь кздесь.
Дерево
Дерево представляет собой иерархическую модель абстракции данных и первую ненужечную структуру данных, представленную в этой статье.
Дерево состоит из «корневых узлов, дочерних узлов и конечных узлов». Корневой узел — это узел на вершине дерева, корневой узел не имеет родительского узла, узел с родительским узлом называется дочерним узлом, а узел без дочернего узла называется конечным узлом.
У дерева может быть много дочерних узлов.Наиболее часто используемое бинарное дерево может иметь не более двух дочерних узлов: левый дочерний узел и правый дочерний узел.
бинарное дерево поиска
Бинарное дерево поиска — это тип бинарного дерева, который позволяет хранить только значения, меньшие, чем родительский узел слева, и большие значения, чем родительский узел справа. Такое определение очень эффективно для поиска/вставки/удаления узлов из узлов дерева.
Давайте реализуем бинарное дерево поиска:
const BinarySearchTree = (function(){
const Node = function (key) {
this.key = key
this.left = null
this.right = null
}
const insertNode = function (node, newNode) { // 插入节点辅助函数
if (newNode.key < node.key) {
if (node.left) {
insertNode(node.left, newNode)
} else {
node.left = newNode
}
} else {
if (node.right) {
insertNode(node.right, newNode)
} else {
node.right = newNode
}
}
}
const searchNode = function (node, key) { // 搜索节点辅助函数
if (!node) {
return false
}
if (key < node.key) {
return searchNode(node.left, key)
} else if (key > node.key) {
return searchNode(node.right, key)
} else {
return true
}
}
const minNode = function (node) { // 找到最小节点并返回key
if (!node) {
return null
}
if (node.left) {
return minNode(node.left)
} else {
return node.key
}
}
const maxNode = function (node) { // 找到最大节点并返回key
if (!node) {
return null
}
if (node.right) {
return maxNode(node.right)
} else {
return node.key
}
}
const findMinNode = function (node) { // 找到最小节点并返回node对象
if (!node) {
return null
}
if (node.left) {
return findMinNode(node.left)
} else {
return node
}
}
const removeNode = function (node, key) { // 移除节点并返回传入的 node
if (node === null) {
return null
}
if (key < node.key) { // 这种情况需要更新node.left，然后返回更新了node.left的新的node
node.left = removeNode(node.left, key)
return node
} else if (key > node.key) { // 这种情况需要更新node.right，然后返回更新了node.right的新的node
node.right = removeNode(node.right, key)
return node
} else { // 这种情况需要更新node.key或者其他更新手段(包括直接将node变为null, 或更新node.right)，返回的也是更新后的node
// 情况1，被移除的是叶子节点
if (node.left === null && node.right === null) {
node = null
return node
}
// 情况2，被移除的是只有一个子节点的节点
if (node.left === null) { // 只有右子节点
node = node.right
return node
} else if (node.right === null) {//只有左子节点
node = node.left
return node
}
// 情况3，被移除的是有两个子节点的节点
const aux = findMinNode(node.right) // 找到子树中的最小节点，它肯定是一个叶子节点
node.key = aux.key // 将node的key设置为aux的key，达到删除效果，但此时有两个一样的key
node.right = removeNode(node.right, aux.key) // 移除以node.right为root的树上的重复的叶子节点aux.key
return node
}
}
class BinarySearchTree {
constructor () {
this.root = null
}
insert (key) { // 插入节点
let newNode = new Node(key)
if (!this.root) {
this.root = newNode
} else {
insertNode(this.root, newNode)
}
}
serach (key) { // 搜索节点，返回布尔值
return searchNode(this.root, key)
}
min () { // 最小节点
return minNode(this.root)
}
max () { // 最大节点
return maxNode(this.root)
}
remove (key) { // 删除节点
this.root = removeNode(this.root, key)
}
}
return BinarySearchTree
})()
Есть толькоremoveМетод сложнее, и узлы были удалены, могут быть «узлами листа», «только правильные детские узлы», «только левые детские узлы», «все левые и правые дочерние узлы» и т. Д.
первый,removeNodeМетод принимает два параметра, один из которых является удаляемым узлом.node(обратите внимание, что следующие узлы называются «узлами»), один из них — удаляемый узел.key, возвращает новое значение узла, в котором узел находится после удаления узлаnode. Почему вы хотите вернуться в узел, где вы находитесь? В js, если вы хотите удалить свойства объекта, вы должны иметь возможность получить композицию «объект + свойства»Referenceтипа, напримерdelete obj.nameсерединаobj + nameсформированныйReferenceТипы. в то время как параметр функцииnodeссылочный тип, переменная в теле функцииnodeСсылка на узел, где он находится, если только установитьnode = nullзатем просто поместите переменные в тело функцииnodeОсвобожден и не удаляет реальный узел. Если удаляемым узлом является этот узел, то должен быть найден родительский узел узла, который, очевидно, не может быть найден здесь. тогда что нам делать? Мы можем вернуть новый узел после удаления узла и назначить его старому узлу. Это хорошая идея, потому что для передачи параметров функции требуется меньше кода, а код более лаконичный и понятный.
Затем на основе вышеизложенного, если вы хотите удалить, это узел листьев, то узел назначен непосредственноnullИ вернуться к узлу, где он находится, если удаленный узел имеет толькоright, назначьте узелnode.rightИ вернуться к узлу, где он находится, достигается эффект удаления, если узел имеетleft right, затем поставьтеrightсамый маленький узел вkeyЗаменить на текущий узел и удалитьrightНаименьший узел в повторении, а затем вернуться к узлу;
В дополнение к добавлениям и удалениям, реализованным вышеприведенным кодом, бинарное дерево поиска также имеет важную функцию обхода. В соответствии с различным порядком обхода его можно разделить на обход в предварительном порядке (который сам по себе превосходит последовательный доступ к узлам-потомкам), обход по порядку (последовательный доступ от наименьшего к наибольшему узлу), обход по порядку. (сначала доступ к потомкам узла, а потом доступ к самому узлу)).
Предварительный обход бинарного дерева поиска: (self -> left -> right)
Код обхода предварительного заказа выглядит следующим образом:
const BinarySearchTree = (function(){
...
const preOrder = function (node, callback) {
if (node) {
callback(node.key)
preOrder(node.left, callback)
preOrder(node.right, callback)
}
}
...
class BinarySearchTree {
...
preOrderTraverse (callback) {
preOrder(this.root, callback)
}
...
}
return BinarySearchTree
})()
Неупорядоченный обход бинарного дерева поиска: (мин -> макс)
Код обхода по порядку выглядит следующим образом:
const BinarySearchTree = (function(){
...
const inOrder = function (node, callback) {
if (node) {
inOrder(node.left, callback)
callback(node.key)
inOrder(node.right, callback)
}
}
...
class BinarySearchTree {
...
inOrderTraverse (callback) {
inOrder(this.root, callback)
}
...
}
return BinarySearchTree
})()
Проверка почты двоичного поиска: (потомки -> сама)
Теверс после порядка следующий:
const BinarySearchTree = (function(){
...
const postOrder = function (node, callback) {
if (node) {
postOrder(node.left, callback)
postOrder(node.right, callback)
callback(node.key)
}
}
...
class BinarySearchTree {
...
postOrderTraverse (callback) {
postOrder(this.root, callback)
}
...
}
return BinarySearchTree
})()
Видно, что все три обхода используют рекурсию, единственное отличие состоит в том, что порядок вызова функции обратного вызова разный. обход предварительного заказаcallbackСначала вызов, обход по порядкуcallbackПромежуточный вызов, обход после заказаcallbackПоследний звонок.
В дополнение к бинарным деревьям поиска существуют также самобалансирующиеся деревья AVL, красно-черные книги, деревья с несколькими вилками и т. д., которые будут изучены позже.
картина
Граф — это абстрактная модель сетчатой структуры, состоящая из ребер и вершин. Для карты вершина — это локация, а ребро — это маршрут, соединяющий две локации, для WeChat QQ вершина — это пользователь, а ребро — это отношения между двумя пользователями, которые добавили друзей.
Графы делятся на ориентированные графы и неориентированные графы.Направленные графы являются однонаправленными, такими как Weibo fan и Weibo big V. Поклонники следуют за большим V, но большой V не следует за фанатами. Неориентированный граф означает, что между вершинами нет направления.Например, друзья WeChat являются неориентированными графами.
Один из способов хранения графиков«Матрица смежности». Матрица смежности представляет собой двумерный массив,A[i][j] === A[j][i].
Матрица смежности записывает взаимосвязь между всеми вершинами, но на самом деле между многими вершинами связи нет, и каждая из них приводит к пустой трате места для хранения. Но матрицы смежности эффективны для получения отношений между двумя вершинами.
Другой способ хранения графика«Список соседей». Каждая вершина в списке смежности соответствует связанному списку, указывающему на вершину, на которую указывает вершина. Таким образом, в таблице нет несвязанных вершин, что экономит место для хранения. Однако запрос соседних вершин занимает относительно много времени.
Суммировать
Эта статья застряла на несколько месяцев, и я хотел продолжить писать после углубленного изучения, но из-за корректировки личного плана обучения я больше не буду сосредотачиваться на изучении структуры и типов данных. Тем не менее, структуры данных и алгоритмы должны быть изучены.После того, как я узнаю то, что я хочу узнать, я продолжу усердно работать в этой области, и я буду обновлять новые главы, связанные со структурами данных и алгоритмами. Если у вас есть глубокий интерес к структурам данных и алгоритмам, вы можете купить курс «Красота структур данных и алгоритмов» на Geek Time, Я думаю, вы получите много пользы после его прочтения (многие картинки в тексте взяты из этого курс).