Category: дача

Category was added automatically. Read all entries about "дача".

Технотрек: Занятия 07, 08: Построить проект, вырастить дерево, родить левого или правого сына


(Копия блога на Технотреке)

Summary

Деревья - структуры данных, где мы совсем отказываемся от линейности, даже в логическом смысле. Для родительского узла дерева существует более одного "следующего" узла - например, левый и правый, называемых сыновними или дочерними узлами. Связь с родительским узлом у дочерних узлов может как быть, так и не быть; но с ней гораздо удобнее продвигаться от листьев дерева к его корню. Мы рассмотрели разные виды организации узлов деревьев и реализации связей между узлами.

Деревьев разного назначения и вида великое множество. В алгоритмических курсах часто рассматривают деревья поиска, хранящие данные и выдающие их как можно быстрее - то есть такие деревья представляют множества в их математическом смысле. Для этого им важно не содержать длинных путей от корня к листьям, и, если такой путь возникает, дерево перестраивается (балансируется) согласно различным алгоритмам. Структура связей такого дерева постоянно меняется, так как ее сохранение - не задача таких деревьев, главное, чтобы элементы искались максимально быстро.

Мы будем рассматривать такие деревья, в которых структура связей - важна. Роль таких деревьев - представлять взаимоотношения между объектами. Если у такого дерева меняются связи, то это должно быть следствием изменения таких отношений, и никак иначе. Поэтому понятие балансировки в таких деревьях бессмысленно, и если в них вдруг обнаружились длинные несбалансированные пути от корня - что ж, значит так построены взаимоотношения между объектами, которые это дерево отражает.

Для деревьев у нас будут три задачи, полторы из них рассматривались на прошедшей лекции: это экспертная система ("Акинатор") и убийца лаб по общефизу символьное дифференцирование.

Домашнее задание

Collapse )