В этой книге содержатся фундаментальные материалы, связанные с организацией, сортировкой и поиском данных в основной и внешней памяти. Соответствующие знания необходимы программистам всех уровней (от разработчиков простых прикладных программ до создателей сложнейших систем), квалифицированным пользователям программных продуктов, которые хотят хорошо понимать суть происходящего и, конечно, преподавателям разнообразных компьютерных дисциплин и их студентам.
Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями. Рис. 1 Бинарное дерево Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде.