Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Древовидные структуры (деревья бинарные, сбалансированные, сильноветвящиеся). Основные операции (поиск, вставка, удаление).




Читайте также:
  1. A) сочетание жилищ, городской инфраструктуры и зеленых насаждений
  2. I. Основные термины курса
  3. S: Перечислите основные направления в исламе.
  4. S: Перечислите основные направления в исламе.
  5. S: Перечислите основные направления протестантизма.
  6. S: Перечислите основные причины возникновения религии.
  7. V2:2 Основные мировые религии.
  8. А. Анализ существующих структуры и фонда заработной платы
  9. Автокорреляция уровней временного ряда. Анализ структуры временного ряда на основании коэффициентов автокорреляции
  10. Аграрная реформа П.А. Столыпина: основные задачи и последствия;

Деревом называется орграф для которого: Существует узел, в которой не входит ни одной дуги. Этот узел называется корнем. В каждую вершину, кроме корня, входит одна дуга.

С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся. В бинарном дереве из каждой вершины выходит не более двух дуг. В сильноветвящемся дереве количество дуг может быть произвольным.

Бинарное дерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков. Как правило, первый называется родительским узлом, а дети называются левым и правым сыновьями. Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.

Бинарное дерево называется сбалансированным или АВЛ-деревом, если для любой вершины дерева, высота левого и правого поддеревьев отличается не более чем на единицу.

 

Поиск элемента (FIND) Дано: дерево Т и ключ K. Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел. Алгоритм:

  • Если дерево пусто, сообщить, что узел не найден, и остановиться.
  • Иначе сравнить K со значением ключа корневого узла X.
    • Если K=X, выдать ссылку на этот узел и остановиться.
    • Если K>X, рекурсивно искать ключ K в правом поддереве Т.
    • Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Добавление элемента (INSERT) Дано: дерево Т и пара (K,V). Задача: добавить пару (K, V) в дерево Т. Алгоритм:

  • Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.
  • Иначе сравнить K с ключом корневого узла X.
    • Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
    • Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.

 

Удаление узла (REMOVE) Дано: дерево Т с корнем n и ключом K. Задача: удалить из дерева Т узел с ключом K (если такой есть). Алгоритм:


Дата добавления: 2015-04-18; просмотров: 15; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты