Упорядоченное множество
Пример упорядоченного множества:
Сбалансированное дерево, т.е. то дерево, в котором высота его поддеревьев различается не более чем на 1.
Операции над упорядоченным множеством
Чтобы работать со множеством было проще - используют упорядоченное множество, где можно совершать следующие операции: Search(x) (поиск), Minimum (минимум), Maximum (максимум), Predecessor (предыдущий), Successor (следующий), Insert(x) (вставить), и Delete(x) (удалить).
Search
Функция поиска получает на вход искомый ключ , и возвращает указатель на элемент множества или специальное значение , если такого элемента нет.
Minimum
Функция Minimum возвращает указатель на минимальный элемент множества.
Maximum
Функция Maximum возвращает указатель на максимальный элемент множества.
Predecessor
Функция Predecessor возвращает указатель на предыдущий элемент множества.
Successor
Функция Successor возвращает указатель на следующий элемент множества.
Insert
Функция Insert(x) добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности).
Delete
Параметром функции Delete(x) удаления является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности).
Литература
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5
