Упорядоченное множество — различия между версиями
(→Пример упорядоченного множества:) |
Lirik (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
==Операции над упорядоченным множеством== | ==Операции над упорядоченным множеством== | ||
| − | Чтобы работать со множеством было проще - используют '''упорядоченное множество''', где можно совершать следующие операции: | + | Чтобы работать со множеством было проще - используют '''упорядоченное множество''', где можно совершать следующие операции: '''Search(x)''' (поиск), '''Minimum''' (минимум), '''Maximum''' (максимум), '''Predecessor''' (предыдущий), '''Successor''' (следующий), '''Insert(x)''' (вставить), и '''Delete(x)''' (удалить). |
=== Search === | === Search === | ||
| − | + | Функция поиска получает на вход искомый ключ <tex>x</tex>, и возвращает указатель на элемент множества или специальное значение <tex>NIL</tex>, если такого элемента нет. | |
=== Minimum === | === Minimum === | ||
| − | + | Функция '''Minimum''' возвращает указатель на минимальный элемент множества. | |
=== Maximum === | === Maximum === | ||
| − | + | Функция '''Maximum''' возвращает указатель на максимальный элемент множества. | |
=== Predecessor === | === Predecessor === | ||
| − | + | Функция '''Predecessor''' возвращает указатель на предыдущий элемент множества. | |
=== Successor === | === Successor === | ||
| − | + | Функция '''Successor''' возвращает указатель на следующий элемент множества. | |
=== Insert === | === Insert === | ||
| − | + | Функция '''Insert(x)''' добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности). | |
=== Delete === | === Delete === | ||
| − | Параметром | + | Параметром функции '''Delete(x)''' удаления является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности). |
== Литература == | == Литература == | ||
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5 | 1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5 | ||
Версия 23:52, 19 марта 2012
Содержание
Пример упорядоченного множества:
Сбалансированное дерево, т.е. то дерево, в котором высота его поддеревьев различается не более чем на 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
