Binary search (BST)

Поиск по массиву путем деления пополам.

Для таблицы символов (Object in JS) строим BST. BST:

• У каждой ноды слева все элементы, кт. меньше и справа все элементы кт. больше

• Может быть сбалансированным, когда одинаковое кол-во листьев

• Может быть средне сбалансированным, когда элементы добавляются произвольно

• Может максимально несбалансированным

Проблематика: может быть максимально несбалансированным, что в свою очередь устремляет добавление и поиск к O(N), вместо lgN. Соотв. сбалансированные деревья намного интереснее.