Упорядоченное множество — различия между версиями

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

Версия 01:22, 20 марта 2012

Определение

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

Операции над упорядоченным множеством

Над упорядоченным множеством [math]Set[/math] заданы следующие операции:

Search

Функция Search(Set, key), которая получает на вход искомый ключ [math]key[/math], и возвращает указатель на элемент множества [math]Set[/math] или специальное значение [math]null[/math], если такого элемента нет.

Minimum

Функция Minimum(Set) возвращает указатель на минимальный элемент множества [math]Set[/math].

Maximum

Функция Maximum(Set) возвращает указатель на максимальный элемент множества [math]Set[/math].

Predecessor

Функция Predecessor(Set, elem) возвращает указатель на элемент, стоящий перед элементом [math]elem[/math] множества [math]Set[/math].

Successor

Функция Successor(Set, elem) возвращает указатель на элемент, стоящий после элемента [math]elem[/math] множества [math]Set[/math].

Insert

Функция Insert(Set, elem, elem_key) добавляет заданный элемент [math]elem[/math], имеющий ключ [math]elem_key[/math], в подходящее место множества [math]Set[/math] (сохраняя свойство упорядоченности).

Delete

Функция Delete(Set, key) удаляет элемент, имеющий ключ [math]key[/math] (сохраняя свойство упорядоченности).

Пример упорядоченного множества:

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

Литература

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Упорядоченное_множество&oldid=19673»