«Красно-черное дерево»

МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН ТАШКЕНТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ИМЕНИ МУХАММАДА АЛЬ-ХОРЕЗМИЙ УРГЕНЧСКИЙ ФИЛИАЛ ТЕХНОЛОГИЧЕСКОГО УНИВЕРСИТЕТА
ФАКУЛЬТЕТ ТЕЛЕКОММУНИКАЦИОННЫЕ ТЕХНОЛОГИИ





Самостоятельная работа

по предмету:

«Проектирование алгоритомов»
На тему: «Красно-черное дерево»


Подготовила: студентка группы 972-19 Хазиева Элиза Рауфовна
Приняла: Матякубов Маркс

Ургенч-2022

План:

Введение

• 
  1. Терминология
  
• 
  2. Свойства
  
• 
  3. Аналогия с B-деревом порядка 4
  
• 
  4. Работа с красно-чёрными деревьями
  
• 
  5. Операции
  
  • 
    5.1. Вставка
    
  • 
    5.2. Удаление
    
• 
  6. Сравнение с идеально сбалансированным АВЛ-деревом
  
  • 
    6.1. Высота дерева
    
  • 
    6.2. Поиск
    
  • 
    6.3. Вставка
    
  • 
    6.4. Удаление
    
  • 
    6.5. Память
    
• 
  7. Доказательство асимптотических границ
  

Литература
Источники

Введение

Красно-чёрное дерево (англ. Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски, красная и чёрная, и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом.