Доказательство асимптотических границ
Красно-чёрное дерево, которое содержит n внутренних узлов, имеет высоту O ( l o g ( n ) ) {\displaystyle O(log(n))} O(log(n)).
Обозначения:
h ( v ) {\displaystyle h(v)} {\displaystyle h(v)} — высота поддерева с корнем в v {\displaystyle v} v
b h ( v ) {\displaystylebh(v)} {\displaystylebh(v)} — число чёрных узлов (не считая v {\displaystyle v} v, если он чёрный) от v {\displaystyle v} v до любого листа в поддереве (называемое чёрной высотой)
Лемма: Поддерево с корнем в узле v {\displaystyle v} v имеет не менее 2 b h ( v ) − 1 {\displaystyle 2^{bh(v)}-1} {\displaystyle 2^{bh(v)}-1} внутренних узлов.
Доказательство леммы (индукцией по высоте):
Основание индукции: h ( v ) = 0 {\displaystyle h(v)=0} {\displaystyle h(v)=0}.
Если поддерево имеет нулевую высоту, то v {\displaystyle v} v должен быть null, поэтому b h ( ″ v ″ ) = 0 {\displaystylebh(''v'')=0} {\displaystylebh(''v'')=0}.
Итак:
2 b h ( v ) − 1 = 2 0 − 1 = 1 − 1 = 0 {\displaystyle 2^{bh(v)}-1=2^{0}-1=1-1=0} {\displaystyle 2^{bh(v)}-1=2^{0}-1=1-1=0}
Индукционный шаг: пусть узел v {\displaystyle v} v такой, что h ( v ) = k {\displaystyle h(v)=k} {\displaystyle h(v)=k} и поддерево имеет не менее 2 b h ( v ) − 1 {\displaystyle 2^{bh(v)}-1} {\displaystyle 2^{bh(v)}-1} внутренних узлов.
Покажем, что тогда v ′ {\displaystyle v'} v', для которого h ( v ′ ) = k + 1 {\displaystyle h(v')=k+1} {\displaystyle h(v')=k+1}, имеет не менее 2 b h ( v ′ ) − 1 {\displaystyle 2^{bh(v')}-1} {\displaystyle 2^{bh(v')}-1} внутренних узлов.
Так как v ′ {\displaystyle v'} v' имеет h ( v ′ ) > 0 {\displaystyle h(v')>0} {\displaystyle h(v')>0}, это внутренний узел. Как таковой он имеет два потомка, оба из которых имеют чёрную высоту b h ( v ′ ) {\displaystylebh(v')} {\displaystylebh(v')}, либо b h ( v ′ ) − 1 {\displaystylebh(v')-1} {\displaystylebh(v')-1} (зависит от того, является v ′ {\displaystyle v'} v' красным, или чёрным).
|
|
|
По индукционному предположению каждый потомок имеет не менее 2 b h ( v ′ ) − 1 − 1 {\displaystyle 2^{bh(v')-1}-1} {\displaystyle 2^{bh(v')-1}-1} внутренних узлов, поэтому v ′ {\displaystyle v'} v' имеет не менее
2 b h ( v ′ ) − 1 − 1 + 2 b h ( v ′ ) − 1 − 1 + 1 = 2 b h ( v ′ ) − 1 {\displaystyle 2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1} {\displaystyle 2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1}
внутренних узлов.
Используя эту лемму, мы можем показать, что дерево имеет логарифмическую высоту. Так как по крайней мере половина узлов в любом пути от корня до листа — чёрные (свойство 4 красно-чёрного дерева), чёрная высота корня не менее h ( r o o t ) / 2 {\displaystyle h(root)/2} {\displaystyle h(root)/2}. По лемме имеем:
n ≥ 2 h ( root ) 2 − 1 ↔ log 2 ( n + 1 ) ≥ h ( root ) 2 ↔ h ( root ) ≤ 2 log 2 ( n + 1 ) . {\displaystyle n\geq 2^{h({\text{root}}) \over 2}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\text{root}}) \over 2}\leftrightarrow \;h({\text{root}})\leq 2\log _{2}{(n+1)}.} n\geq 2^{{{h({\text{root}}) \over 2}}}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\text{root}}) \over 2}\leftrightarrow \;h({\text{root}})\leq 2\log _{2}{(n+1)}.
Поэтому высота корня O ( l o g ( n ) ) {\displaystyle O(log(n))} O(log(n)).
Язык программирования
Си++ — компилируемый строго типизированный язык программирования общего назначения. Поддерживает разные парадигмы программирования: процедурную, обобщённую, функциональную; наибольшее внимание уделено поддержке объектно-ориентированного программирования.
|
|
|
Разработка языка началась в 1979 году. Целью создания C++ было дополнение C возможностями, удобными для масштабной разработки ПО, с сохранением гибкости, скорости и портабельности C. Вместе с тем создатели C++ стремились сохранить совместимость с C: синтаксис первого основан на синтаксисе последнего, и большинство программ на C будут работать и как C++. Изначально новый язык назывался “C с классами”, но затем имя было изменено на C++ — это должно было подчеркнуть как его происходжение от C, так и его превосходство над последним.
Нововведениями C++ в сравнении с C являются:
1.поддержка объектно-ориентированного программирования через классы. 2.C++ предоставляет все четыре возможности ООП — абстракцию, инкапсуляцию, наследование (в том числе и множественное) и полиморфизм.
поддержка обобщённого программирования через шаблоны функций и классов;
3.стандартная библиотека C++ состоит из стандартной библиотеки C (с некоторыми модификациями) и библиотеки шаблонов (StandardTemplateLibrary, STL), которая предоставляет обширный набор обобщенных контейнеров и алгоритмов;
|
|
|
4дополнительные типы данных;
5обработка исключений;
6виртуальные функции;
7пространства имён;
8встраиваемые (inline) функции;
9перегрузка (overloading) операторов;
10перегрузка имён функций;
11ссылки и операторы управления свободно распределяемой памятью.
c++ Поддерживает такие парадигмы программирования, как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование. Язык имеет богатую стандартную библиотеку, которая включает в себя распространённые контейнеры и алгоритмы, ввод-вывод, регулярные выражения, поддержку многопоточности и другие возможности. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков.[3][4] В сравнении с его предшественником — языком C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования.
Типы
В C++ доступны следующие встроенные типы. Типы C++ практически полностью повторяют типы в C:
Символьные: char, wchar_t (char16_t и char32_t, в стандарте C++).
Целочисленныезнаковые: signed char, short int, int, long int (и long long, встандарте C++).
Целочисленныебеззнаковые: unsigned char, unsigned short int, unsigned int, unsigned long int(и unsigned long long, встандарте C++).
|
|
|
Сплавающейточкой: float, double, long double.
Логический: bool, имеющий значения true или false.
Операции сравнения возвращают тип bool. Выражения в скобках после if, while приводятся к типу bool.
Язык ввёл понятие ссылок, а начиная с одиннадцатой версии стандарта rvalue ссылки и forwarding ссылки.
C++ добавляет к C объектно-ориентированные возможности. Он вводит классы, которые обеспечивают три самых важных свойства ООП: инкапсуляцию, наследование и полиморфизм.
В стандарте C++ под классом (class) подразумевается пользовательский тип, объявленный с использованием одного из ключевых слов class, struct или union, под структурой (structure) подразумевается класс, определённый через ключевое слово struct, и под объединением (union) подразумевается класс, определённый через ключевое слово union.
В теле определения класса можно указать как объявления функций, так и их определение. В последнем случае функция является встраиваемой (inline)). Нестатические функции-члены могут иметь квалификаторы const и volatile, а также ссылочный квалификатор (& или &&)
Стандартная библиотека C++ включает в себя набор средств, которые должны быть доступны для любой реализации языка, чтобы обеспечить программистам удобное пользование языковыми средствами и создать базу для разработки как прикладных приложений самого широкого спектра, так и специализированных библиотек. Стандартная библиотека C++ включает в себя часть стандартной библиотеки C. Стандарт C++ содержит нормативную ссылку на стандарт C от 1990 года и не определяет самостоятельно те функции стандартной библиотеки, которые заимствуются из стандартной библиотеки C.
Доступ к возможностям стандартной библиотеки C++ обеспечивается с помощью включения в программу (посредством директивы #include) соответствующих стандартных заголовочных файлов. Всего в стандарте C++11 определено 79 таких файлов. Средства стандартной библиотеки объявляются как входящие в пространство имён std. Заголовочные файлы, имена которых соответствуют шаблону «cX», где X — имя заголовочного файла стандартной библиотеки C без расширения (cstdlib, cstring, cstdio и пр.), содержат объявления, соответствующие данной части стандартной библиотеки C. Стандартные функции библиотеки C также находятся в пространстве имён std.
Поддержка языка. Включает средства, которые необходимы для работы программ, а также сведения об особенностях реализации. Выделение памяти, RTTI, базовые исключения, пределы значений для числовых типов данных, базовые средства взаимодействия со средой, такие как системные часы, обработка сигналов UNIX, завершение программы.
Стандартные контейнеры. В стандартную библиотеку входят шаблоны для следующих контейнеров: динамический массив(vector), статический массив(array), одно- и двунаправленные списки(list, forward_list), стек(stack), дек(deque), ассоциативные массивы(map, multimap), множества(set, multiset), очередь с приоритетом(priority_queue).
Основные утилиты. В этот раздел входит описание основных базовых элементов, применяемых в стандартной библиотеке, распределителей памяти и поддержка времени и даты в стиле C.
Итераторы. Обеспечивают шаблоны итераторов, с помощью которых в стандартной библиотеке реализуется стандартный механизм группового применения алгоритмов обработки данных к элементам контейнеров.
Алгоритмы. Шаблоны для описания операций обработки, которые с помощью механизмов стандартной библиотеки могут применяться к любой последовательности элементов, в том числе к элементам в контейнерах. Также в этот раздел входят описания функций bsearch() и qsort() из стандартной библиотеки C.
Строки. Шаблоны строк в стиле C++. Также в этот раздел попадает часть библиотек для работы со строками и символами в стиле C.
Ввод-вывод. Шаблоны и вспомогательные классы для потоков ввода-вывода общего вида, строкового ввода-вывода, манипуляторы (средства управления форматом потокового ввода-вывода в стиле C++).
Локализация. Определения, используемые для поддержки национальных особенностей и форматов представления (дат, валют и т. д.) в стиле C++ и в стиле C.
Диагностика. Определения ряда исключений и механизмов проверки утверждений во время выполнения (assert). Поддержка обработки ошибок в стиле C.
Числа. Определения для работы с комплексными числами, математическими векторами, поддержка общих математических функций, генератор случайных чисел.
Контейнеры, строки, алгоритмы, итераторы и основные утилиты, за исключением заимствований из библиотеки C, собирательно называются STL (StandardTemplateLibrary — стандартная шаблонная библиотека). Изначально эта библиотека была отдельным продуктом и её аббревиатура расшифровывалась иначе, но потом она вошла в стандартную библиотеку C++ в качестве неотъемлемого элемента. В названии отражено то, что для реализации средств общего вида (контейнеров, строк, алгоритмов) использованы механизмы обобщённого программирования (шаблоны C++ — template). В работах Страуструпа подробно описываются причины, по которым был сделан именно такой выбор. Основными из них являются бо?льшая универсальность выбранного решения (шаблонные контейнеры, в отличие от объектных, могут легко использоваться для не объектных типов и не требуют наличия общего предка у типов элементов) и его техническая эффективность (как правило, операции шаблонного контейнера не требуют вызовов виртуальных функций и могут легко встраиваться (inline), что в итоге даёт выигрыш в производительности).
Начиная со стандарта C++ добавились следующие возможности:
Добавлена библиотека <regex>, реализующая общепринятые механизмы поиска и подстановки с помощью регулярных выражений.
Добавлена поддержка многопоточности.
Атомарные операции
unordered варианты ассоциативных массивов и множеств.
Умные указатели, обеспечивающие автоматическое освобождение выделенной памяти.
Источники
1.Штайн К. Алгоритмы: построение и анализ
2.Источники Internet
Дата добавления: 2018-02-15; просмотров: 980; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!