Знайте, Intuit, лекция, задачите по динамична структура на данните
През декември е специален вид линия.
Декември (Engl deque -. Съкращение на два края на опашката deque.) - структурата на данните. представлява последователност от елементи, които могат да добавяне и изтриване на елементи в произволен ред от двете страни (фиг. 32.3). Първите и последните елементи на входа на палубата мач и изхода на палубата.
Фиг. 32.3. Дъски и неговата организация
Специфични случаи на палубата - на палубата е ограничен:
- Декември ограничен вход - от края на палубата може да извлече само елементи;
- Декември ограничен изход - това е възможно само, за да добавите елементи към края на палубата.
Тази структура е най-разнообразни линейни структури, описани по-горе. С налагането на допълнителни ограничения върху работата с началото и / или края на палубата. Тя може да се извършва моделиране на стека и опашката.
Въпреки това, по отношение на палубата не е препоръчително да се говори за началото и края на свой ред и на левия и десния край.
Изпълнението на тези операции са показани като съответните функции, които, от своя страна. Използвайте функцията операции с линеен двупосочен списък.
Червено-черните дървета
Двоични дървета работят най-добре, когато те са балансирани, когато дължината на пътя от корена на всяко листо е до известна степен, свързана с броя на върховете. Червените-черно дървета са един от начините за балансиране дървета. Името се получава от стандартните оцветители събрания такива дървета в червено и черно цветове. Vertex цветове се използват за балансиране на дървото.
Червено-черен дърво (червено-черно-Tree, RB-Tree) - е двоично дърво със следните свойства (виж фигура 32.4.):
- всеки връх трябва да бъдат оцветени или черно или червено;
- корен на дървото трябва да е черен;
- листата на дървото трябва да са черни и да се декларират като върховете на NIL (NIL -uzly, тоест, "виртуални" възли наследници възли, обикновено се наричат листа, те "покажи" NULL указатели);
- всеки червен възел трябва да има една черна предшественик;
- във всички клонове на дървото, което води от корена към листата, броят на черните върхове еднакво.
Фиг. 32.4. Червено-черен дърво
Броят на черни върховете на клоните от корена до листо на дървото се нарича черен височина. Тези свойства гарантират, че най-дългият клон от корена до листо е не повече от два пъти по-дълго, колкото всички други отрасли от корена към листата.
Над червено-черно дърветата можете да извършвате всички същата основна операция. че на двоични дървета.
Основни термини
А циклични (пръстен) списък - структурата на данните. представлява последователност от елементи, като последният елемент от които съдържа указател към първия елемент. и първия (в случая на двупосочна списък) - последен.
Декември - структурата на данните. представлява последователност от елементи, които могат да се добавят и изтриване на елементи в произволен ред от двете страни.
Декември и при ограничен вход - този на декември. от края на която е възможно да се извлече само елементите;
Декември и при ограничен изход - декември. в края на който можете да добавите само предмети.
Червено-черен дърво (червено-черно-Tree, RB-Tree) - е двоично дърво със следните свойства:
- всеки връх трябва да бъдат оцветени или черно или червено;
- корен на дървото трябва да е черен;
- листата на дървото трябва да са черни и да се декларират като върховете на NIL;
- всеки червен възел трябва да има една черна предшественик;
- във всички клонове на дървото, което води от корена към листата, броят на черните върхове еднакво.
Черно височина на дървото - е броят на черни върхове в клон червено-черно дърво от корена до листо.