Хеш-таблица. Что такое хеш-функция?

Как я уже сказал, можно думать о хеш-функции о черном ящике, который:

1. всегда принимает ключ (и текущую длину массива).
2. всегда возвращает индекс массива.

Не так важно, как он устроен. Важно, что это чистая функция с чётко определенной задачей.

Усвоив это, углубимся в реализацию.

Хеш-функции сравнивают по разным критериям, главными из которых я назвал бы:

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

Наименее качественная, но наиболее простая и наглядная реализация - арифметическая:

#h(key, tableLength) {
let ASCIICharKeysSum = 0;

for(let i = 0; i < key.length; i++) {
ASCIICharKeysSum += key[i].charCodeAt();
}

return ASCIICharKeysSum % tableLength;
}

Что здесь происходит?

Примем за условие, что ключи передаются строками или приравниваются к ним. Тогда строка:

- разбивается на символы
- возвращает свой индекс из ASCII-таблицы
- складывает индексы
- возвращает остаток от деления, который становится индексом массива.

Среди других реализаций есть криптографические, универсальные, с псевдослучайными числами и многие другие.

В следующем посте обсудим rehashing.

Хеш-таблица. Функция перераспределения, или rehashing.

Прежде чем разбираться, что такое рехешинг, ответим, зачем он нужен.

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

Rehashing решил эту проблему: в таблицах может храниться сколько угодно элементов - ценой сложности O(n).

Что, в сущности, такое рехешинг? Это просто создание нового массива, пересоздание хешей и перераспределение данных. Та же технология, что и в динамических массивах.

Но постойте, что значит сложность O(n)?! Где хваленый (O1)?

Не спешите ужасаться. Рехешинг выполняется редко. Например, если массив состоит из 32 элементов, а рехешинг увеличивает его каждый раз вдвое, выполнится он только 5 раз.

Вот реализация в моей хеш-таблице:

#allocateSpace() {
    const newTable = new Array(this.table.length * 2) // таблица при каждом вызове увеличивается вдвое
        .fill(null)
        .map(_ => new LinkedList()); // каждый бакет использует связанный список

    const bucketNodes = [];

    for(const bucket of this.table) {
        bucket.traverse((node) => { // метод traverse обходит связанный список, используемый в бакете
            if(node) bucketNodes.push(node.value);
        })
    }

    for(const node of bucketNodes) {
        const newHash = this.#h(node.key, newTable.length);
        newTable[newHash].append({
            key: node.key,
            value: node.value,
        });
    }

    this.table = newTable;
}

А в следующем посте поговорим про коллизии :)

Хеш-таблица. Коллизии.

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

Мы можем либо разрешить, либо запретить это.

- Стратегия "разрешить" называется "chaining".
- Стратегия "запретить" называется "открытая адресация".

Chaining: элементы массива хранят структуры данных, в которые при коллизии добавляются новые значения.
Достоинства чейнинга - в относительной простоте и избегании проблем, которые приносит стратегия "запретить".
Недостаток - в том, что, в худшем случае (если для всех ключей будет вычислен одинаковый хеш), сложность поиска и удаления станет O(n).
Для оптимизации поиска вместо простого связанного списке могут использоваться более сложные структуры данных, включая двоичные деревья. В связке с ними используют рехешинг.

Открытая адресация: один элемент массива хранит непосредственно одно значение.
Достоинства - в том, что такая реализация не требует дополнительных структур данных.
Недостаток вытекает из достоинства. Коллизии всё равно происходят, но просто добавить элементы в одну ячейку - нельзя.
Это решают поиском следующего свободного элемента.

Отсюда возникает следующая проблема: кластеры.
Что это такое? Представьте, что для двух десятков ключей хеш-функция вычислила только четыре хеша. Тогда в массиве возникнет четыре последовательных набора элементов, а остальные места в массиве остаются пустыми.
Борьба с кластерами - отдельная интересная тема. Все методы сводятся к тому, чтобы повысить вероятность равномерного заполнения таблицы. Например, используют две хеш-функции: одну для вычисления индекса, другую - для вычисления уникального множителя под этот индекс.

Исходя из этого, заключим, что операции вставки, удаления и поиска в хеш-таблице имеют амортизированную константную сложность. Это значит, что, несмотря на присутствие операций со сложностью O(n) или выше, обычно операции выполняются за O(1) или близкое к тому время.

Правильный ответ - 1.

Почему?

В коде используется оператор XOR - исключающее "ИЛИ". Как оно работает:

1 | 1 = 0
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

Этот оператор преобразует числа в 32-битное представление. Например, 0 - к 00000000 00000000 00000000 00000000.

В свою очередь, типы отсутствия, такие как null и undefined, приводятся к 0. Положительный булев тип приводится к единице.

Что же мы имеем?

1. undefined ^ null ^ 2 ^ true ^ 2
2. 0 ^ 0 ^ 2 ^ 1 ^ 2
3. Слева-направо:

1.

00000000 00000000 00000000 00000000
^
00000000 00000000 00000000 00000000
=
00000000 00000000 00000000 00000000

2.
00000000 00000000 00000000 00000000
^
00000000 00000000 00000000 00000010
=
00000000 00000000 00000000 00000010

3.
00000000 00000000 00000000 00000010
^
00000000 00000000 00000000 00000001
=
00000000 00000000 00000000 00000011

4.
00000000 00000000 00000000 00000011
^
00000000 00000000 00000000 00000010
=
00000000 00000000 00000000 00000001

Приведем результат последнего вычисления к десятичному формату - и получим 1.

Эврика!

Этот принцип лежит за решением задачи Leetcode по поиску единственного числа без дублей в массиве, или single number:
https://leetcode.com/problems/single-number/

Побитовые операции. База

- Все данные находятся в памяти в виде двоичного кода.
- Двоичный код - это совокупность битов.
- Биты измеряют в разных величинах: 8 бит - байт, 16 бит - машинное слово, 32 или 64 бита - слова для соответствующих процессоров, и так далее.
- Правые биты называются младшими. Левые - старшими.
- Самый старший бит указывает знак числа.
- Числа в JS представлены в виде 64 бит.

- Побитовые операции приводят числа к 32-битному формату.
- Чтение, переключение и установка битов - то, ради чего нужны побитовые операции.
- Самый частый паттерн работы с битами - маски. Маска - это второй операнд для побитовой операции.

Пример работы с маской. В битах программист может зашифровать булевы состояния. Например, три состояния (или 9 возможных комбинаций) в трёх младших битах:
"00000000000000000000000000000100"
"00000000000000000000000000000010"
"00000000000000000000000000000001"

Как прочитать текущее состояние? Через маску и оператор & (И).
"00000000000000000000000000000100" - текущее состояние.
"00000000000000000000000000000100" - маска для проверки третьего бита.
Применим &...
"00000000000000000000000000000100", так как 1 & 1 = 1.

Как установить состояние бита? Через маску и оператор | (ИЛИ).
"00000000000000000000000000000000" - текущее состояние.
"00000000000000000000000000000100" - маска для установки третьего бита.
Применим |...
"00000000000000000000000000000100", так как 0 | 1 = 1. Если бит в первом операнде будет 1, то результат все равно будет 1.

Как переключить состояние бита? Через маску и оператор ^ (Исключающее ИЛИ).
"00000000000000000000000000000000" - текущее состояние.
"00000000000000000000000000000100" - маска для переключения третьего бита.
Применим ^...
"00000000000000000000000000000100", так как 0 ^ 1 = 1. Если бит в первом операнде будет 1, то результат будет 0.

И наглядный экземпляр кода.

1. Функция проверки бита по динамической маске:

const readBit = (number, index) => {
return number & (1 << index);
}

Что здесь происходит?
1. Первый аргумент - это первый операнд в формате десятичного числа.
2. Второй аргумент - количество, на которое нужно сдвинуть бит в маске (изначально равной 1).
3. Вычисляется выражение в скобках. Происходит сдвиг по указанному индексу - например, бит передвигается на 9 позиций влево.
4. Операнды сравниваются.
5. Результат может быть 0 или 1.

Задачки на побитовые операции.
Попробуйте сами!

1. Напишите программу, вычисляющую заданную степень числа 2, используя битовые операции.
Условие: n < 31.
Как решать: вспомнить, как умножать побитовыми операциями, и что такое дополнительный код знака числа.
const foo = (n) => (2 << (n-1)) >>> 0;

2. Напишите программу, которая в заданном числе устанавливает определенный бит в 1 (биты при этом нумеруются с нуля, начиная от младших).
Как решать: вспомнить, какая операция нужна для установки бита в 1, и создать маску для такой операции.
const foo = (A, i) => {
const mask = 1 << i;
return A | mask;
}

3. Напишите программу, определяющую значение i-го бита числа.
Как решать: выполнить сдвиг А на значение i, чтобы искомый бит оказался на последнем месте, и вспомнить, какая операция нужна, чтобы прочесть состояние бита.
const foo = (A, i) => (A >> i) & 1

Leetcode. First Occurrence

Пока готовлю большой материал по бинарным деревьям, занимаюсь задачами с Leetcode. Работаю с методом двух указателей.

Сегодня решил задачу поиска первого совпадения в строке: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

Однако в первом решении обошелся одним указателем:

const strStr = (haystack, needle) => {
for(let i = needle.length-1; i <= haystack.length; i++) {
const currentSlice = haystack.slice(i-needle.length, i);
if(currentSlice === needle) {
return i-needle.length;
}
}

return -1;
};

Решить помогла другая задача:
https://leetcode.com/problems/remove-duplicates-from-sorted-array

Самое популярное решение создает "плавающее окно" между переменной i цикла for и i-1. Это окно движется по массиву, перемещая элементы. Тот же принцип я использовал и здесь. :)

В следующем посте опишу вариант честнее - без встроенных методов, более академический.

Leetcode. First Occurrence: Алгоритм Рабина-Карпа. Скользящая хеш-функция.

На собеседованиях цель не решить задачу хотя бы как-то, а:

1. Оптимально,
2. Осмысленно.

В случае поиска подстрок компании ожидают увидеть решение за О(n). С этой скоростью задачу решает алгоритм Рабина-Карпа. Это базовый алгоритм, на котором можно строить решения других подобных задач.

Этот алгоритм использует в работе хеш-функцию. Но не какую угодно, а скользящую! Одна из популярных и простых скользящих хеш-функций - полиномиальная.

Но что значит "скользящая" хеш-функция? В такой функции хэши не вычисляются на каждой итерации заново для каждой подстроки, а, используя хэш предыдущей подстроки, удаляется влияние предыдущего и добавляется следующий.

В наивном решении сложность возрастает до О(n * m), где n - длина строки, а m - длина искомой подстроки. Наивный алгоритм перебирает каждую подстроку, пока не найдет решение.

Алгоритм Рабина-Карпа не перебирает подстроки на каждой итерации, а сравнивает хэш искомой подстроки с хэшем новой, полученным на основе предыдущей. Только в случае совпадения алгоритм сравнивает строки перебором, чтобы удостовериться в результате. Таким образом добиваемся скорости O(n+m), или O(n).

Давайте напишем этот алгоритм...

Алгоритм Рабина-Карпа. Часть 1: полиномиальный хэш.

Для начала научимся писать полиномиальную хэш-функцию.

Из каких шагов состоит алгоритм?
1. Вычислить полином для строки.
2. Вернуть результат деления полинома по модулю.

Полином вычисляется по формуле:
P(x) = base * s[i]**1 + base * s[i]**2 + base * s[i]**3 (...)

Комбинация пунктов может выглядеть так:

/**
* Вычисляет полиномальный хеш
* @param str { string } - строка, для которой хеш вычисляется
* @param base { number } - основание для создания частей полинома
* @param mod { number } - модуль, остаток деления на который - искомый хеш
* @returns { number } полиномальный хеш
*/

const polynomialHash = (str, base = 256, mod = 101) => {
    let result = 0;

    for(let i = 0; i < str.length; i++) {
        const charPosition = str.codePointAt(i);
        let currentPart = charPosition * (base ** i);
        result += currentPart;
    }

    return result % mod;
}

В следующем посте напишем функцию рехешинга.

Алгоритм Кнута-Морриса-Пратта.

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

В поиске альтернативы узнал об алгоритме Кнута-Морриса-Пратта. И это было открытие! Алгоритм очень прост, логичен и популярен - ведь его сложность равна О(n + m), где n - длина текста, а m - длина искомой подстроки.

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

Как он работает? Давайте разбираться...

Алгоритм Кнута-Морриса-Пратта: префикс-функция

Заранее оговорюсь, что за полноценной теорией - не сюда, а в учебник. Здесь только практика и мои замечания.

В чем задача префикс-функции? Она подсчитывает префиксы строки. Точнее, части строки, которые являются её же суффиксами.

Например, в строке "abab" префиксо-суффиксы - это "ab".

Функция всегда принимает строку и возвращает массив (вектор, итератор...) чисел - тех самых префиксов. Этот массив используется в КМП для подсчета отступа, если найденное частичное вхождение строки прерывается.

И префикс-функцию, и использующий ее алгоритм КМП можно сделать через два указателя.

const prefix = (str) => {
    if(typeof str !== 'string') {
        throw new Error('В префикс-функцию переданы данные не строкового типа')
    }

    const prefixTable = Array(str.length).fill(0);
    let i = 1,
        j = 0;

    while(i < str.length) {
        while(j > 0 && str[i] !== str[j]) {
            j = prefixTable[j-1];
        }
        if(str[i] === str[j]) {
            j++;
        }
        prefixTable[i] = j;
        i++;
    }

    return prefixTable;
}

Алгоритм Кнута-Морриса-Пратта: тело алгоритма

Для меня удовольствие избегать циклов for. While подобен опасной бритве: ошибка в условии выхода из цикла - и программа сходит с ума в дурной бесконечности. Программист чувствует себя живым, как на штурме дворца Амина.

Но вернемся к алгоритму.

Как видите, во многом он похож на префикс-функцию. Тот же while для отката индекса j на каждом цикле, та же проверка на совпадение. Только индекс i указывает на символы текста, а j - на подстроку.

Всё гениальное - просто.

const KMP = (text, substr) => {
const pi = prefix(substr);

if(!pi) {
return null;
}

let j = 0;
let i = 0;

while(i < text.length) {
while(text[i] !== substr[j] && j > 0) {
j = pi[j - 1];
}

if(text[i] === substr[j]) {
j++;
}

if(j === substr.length) {
return i - j + 1;
}
i++;
}

return -1;
}

Про рекурсию

Много воды утекло с тех пор, как я переключился с деревьев на алгоритмы поиска подстрок. Многое забыл. Со вчерашнего вечера разбираю AVL-деревья: как увеличивать параметр высоты нод при добавлении новых и выполнять балансировку.

Вспомнил, что для вставки, удаления и поиска в сбалансированных деревьях идеально подходит рекурсия. Почему? Две причины: сложность основных операций - O(logN), а сущность операций - обход одинаковых нод. Балансировка и обработка высот выполняется уже после добавления ноды. В цикле это сложно сделать, а вот рекурсия каким-то образом "восходит" назад к корню.

И вот ночью мне снится сон про рекурсию. В котором увидел, что...

Рекурсивная функция может обрабатывать данные в обратном порядке!

Нужно только вызывать блок обработки данных после рекурсивного вызова.

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

Вот пример рекурсивного обхода массива с конца:

const rec = [0, 4, 8, 11, 14, 15, 17, 18, 20, 22]

const foo = (arr, index) => {
if(index === arr.length) {
return;
}
foo(arr, index+1);
console.log(arr[index])
}

foo(rec, 0)

В итоге я понял, почему рекурсия идеально подходит для деревьев - и как её особенности помогают в балансировке.

AVL-дерево. Начало.

Прежде чем погружаться в понятия и код, разберемся с базой: что это и зачем.

Всё начинается с графов. Ациклический граф, где каждую пару вершин связывает только один путь, - это дерево. Дерево, где у ноды может быть только два потомка, - это бинарное дерево. Вид бинарного дерева, в котором левый потомок всегда меньше правого, - это бинарное дерево поиска.

AVL-дерево, в свою очередь, - самобалансирующаяся разновидность бинарного дерева поиска.

Что это значит?

Это значит, что в AVL-дереве за гарантированное O(log N) выполняются:

- вставка
- удаление
- поиск.

Фантастические показатели! В AVL-дереве с ~1.000.000 элементов поиск будет выполнен, в худшем случае, за 20 операций. Гарантированно.

Обычное бинарное дерево поиска не похвастается такими показателями. Почему? Если последовательно добавлять элементы по возрастанию или убыванию, BST радостно выродится в связанный список.

Цена производительности - сложность. AVL-дерево сходу поймет далеко не каждый программист, а на доске напишет разве что человек дождя. Если данные нужно часто вставлять и удалять, то появляются дополнительные накладки на вращения. Эту проблему решают Красно-Чёрные деревья, более популярный вид сбалансированных структур.

В следующем посте я опишу основные сущности и операции, а после перейдем к коду.

#AVL #деревья #структурыДанных

AVL-дерево. Сущности и методы.

Элементарные и не очень составляющие структуры, такие как поля класса, я называю сущностями. Действия над ними - методами.

Сущности AVL-дерева, помимо типичных для BST:

- height: поле отдельно взятой ноды, описывающее количество нисходящих нод от неё до листа. По высоте root-ноды дерева определяется и высота дерева (а по высоте - N в log N). Используется для вычисления balance factor.
- balance factor: поле отдельно взятой ноды, описывающее разницу между высотами её правого и левого поддеревьев. Это как весы. Нормальный вес колеблется в пределах [-1, 0, 1]; показатели выше или ниже вызывают вращения дерева.

Методы AVL-дерева:

- обычные для BST операции вставки, удаления, поиска, получения минимального и максимального элементов. Вставка и удаление отличаются тем, что после рекурсивного вызова описаны действия над высотой и balance factor-ом, а также балансировка. Рекурсия помогает обойти дерево в высоту в обратном порядке: это ключ к пониманию балансировки деревьев. Обратный обход можно сделать и явно, с помощью итерации и стека, но я не вижу в этом смысла: код усложнится, а выигрыша по скорости нет.
- balance: метод, внутри которого вызываются вращения.
- setbalanceFactor: вычисляет показатель этого поля.
- setHeight: устанавливает изначальный показатель высоты ноды.
- updateHeight: обновляет высоту на основе высот потомков.
- rotate: вращают дерево. Бывают четырёх видов: влево, вправо, вправо-влево, влево-вправо.

В следующем посте покажу дерево, а после - подробно опишу методы.

#AVL #деревья #структурыДанных

AVL-дерево. Код

Прежде чем разбирать методы, посмотрим на готовое дерево:

class AVLNode {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.height = 1;
        this.balanceFactor = 0;
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }

    search(key) {
        const _search = (node, key) => {
            if(!node) {
                return null;
            }

            if(node.key === key) {
                return node;
            }

            if(key > node.key) {
                return _search(node.right, key);
            }

            return _search(node.left, key);
        }

        return _search(this.root, key);
    }

    /** обоабатывает случаи с null-нодами */
    getHeight(node) {
        return node ? node.height : 0;
    }

    setBalanceFactor(node) {
        node.balanceFactor = this.height(node.left) - this.height(node.right);
        return node;
    }

    /** Вычисляет высоту ноды на основе двух потомков  */
    updateHeight(node) {
        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    }

    rotateRight(x) {
        const y = x.left;
        const T2 = y.right;

        y.right = x;
        x.left = T2;

        this.updateHeight(x);
        this.updateHeight(y)

        return y;
    }

    rotateLeft(x) {
        const y = x.right;
        const T2 = y.left;

        y.left = x;
        x.right = T2;

        this.updateHeight(x);
        this.updateHeight(y)

        return y;
    }

    rotateRightLeft(x) {
        x.right = this.rotateRight(x.right)
        return this.rotateLeft(x);
    }

    rotateLeftRight(x) {
        x.left = this.rotateLeft(x.left)
        return this.rotateRight(x);
    }

    balance(node, key) {
        const balanceFactor = node.balanceFactor;

        if(balanceFactor < -1) {
            if(key > node.right.key) {
                return this.rotateLeft(node);
            }
            return this.rotateRightLeft(node);
        } else if(balanceFactor > 1 ) {
            if(key < node.left.key) {
                return this.rotateRight(node);
            }
            return this.rotateLeftRight(node);
        }

        return node;
    }


    add(key) {
        const _add = (node, key) => {
            if(node === null) {
                return new AVLNode(key);
            }

            if(node.key > key) {
                node.left = _add(node.left, key, node);
            } else if(node.key < key) {
                node.right = _add(node.right, key, node);
            }

            this.updateHeight(node);
            this.setBalanceFactor(node);

            return this.balance(node, key)
        }

        this.root = _add(this.root, key, null);
        return this;
    }

    delete(key) {
        const _delete = (node, key) => {
            if(!node) {
                return node;
            }

            if(node.key > key) {
                node.left = _delete(node.left, key)
            } else if(node.key < key) {
                node.right = _delete(node.right, key)
            } else {
                if(!node.left) {
                    return node.right;
                }
                if(!node.right) {
                    return node.left;
                }

                const theBiggerLeft = this.getMax(node.left);
                node.key = theBiggerLeft.key;
                node.left = _delete(node.left, theBiggerLeft.key)
            }

            this.updateHeight(node);
            this.setBalanceFactor(node);
            return this.balance(node);
        }

        this.root = _delete(this.root, key);
        return this;
    }

    getMin(node) {
        if(!node.left) {
            return node;
        }
        return this.getMin(node.left)
    }

    getMax(node) {
        if(!node.right) {
            return node;
        }
        return this.getMax(node.right)
    }
}

#AVL #деревья #структурыДанных

Leetcode: 2824. Count Pairs Whose Sum is Less than Target

Ссылка на задачу: https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/description/

Это одна из самых простых задач на работу с массивом. Решить можно двумя путями: за O(n^2) и за O(n log n). Наивный перебор первого пути описывать нет смысла, сразу перейду ко второму.

Он включает две стадии:

1. Сортировка массива.
Здесь бутылочное горлышко: общая сложность равна сложности сортировки. Разные методы работают лучше с определенными данными, важно уточнять вид данных. Я взял встроенный метод sort движка V8. В среднем он выполняется за O(n log n).

2. Обработка отсортированного массива.
Выполняется за O(n).
Логика второго шага:
- указатели двигаются навстречу и завершают цикл, когда их значения совпадают.
- на каждой итерации проверяем, выполняется ли условие.
- если условие выполняется, делаем вывод:
☝️условие также будет выполнять пара из элемента sortedArray[left] и любого другого элемента до right, включая и его самого.
тогда вычисляем, сколько всего элементов между left и right, включая right, и добавляем к итоговой сумме пар.
- иначе отбрасываем правый элемент.

Вот код решения:

const countPairs = (nums, target) => {
    const sorted = nums.sort((a, b) => a - b);
    
    let count = 0;
    let left = 0;
    let right = sorted.length - 1;

    while(left < right) {
        if(sorted[left] + sorted[right] < target) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }

    return count;
};

#leetcode #array #twoPointers

AVL-дерево. Методы, часть 1

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

- getHeight(node)
Возвращает либо значение height для текущей ноды, либо 0, если нода является листом (null).

- updateHeight(node)
Докидывает +1 к вершине ноды на пути обратной рекурсии.

- setBalanceFactor(node)
На основе вершин потомков вычисляет balanceFactor, по которому алгоритм определяет, нужно ли вращение. Возвращает ноду для удобства.

#AVL #деревья #структурыДанных

Leetcode: 2000. Reverse prefix.

Еще одна задача с простыми условиями. Смысл в том, чтобы найти префикс - кусочек строки до некоего символа - и развернуть его.

Простая задача, не так ли? Зачем же их решать?

Затем, чтобы тренировать насмотренность и алгоритмическое мышление. Они нужны, чтобы адекватно оценивать сложность задачи - и время на её выполнение. Программист либо решает задачи с нужной скоростью, либо пользуется харизмой для переноса сроков, но тогда зачем он работает программистом?..

Решение без встроенных методов может быть таким:

const reversePrefix = (word, ch) => {
    if(!ch) return word;
    
    for(let i = 0; i < word.length; i++) {
        if(word[i] === ch) {
            let j = i;
            let prefix = '';
            let suffix = '';
          
            while(j >= 0) {
                prefix += word[j];
                j--;
            }
          
            j = i + 1;
            while(j < word.length) {
                suffix += word[j];
                j++;
            }
          
            return `${prefix}${suffix}`
        }
    }
  
  return word;
}