Глава 10

10. 1 внутри( Элем, л( Элем)). % Элемент найден в листе
внутри( Элем, в2( Д1, М, Д2) ):-
                                                    % Вершина имеет два поддерева
    больше( М, Элем),  !,           % Вершина не во втором поддереве
    внутри( Элем, Д1);               % Поиск в первом поддереве
    внутри( Элем, Д2).               % Иначе - во втором поддереве
внутри( Элем, в3( Д1, М2, Д2, М3, Д3) ):-
                                                    % Вершина имеет три поддерева
    больше( М2, Элем),  !,
                % Элемент не во втором и не в третьем поддереве
    внутри( Элем, Д1);               % Поиск в первом поддереве
    больше( М3, Элем),  !,         % Элемент не в третьем поддереве
    внутри( Элем, Д2);               % Поиск во втором поддереве
    внутри( Элем, Д3).               % Поиск в третьем поддереве

10. 3 avl( Дер) :-
    аvl( Дер, Глуб).         % Дер является AVL-деревом глубины Глуб
avl( nil, 0).                     % Пустое дерево  -   AVL -дерево глубины 0
avl( д( Лев, Кор, Прав), Г) :-
    avl( Лев, ГЛ),
    avl( Прав, ГП),
    ( ГЛ is ГП; ГЛ is ГП + 1; ГЛ is ГП - 1),
                                    % Глубины поддеревьев примерно совпадают
        макс( ГЛ, ГП, Г).
макс1( U, V, М) :-                                     % М = 1 + макс( U, V)
    U > V,  !, М is U + 1;
    М is V + 1.