Published December 23, 2021
| Version v1
Publication
Open
Improving the Red-Black tree delete algorithm
Description
Abstract Today, Red-Black trees are becoming a popular data structure typically used to implement dictionaries, associative arrays, symbol tables within some compilers (C++, Java …) and many other systems. In this paper, we present an improvement of the delete algorithm of this kind of binary search tree. The proposed algorithm is very promising since it colors differently the tree while reducing color changes by a factor of about 29%. Moreover, the maintenance operations re-establishing Red-Black tree balance properties are reduced by a factor of about 11%. As a consequence, the proposed algorithm saves about 4% on running time when insert and delete operations are used together while conserving search performance of the standard algorithm.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
اليوم، أصبحت أشجار الأحمر والأسود بنية بيانات شائعة تستخدم عادةً لتنفيذ القواميس والمصفوفات الترابطية وجداول الرموز داخل بعض المترجمات (C++ و Java ...) والعديد من الأنظمة الأخرى. في هذه الورقة، نقدم تحسينًا لخوارزمية الحذف لهذا النوع من شجرة البحث الثنائية. الخوارزمية المقترحة واعدة للغاية لأنها تلون الشجرة بشكل مختلف مع تقليل تغيرات اللون بعامل يبلغ حوالي 29 ٪. علاوة على ذلك، يتم تقليل عمليات الصيانة التي تعيد إنشاء خصائص توازن شجرة الأحمر والأسود بعامل يبلغ حوالي 11 ٪. ونتيجة لذلك، توفر الخوارزمية المقترحة حوالي 4 ٪ في وقت التشغيل عند استخدام عمليات الإدراج والحذف معًا مع الحفاظ على أداء البحث للخوارزمية القياسية.Translated Description (French)
Résumé Aujourd'hui, les arbres rouge-noir deviennent une structure de données populaire généralement utilisée pour implémenter des dictionnaires, des tableaux associatifs, des tables de symboles au sein de certains compilateurs (C++, Java ...) et de nombreux autres systèmes. Dans cet article, nous présentons une amélioration de l'algorithme de suppression de ce type d'arbre de recherche binaire. L'algorithme proposé est très prometteur car il colore différemment l'arbre tout en réduisant les changements de couleur d'un facteur d'environ 29%. De plus, les opérations de maintenance rétablissant les propriétés d'équilibre des arbres rouge-noir sont réduites d'un facteur d'environ 11 %. En conséquence, l'algorithme proposé permet d'économiser environ 4 % sur le temps d'exécution lorsque les opérations d'insertion et de suppression sont utilisées ensemble tout en conservant les performances de recherche de l'algorithme standard.Translated Description (Spanish)
Resumen Hoy en día, los árboles rojo-negro se están convirtiendo en una estructura de datos popular que se utiliza normalmente para implementar diccionarios, matrices asociativas, tablas de símbolos dentro de algunos compiladores (C++, Java ...) y muchos otros sistemas. En este artículo, presentamos una mejora del algoritmo de eliminación de este tipo de árbol de búsqueda binario. El algoritmo propuesto es muy prometedor, ya que colorea el árbol de manera diferente y reduce los cambios de color en un factor de aproximadamente el 29%. Además, las operaciones de mantenimiento que restablecen las propiedades de equilibrio del árbol rojo-negro se reducen en un factor de aproximadamente el 11%. Como consecuencia, el algoritmo propuesto ahorra aproximadamente un 4% en tiempo de ejecución cuando las operaciones de inserción y eliminación se utilizan juntas, al tiempo que conserva el rendimiento de búsqueda del algoritmo estándar.Files
latest.pdf.pdf
Files
(2.1 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:3eb7de7328074dc85805a384c3bddff1
|
2.1 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- تحسين خوارزمية حذف الشجرة الحمراء والسوداء
- Translated title (French)
- Amélioration de l'algorithme de suppression de l'arbre rouge-noir
- Translated title (Spanish)
- Mejora del algoritmo de eliminación del árbol rojo-negro
Identifiers
- Other
- https://openalex.org/W4200536528
- DOI
- 10.21203/rs.3.rs-1194654/v1