Как искать значение в сбалансированном бинарном дереве?
Так же, как и в несбалансированном. Сбалансированность на стратегию поиска никак не влияет. Влияет логика построения дерева.
Чтобы создать из этого сбалансированное дерево я беру элементы с индексом floor(arr.length / 2)
С такой логикой элементы равные данному могут попасть как в левое поддерево, так и в правое. Чтобы найти их все нужно будет сканировать оба поддерева, если корень равен искомому числу.
Ну да я нашел первый на самом верху дерева, ну а потом? Левый узел меньше тройки а правая больше, но под правым узлом есть еще тройка. По какой логике надо искать ?
Если текущий корень больше искомого -- идти в левое поддерево, Если меньше -- идти в правое. Если равен -- то найдено, после чего идти в оба поддерева.
