Главная » Деревья

Красно черные деревья pascal

Содержание
  1. Введение
  2. 1. Структуры данных: деревья
  3. 1.1 Структуры данных
  4. Красно черные деревья pascal
  5. Usage
  6. Example
  7. Complexity
  8. Authors
  9. Download
  10. Licence
  11. Bugs/Contact
  12. Красно черные деревья pascal
  13. Usage
  14. Example
  15. Complexity
  16. Authors
  17. Download
  18. Licence
  19. Bugs/Contact

Введение

Множество — это фундаментальное понятие, как в математике, так и в теории вычислительных машин. Тогда как математические множества остаются неизменными, множества, которые обрабатываются в ходе выполнения алгоритмов, могут с течением времени разрастаться, уменьшаться, или подвергаться другим изменениям. Назовем такие множества динамическими (dynamic). В данной работе описывается метод представления конечных динамических множеств в виде красно-чёрных деревьев – один из основных методов представления конечных динамических множеств.

Объектом данной работы является разновидность структур данных красно-чёрные деревья.

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

В качестве предмета данной работы выступают операции, выполняемые над красно-чёрными деревьями.

Целью данной работы является изучение красно-чёрных деревьев и исследование их основных свойств, а также автоматизация операций для работы с ними на Turbo Pascal 7.0. Для этого необходимо выполнить следующие задачи:

  • исследовать основные понятия красно-чёрных деревьев;
  • изучить основные операции, выполняемые над красно-чёрными деревьями;
  • автоматизировать основные операции, выполняемые над красно-чёрными деревьями, в общем виде на языке Turbo Pascal;
  • сделать выводы по выполненной работе.

Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска. В частности, контейнер map в большинстве реализаций библиотеки STL языка C++, класс TreeMap языка Java, так же, как и многие другие реализации ассоциативного массива в различных библиотеках, основаны на красно-чёрных деревьях.

Популярность красно-чёрных деревьев связана с тем, что на них часто достигается подходящий баланс между степенью сбалансированности и сложностью поддержки сбалансированности.

1. Структуры данных: деревья

1.1 Структуры данных

Структура данных — совокупность физически (типы данных) и логически (алгоритм, функции) взаимосвязанных переменных и их значений.

Рис. 1. Классификация структур данных.

Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных — простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).

Весьма важный признак структуры данных — ее изменчивость — изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивости приведена на рис. 1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

Читайте также:  Масло чайного дерева пакистан

Важный признак структуры данных — характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур — многосвязные списки, деревья, графы.

В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.

Информация по каждому типу однозначно определяет :

1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;

2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

3) множество допустимых операций, которые применимы к объекту описываемого типа.

Источник

Красно черные деревья pascal

The class is based on the STL tree implementation of gcc-3.4.4 (/libstdc++-v3/include/bits/stl_tree.h and /libstdc++-v3/src/tree.cc) of which the insertion and deletion algorithms are based on those in Cormen, Leiserson and Rivest, Introduction to Algorithms (MIT Press, 1990).

This unit should work ok with Borland Delphi and Free Pascal (I used fpc-2.0.0 with the -Sd commandline switch).

Usage

The TRBTree class behaves somewhat like a TList: it stores pointers and uses the same comparison function as TList.Sort (TListSortCompare). Functions Clear, Add, Delete, First and Last are equivalent, except that First and Last return a TRBNodeP instead of its key so they can be used for comparisons in loops. All values occur only once in the tree: when the same value is added twice, the second one is not stored.

To be able to manage the tree, the Create constructor has a argument specifying the comparison function that should be used.

The function Find can be used to find a value that was put in the tree, it searches for the given pointer using the comparison function given at time of object creation. It returns a TRBNodeP.

The functions RBInc and RBDec can be used to «walk» through the tree: given a TRBNodeP x, RBInc returns the TRBNodeP with the smallest key that is larger than x, RBDec returns the TRBNodeP with the largest key that is smaller than x. RBInc(tree.Last) and RBDec(tree.First) are not defined.

Читайте также:  Заболевания дерева грецкого ореха

Example

Complexity

Create, First and Last are done in constant time.
Find, Add, Delete, RBInc and RBDec take O(log n) time, where n is the number of items in the tree. Destroy and Clear take O(n) time.

Authors

Written (or translated. ) by Freek van Walderveen, November 2005. Includes some bug fixes by Jani Mátyás, July 2008. Jani also adapted the implementation to use Free Pascal generics, this version can also be found below.

Download

  • rbtree.pas, containing the TRBTree class (unit rbtree)
  • example.dpr, example code
  • grbtree.pas, a version using Free Pascal generics
  • example_grbtree.pas, example code for the generics version

Licence

This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. See http://www.gnu.org/copyleft/gpl.html This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
As a special exception, you may use this library as part of a free software library without restriction. Specifically, if you compile this library and link it with other files to produce an executable, this file does not by itself cause the resulting executable to be covered by the GNU General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License.

Bugs/Contact

Bugs reports and information requests may be send to freek -at- vanwal -dot- nl.

Источник

Красно черные деревья pascal

The class is based on the STL tree implementation of gcc-3.4.4 (/libstdc++-v3/include/bits/stl_tree.h and /libstdc++-v3/src/tree.cc) of which the insertion and deletion algorithms are based on those in Cormen, Leiserson and Rivest, Introduction to Algorithms (MIT Press, 1990).

This unit should work ok with Borland Delphi and Free Pascal (I used fpc-2.0.0 with the -Sd commandline switch).

Usage

The TRBTree class behaves somewhat like a TList: it stores pointers and uses the same comparison function as TList.Sort (TListSortCompare). Functions Clear, Add, Delete, First and Last are equivalent, except that First and Last return a TRBNodeP instead of its key so they can be used for comparisons in loops. All values occur only once in the tree: when the same value is added twice, the second one is not stored.

Читайте также:  Закапать ухо маслом чайного дерева

To be able to manage the tree, the Create constructor has a argument specifying the comparison function that should be used.

The function Find can be used to find a value that was put in the tree, it searches for the given pointer using the comparison function given at time of object creation. It returns a TRBNodeP.

The functions RBInc and RBDec can be used to «walk» through the tree: given a TRBNodeP x, RBInc returns the TRBNodeP with the smallest key that is larger than x, RBDec returns the TRBNodeP with the largest key that is smaller than x. RBInc(tree.Last) and RBDec(tree.First) are not defined.

Example

Complexity

Create, First and Last are done in constant time.
Find, Add, Delete, RBInc and RBDec take O(log n) time, where n is the number of items in the tree. Destroy and Clear take O(n) time.

Authors

Written (or translated. ) by Freek van Walderveen, November 2005. Includes some bug fixes by Jani Mátyás, July 2008. Jani also adapted the implementation to use Free Pascal generics, this version can also be found below.

Download

  • rbtree.pas, containing the TRBTree class (unit rbtree)
  • example.dpr, example code
  • grbtree.pas, a version using Free Pascal generics
  • example_grbtree.pas, example code for the generics version

Licence

This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. See http://www.gnu.org/copyleft/gpl.html This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
As a special exception, you may use this library as part of a free software library without restriction. Specifically, if you compile this library and link it with other files to produce an executable, this file does not by itself cause the resulting executable to be covered by the GNU General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License.

Bugs/Contact

Bugs reports and information requests may be send to freek -at- vanwal -dot- nl.

Источник

Оцените статью
© 2024 Деревья и растения