Декартовы деревья
план-конспект урока по информатике и икт (11 класс)

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«ГИМНАЗИЯ № 3» ГОРОДСКОГО ОКРУГА САМАРА

Конспект урока

Информатики и ИКТ

в 11 классе

Тема урока: «Декартовы деревья»

Дата проведения урока: 20.03.2019 г.

Класс: 11

Работу подготовил:

учитель информатики

высшей категории

Сметанников Андрей Леонидович

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«ГИМНАЗИЯ № 3» ГОРОДСКОГО ОКРУГА САМАРА

Конспект урока

Информатики и ИКТ

в 11 классе

Тема урока: «Декартовы деревья»

Дата проведения урока: 20.03.2019 г.

Класс: 11

Работу подготовил:

 учитель информатики

высшей категории

Сметанников Андрей Леонидович

Самара, 2019 г.

Цели урока:

• создание условий для формирования ключевых компетенций;
• развитие творческих способностей учащихся;
• научить оценки эффективности используемой структуры данных;
• познакомить с существующими методами поиска.

Формируемые УУД:

Познавательные действия:

1. Умение строить бинарное дерево с оценкой эффективности его использования.
2. Анализ структуры данных «Кучи».
3. Умения построения декартового дерева.

Регулятивные действия:

1. Находить варианты решения различных проблем связанных с структурой данных предназначенных для поиска информации.
2. Освоение способов решения проблем творческого и поискового характера.

Коммуникативные действия:

1. Умение обсуждать и анализировать методы поиска в иерархический структурах данных.
2. Задавать вопросы, слушать и отвечать на вопросы других.

Основные понятия: бинарное дерево, heap, декартово дерево.

Межпредметные связи: математика.

Организация пространства: лекционно-практическая работа.

Оснащение рабочего места педагога: компьютер.

ХОД УРОКА

1. Из пройденных тем известно, что при использовании двоичного дерева для поиска повышает эффективность до O(N)=log2N

2. При работе со структурой может произойти вырождение дерева, например:

Не сложно заметить, что эффективности можно оценить как O(N)=N.

3. При решении этой проблемы можно совместить две структуры данных: бинарное дерево («где левые легкие, а праве тяжелые»),  и «кучу» рассмотренную на прошлых уроках («где родитель тяжелее детей»). Для этого добавляется к каждому узлу дерева случайное число, создавая пару (ключ, значение), по ключу строиться бинарное дерево, а по значению куча.

Где красным- ключ, синим значение.

4. Операции работы с деревом:

Lookup(x). Вывод данных. O(N)=log2N.

Insert(x,value). Вставка элемента. O(N)=log2N.

Delete(x) (log 𝑛) ). Удаление элемента. O(N)=log2N.

Split(x). Деление на два дерева. O(N)=[log2N, N].

Merge(T1, T2) ). Объединение деревьев. O(N)= [log2N, N].

5. Split(x).

Случай 1: ключ разбиения x > ключа корня (root.x)

• Левое поддерево T1 совпадает с левым поддеревом корня T
• Для нахождения правого поддерева T1 необходимо разбить правое поддерево T по ключу x на T1R и T2R и взять T1R
• Дерево T2 совпадает с деревом T2R

Случай 2: ключ разбиения x < ключа корня

• Правое поддерево T2 совпадает с правым поддеревом корня T
• Для нахождения левого поддерева T2 необходимо разбить левое поддерево T по ключу x на T1L и T2L и взять T2L
• Дерево T1 совпадает с деревом T1L

// дерево с корнем t делим на два с корнями a b причем все ключи а больше k, b меньше.

void split(treapNode* t, int k, treapNode* &a, treapNode* &b) {

    if (t==NULL)

        a = b = NULL;

    else

        if (t->k < k) { split(t->r, k, t->r, b); a = t; } else { split(t->l, k, a, t->l); b = t; }

}

6. Merge(T1,T2).

Случай 1: Приоритет y корня T1 > приоритета y корня T2

• Корень дерева T1 становится корнем T
• Левое поддерево T1 становится левым поддеревом T
• Правое поддерево T – это объединение правого поддерева T1 и дерева T2

Случай 2: Приоритет y корня T1 < приоритета y корня T2

• Корень дерева T2 становится корнем T
• Правое поддерево T2 становится правым поддеревом T
• Левое поддерево T – это объединение T1 и левого поддерева T2

// соединяем два дерева в одно a,b - указатели на корни соединяемых деревьев все ключи k от а больше ключей b

// на соединенное дерево указывает а

treapNode * merge(treapNode *a, treapNode *b) {

    if (a==NULL || b==NULL) return a ? a : b;

    if (a->p > b->p) { a->r = merge(a->r, b); return a;}

    else { b->l = merge(a, b->l); return b; }

}

7. Insert (T1,X).

void insert(int key, int value) {

    treapNode *cur = new treapNode(key, value), *rootL, *rootR;

    split(root, key, rootL, rootR);

    root = merge(rootL, cur);

    root = merge(root, rootR); }

8. Remove(Key)

void remove(int key) {

    treapNode *rootL, *rootM, *rootR;

    split(root, key, rootL, rootM);

    split(rootM, key + 1, rootM, rootR);

    root = merge(rootL, rootR);

    delete(rootM);

}

9. Вывод дерева

struct treapNode {

    int k, p, v; // k - ключ для бинарного дерева поиска  p - для кучи (пирамиды),  v - значение

    treapNode *l, *r;

    treapNode(int key, int value) { k = key; v = value; p = rand(); l = r = NULL;}

};