Двоичное дерево поиска (сокращенно BST) — популярная концепция структуры данных. Это отсортированное двоичное дерево, в котором каждый из его внутренних узлов представляет такое значение, что левое поддерево узла — это дерево со значениями меньше, чем у узла, а правое поддерево — дерево со значениями больше, чем у узла. Каждый узел представляет собой объект, содержащий атрибуты left_subtree, value и right_subtree, где атрибуты left/right относятся к другим узлам. Узел BST по определению может иметь не более двух поддеревьев.
Такой способ упорядочения позволяет эффективно реализовать функцию этажа. пол (x) в математике/информатике — это понятие, которое "округляет" действительное число x в меньшую сторону, возвращая ближайшее целое число, меньшее или равное x. С упорядоченным деревом, таким как двоичное дерево поиска. , относительно легко пройти вниз по дереву, чтобы найти пол входа.
Предполагая, что BST имеет целочисленные значения, и для простоты ввод будет обозначаться как x. Общая идея состоит в том, чтобы сравнить текущий узел с x и решить, что делать. Поскольку дерево уже отсортировано, можно реализовать простой алгоритм:
››если x ‹ узла, то узел не может быть этажом(x). Следовательно, результат floor(x) будет в левом поддереве.
››если x == узла, то поздравляю, floor(x) вернет значение узла.
›› если узел x ›, то соответствующее значение floor(x) может быть* в правом поддереве. Если нет, то значение узла является результатом floor(x)
* Будьте осторожны с определением пола. Спуск вниз по правому дереву будет означать, что будут встречаться значения, превышающие значения узла, поэтому вполне возможно встретить только значения, превышающие сам x, в которых функция пола будет возвращать только значение, большее, чем сам ввод. Идите вниз по правому поддереву только в том случае, если существует значение y, в котором y больше, чем у текущего узла, и меньше, чем x. (подсказка: рассмотрите рекурсию!)
