Рефераты | Рефераты по информатике, программированию | Двоичные деревья поиска
Двоичные деревья поиска
Категория реферата: Рефераты по информатике, программированию
Теги реферата: отчет о прохождении практики, шпоры на экзамен
Добавил(а) на сайт: Dvoreckov.
Нередко алгоритмы, просто выглядящие на бумаге, становятся нагромождением сплошных конструкций if в реальной программе. Почему?
Ответ очевиден: многие алгоритмы для работы с деревьями предполагают, что
(NIL).parent == (NIL).left == (NIL).right == NIL. Вроде всё ясно и даже
логично, но ведь во многих языках программирования NIL/NULL – это ноль. А
обращение по нулевому адресу памяти чревато нехорошими вещами. Что же делать?
Ведь мало того, что все эти if тормозят программу, в них легко запутаться!
Решение просто: мы не будем использовать NIL! Действительно, алгоритмам
совершенно всё равно, какое численное значение имеет NIL, главное, чтобы адрес
любой реальной вершины в дереве не был ему равен. Поэтому вместо NIL мы будем
использовать адрес переменной, проинициализированной особым образом. Я покажу
это на языке С++, но думаю, этот пример можно будет перевести и на другие
языки, хотя там, скорее всего, нет шаблонов, и придется пожертвовать
типобезопасностью.