Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Спецификация класса AVLTree.
Объявление: // Значения показателя сбалансированности узла
const int leftheavy = - 1; const int balanced = 0; const int rightheavy = 1;
template <class T>
class AVLTree: public BinSTree<T> { private:
// выделение памяти AVLTreeNode<T> *GetAVLTreeNode(const T& item, AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr);
// используется конструктором копирования и оператором присваивания AVLTreeNode<T> *CopyTree(AVLTreeNode<T> *t); // используется методами Insert и Delete для восстановления АВЛ - условий после операций вставки/удаления void SingleRotateLeft (AVLTreeNode<T>* &p); void SingleRotateRight (AVLTreeNode<T>* &p); void DoubleRotateLeft (AVLTreeNode<T>* &p); void DoubleRotateRight (AVLTreeNode<T>* &p); void UpdateLeftTree (AVLTreeNode<T>* &tree, int &reviseBalanceFactor); void UpdateRightTree (AVLTreeNode<T>* &tree, int &reviseBalanceFactor); // специальные версии методов Insert и Delete void AVLInsert(AVLTreeNode<T>* &tree, AVLTreeNode<T>* newNode, int &reviseBalanceFactor); void AVLDelete(AVLTreeNode<T>* &tree, AVLTreeNode<T>* newNode, int &reviseBalanceFactor);
public: // конструкторы AVLTree(void); AVLTree(const AVLTree<T>& tree);
// оператор присваивания AVLTree<T>& operator= (const AVLTree<T>& tree);
// стандартные методы обработки списков virtual void Insert(const T& item); virtual void Delete(const T& item); }; Описание: Константы leftheavy, balanced и rightheavy используются в операциях вставки/удаления для описания показателя сбалансированности узла. Метод GetAVLTreeNode управляет выделением памяти для экземпляра класса. По умолчанию balanceFactor нового узла равен нулю.
Рис. 5. В этом классе заново определяется функция CopyTree для использования с конструктором копирования и перегруженным оператором присвоения. Несмотря на то, что алгоритм идентичен алгоритму для функции CopyTree класса BinSTree, новая версия корректно создает расширенные объекты типа AVLTreeNode при построении нового дерева. Функции AVLInsert и AVLDelete реализуют методы Insert и Delete, соответственно. Они используют скрытые методы наподобие SingleRotateLeft. Открытые методы Insert и Delete объявлены виртуальными и подменяют соответствующие функции базового класса. Остальные операции наследуются от класса BinSTree. Пример: Код, приведенный ниже, создает деревья, приведенные на рисунке 5. После удаления из АВЛ - дерева (В) элемента 3 АВЛ - дерево принимает вид, изображенный на рисунке 5 (С). Цифра после двоеточия означает фактор сбалансированности.
AVLTree<int> avltree; // AVLTree - список целых чисел BinSTree<int> bintree; // BinSTree - список целых чисел
for (int i=1; i<=5; i++) {
bintree.Insert(i); // создать дерево А avltree.Insert(i); // создать дерево В } avltree.Delete(3); // удалить 3 из АВЛ - дерева // дерево (С) есть дерево (В) без удаленного узла 3.
|
||||
Последнее изменение этой страницы: 2020-03-14; просмотров: 113; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.222.125.171 (0.003 с.) |