- окт 09, 2020
Бадасян Т.С., Авагян С.К.
Email: Адрес электронной почты защищен от спам-ботов. Для просмотра адреса в вашем браузере должен быть включен Javascript.
Бадасян Тигран Смбатович – магистрант,
факультет прикладной математики и физики;
Авагян Сурен Константинович – магистрант,
кафедра электронных измерительных приборов и метрологии,
Национальный политехнический университет Армении,
г. Ереван, Республика Армения
Аннотация: красно-чёрное дерево – вариант самобалансирующегося двоичного дерева поиска, которым гарантируется логарифмическое увеличение высоты и скорость выполнения основных операций, представленных добавлением, удалением и поиском узла. Сбалансированность определяется введением «чёрного цвета» или «красного цвета». Red-black tree применяется с целью организации сравнимых данных в виде текстовых фрагментов или числа. В листовых узлах не содержатся данные, поэтому отсутствует необходимость выделять память, а работа предполагает ведение записи в узле-предке (указатель на потомка). В статье рассмотрено красно-чёрное дерево: его балансирование и сложность.
Ключевые слова: красно-черное дерево, балансирование, алгоритм, эффективность, элемент.
RED-BLACK TREE: BALANCING AND COMPLEXITY
Badasyan T.S., Avagyan S.K.
Badasyan Tigran Smbatovich - Undergraduate,
FACULTY OF APPLIED MATHEMATICS AND PHYSICS;
Avagyan Suren Konstantinovich - Undergraduate,
DEPARTMENT OF ELECTRONIC MEASURING INSTRUMENTS AND METROLOGY,
NATIONAL POLYTECHNIC UNIVERSITY OF ARMENIA,
YEREVAN, REPUBLIC OF ARMENIA
Abstract: а red-black tree is a variant of a self-balancing binary search tree, which guarantees a logarithmic increase in height and speed of performing basic operations, represented by adding, deleting and searching a node. Balance is determined by the introduction of “black” or “red”. Red-black tree is used to organize comparable data in the form of text fragments or numbers. The leaf nodes do not contain data, so there is no need to allocate memory, and the work involves maintaining records in the ancestor node (a pointer to a descendant). The article considers the red-black tree: its balancing and complexity.
Keywords: red-black tree, balancing, algorithm, efficiency, element.
Список литературы / References
- Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. Структуры данных и алгоритмы. М.: Вильямс, 2000. С. 384.
- Мейн Майкл, Савитч Уолтер. Структуры данных и другие объекты в C++. 2-е изд. М.: Вильямс, 2002. С. 832.
- Седжвик Роберт. Фундаментальные алгоритмы на C. Анализ / Структуры данных / Сортировка / Поиск. СПб.: ДиаСофтЮП, 2003. С. 672.
Ссылка для цитирования данной статьи
Тип лицензии на данную статью – CC BY 4.0. Это значит, что Вы можете свободно цитировать данную статью на любом носителе и в любом формате при указании авторства. | ||
Бадасян Т.С., Авагян С.К. КРАСНО-ЧЁРНОЕ ДЕРЕВО: БАЛАНСИРОВАНИЕ И СЛОЖНОСТЬ // Наука, техника и образование № 3(67), 2020. - С.{см. журнал}. |