Знайте, Intuit, лекция, задачите по динамична структура на данните

През декември е специален вид линия.

Декември (Engl deque -. Съкращение на два края на опашката deque.) - структурата на данните. представлява последователност от елементи, които могат да добавяне и изтриване на елементи в произволен ред от двете страни (фиг. 32.3). Първите и последните елементи на входа на палубата мач и изхода на палубата.

Знайте, Intuit, лекция, задачите по динамична структура на данните


Фиг. 32.3. Дъски и неговата организация

Специфични случаи на палубата - на палубата е ограничен:

  • Декември ограничен вход - от края на палубата може да извлече само елементи;
  • Декември ограничен изход - това е възможно само, за да добавите елементи към края на палубата.

Тази структура е най-разнообразни линейни структури, описани по-горе. С налагането на допълнителни ограничения върху работата с началото и / или края на палубата. Тя може да се извършва моделиране на стека и опашката.

Въпреки това, по отношение на палубата не е препоръчително да се говори за началото и края на свой ред и на левия и десния край.

Изпълнението на тези операции са показани като съответните функции, които, от своя страна. Използвайте функцията операции с линеен двупосочен списък.

Червено-черните дървета

Двоични дървета работят най-добре, когато те са балансирани, когато дължината на пътя от корена на всяко листо е до известна степен, свързана с броя на върховете. Червените-черно дървета са един от начините за балансиране дървета. Името се получава от стандартните оцветители събрания такива дървета в червено и черно цветове. Vertex цветове се използват за балансиране на дървото.

Червено-черен дърво (червено-черно-Tree, RB-Tree) - е двоично дърво със следните свойства (виж фигура 32.4.):

  • всеки връх трябва да бъдат оцветени или черно или червено;
  • корен на дървото трябва да е черен;
  • листата на дървото трябва да са черни и да се декларират като върховете на NIL (NIL -uzly, тоест, "виртуални" възли наследници възли, обикновено се наричат ​​листа, те "покажи" NULL указатели);
  • всеки червен възел трябва да има една черна предшественик;
  • във всички клонове на дървото, което води от корена към листата, броят на черните върхове еднакво.

Знайте, Intuit, лекция, задачите по динамична структура на данните


Фиг. 32.4. Червено-черен дърво

Броят на черни върховете на клоните от корена до листо на дървото се нарича черен височина. Тези свойства гарантират, че най-дългият клон от корена до листо е не повече от два пъти по-дълго, колкото всички други отрасли от корена към листата.

Над червено-черно дърветата можете да извършвате всички същата основна операция. че на двоични дървета.

Основни термини

А циклични (пръстен) списък - структурата на данните. представлява последователност от елементи, като последният елемент от които съдържа указател към първия елемент. и първия (в случая на двупосочна списък) - последен.

Декември - структурата на данните. представлява последователност от елементи, които могат да се добавят и изтриване на елементи в произволен ред от двете страни.

Декември и при ограничен вход - този на декември. от края на която е възможно да се извлече само елементите;

Декември и при ограничен изход - декември. в края на който можете да добавите само предмети.

Червено-черен дърво (червено-черно-Tree, RB-Tree) - е двоично дърво със следните свойства:

  • всеки връх трябва да бъдат оцветени или черно или червено;
  • корен на дървото трябва да е черен;
  • листата на дървото трябва да са черни и да се декларират като върховете на NIL;
  • всеки червен възел трябва да има една черна предшественик;
  • във всички клонове на дървото, което води от корена към листата, броят на черните върхове еднакво.

Черно височина на дървото - е броят на черни върхове в клон червено-черно дърво от корена до листо.

кратко резюме