Как искать значение в сбалансированном бинарном дереве?

Question

[lightseeker]

Есть массив [1,2,3,3,4].
Чтобы создать из этого сбалансированное дерево я беру элементы с индексом floor(arr.length / 2). И того получается следующее



Теперь надо искать элементы через совпадение ( нужно найти все соответствующие ).
Как это сделать в данном конкретном случае? Или может я неправильно создал дерево?

Comments

[Модератор]

Не надо ставить как можно больше тэгов. Лучше оставить один, но конкретный, с которым проблема.
См.п.3.1 Регламента. Также обратите внимание на п.3.4

Answer 1

[jcmvbkbc]

Как искать значение в сбалансированном бинарном дереве?

Так же, как и в несбалансированном. Сбалансированность на стратегию поиска никак не влияет. Влияет логика построения дерева.

Чтобы создать из этого сбалансированное дерево я беру элементы с индексом floor(arr.length / 2)

С такой логикой элементы равные данному могут попасть как в левое поддерево, так и в правое. Чтобы найти их все нужно будет сканировать оба поддерева, если корень равен искомому числу.

Ну да я нашел первый на самом верху дерева, ну а потом? Левый узел меньше тройки а правая больше, но под правым узлом есть еще тройка. По какой логике надо искать ?

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

Comments

[lightseeker]

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

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

[jcmvbkbc]

до какой глубины нужно искать по этой логике

До дна же. Представь себе, что дерево построено из массива в котором одни тройки.

[GavriKos]

lightseeker,

В общем, если в кратце, то вопрос такой - если найден первое совпадение, нужно ли сканировать всю информацию

Так это напрямую зависит от задачи. Что за поиск?
"Есть ли вообще такой элемент?", "Сколько таких элементов?", "позиции элементов?" (да, дерево не то чтобы индексируемое, но все же). А если это не просто значения а например КЛЮЧИ - то там еще пачка вопросв.

Если просто узнать наличие элемента то очевидно что после первого нахождения можно остановиться.

Answer 2

[GavriKos]

Бинарным поиском.

Comments

[lightseeker]

Можно подробнее пожалуйста?
Меня интересует конкретно поиск тройки здесь.
Ну да я нашел первый на самом верху дерева, ну а потом? Левый узел меньше тройки а правая больше, но под правым узлом есть еще тройка. По какой логике надо искать ?

[GavriKos]

lightseeker, А не должно ее быть там. Как она туда попала?

[lightseeker]

GavriKos, так у меня же массив вот такой [1,2,3,3,4]. И после создания дерева получается как на картинке.

[GavriKos]

lightseeker, есть разные варианты решения дубликатов. Например, хранить количество дубликатов в листьях.

[lightseeker]

GavriKos, можете скинуть годный материал для обучения?

[GavriKos]

lightseeker, да тупо гуглите. Прям вот "бинарное дерево дубликаты"

[lightseeker]

GavriKos, гуглил много раз, но мало полезного. В основном варианты с удобными данными, так, что эти корнер кейсы никак не освещаются. Но буду и дальше искать.
Спасибо большое !

[GavriKos]

lightseeker, да ладно
https://translated.turbopages.org/proxy_u/en-ru.ru...

[res2001]

lightseeker,

По какой логике надо искать ?

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

Answer 3

[Alexandroppolus]

Насколько я понял, дерево строится по отсортированному массиву однократно и потом не меняется. Если это так, то тебе вообще не надо его строить, а бинарный поиск делать по массиву

Answer 4

[mayton2019]

Есть массив [1,2,3,3,4].
Нет. Нет. Все не так. Бинарное дерево строится на основе любых произвольных массивов.
Не обязательно сортированных. То что ты привел это какой-то частный случай чтоб облегчить себе
жизнь. И непонятно зачем мы здесь будем обсуждать частный случай.

Вот попробуй построить дерево из
[5,1,3,2,4].

Comments

[lightseeker]

Речь же про сбалансированное бинарное дерево, а не бинарное дерево в целом

[mayton2019]

lightseeker, долго-же ты думал. 4 дня.

А по другому дерево никак не сбалансировать? Лишь только сортировкой массива?

[lightseeker]

mayton2019, зачем так агрессивно, я же просто здесь задал вопрос по теме в котором далеко не эксперт.
Насчет сортировки, ну раж уж Вы меня спрашиваете, полагаю есть вариант(ы).
Спасибо за подсказку и ответ друг

[mayton2019]

lightseeker, уверяю тебя я всегда так разговариваю. Почитай википедию по ключевым словам таким как Двоичное дерево поиска BST, АВЛ-дерево и Красно-черное дерево (R&B)