АВЛ дерево: назначение, основные принципы.

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска.

Для КАЖДОЙ его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Г. Максимовича и Ландиса Е М. Записать

h = ln(n) + 1;

h - высота всего дерева;

n – число узлов.

Алгоритмы оптимизации АВЛ из тетрадки описать!

КЧ дерево: назначение, основные принципы.

“Высота левого поддерева ЛЮБОГО узла отличается не более чем на +/-1 от высоты правого поддерева".

Свойства

Пример красно-чёрного дерева

Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвет, принимающий значения красный или черный. В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:

Каждый узел-сосед старается иметь разный цвет. Каждый новый узел по-умолчанию изначально красного цвета, но при этом, цветами узлов оперируют следующие правила:

1. Узел либо красный, либо чёрный.

2. Корень — чёрный.

3. Все листья(NIL) — черные.

4. Оба потомка каждого красного узла — черные.

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

Эти ограничения реализуют критическое свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа (если дальний лист расположен на 3-м уровне). Результатом является то, что дерево примерно сбалансировано.

Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски (красная и чёрная)[1] и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом.

h = ln(n) + 1;

h - высота всего дерева;

n – число узлов.

 

ОПЕРАЦИИ УПРОЩЕНИЯ КАК И У АВЛ-ДЕРЕВА!!!

XML: основные задачи, назначение.

XML (eXtensible Markup Language) - это расширяемый язык разметки документа; он позволяет представлять в текстовом формате сложные, иерархические объекты.

Поэтому язык XML может применяться для решения нескольких задач:

· Обмен данными между разными программами.

· Обмен данными с удаленными филиалами организации.

· Обмен данными между разными организациями.

· Обмен данными между базой данных и Интернет-приложением.

Назначение:

Язык XML разработан под патронажем международной организации World Wide Web Consortium (W3C). Язык был создан специально для передачи структурированных данных. Изначально он задумывался как средство передачи данных в Интернет, которое в будущем должно заменить html. Однако область его применения стала значительно шире. И это не случайно. XML оказался настолько универсальным, простым и удобным языком, что его стали применять практически во всех областях информационных технологий, где требуется интеграция или взаимодействие различных приложений.

Новые версии броузеров и Интернет-серверов поддерживают язык XML. Если передавать в динамические страницы данные в этом формате, то скорость разработки Интернет-приложений, работающих с базами данных, значительно возрастает. Упрощается разработка и сопровождение этих приложений.

Однако, в формате XML можно передавать не только данные, но и метаданные - описание данных. Таким образом, можно передать, например, параметры отчета, которые необходимо заполнить в Интернет-приложении, чтобы затем получить сам отчет. Такая технология тоже облегчает программирование. Кроме того, метаданные - заказы на данные и команды на выполнение операций можно передавать от Интернет-приложения к базе данных.