ENGLISH

بحث في العناوين     بحث في المحتوى     بحث في اسماء الكتب     بحث في اسماء المؤلفين

القرأن الكريم وعلومه
العقائد الأسلامية
الفقه الأسلامي
علم الرجال
السيرة النبوية
الاخلاق والادعية
اللغة العربية وعلومها
الأدب العربي
الأسرة والمجتمع
التاريخ
الأدارة والاقتصاد
علم الفيزياء
علم الكيمياء
علم الأحياء
الرياضيات
الزراعة
الجغرافية
القانون
الإعلام

عدد المواضيع في هذا القسم 9764
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الضبابية
نظرية المجموعات
نظرية الزمر
نظرية الحلقات والحقول
نظرية الاعداد
نظرية الفئات
حساب المتجهات
المتتاليات-المتسلسلات
المصفوفات و نظريتها
المثلثات
الهندسة
التفاضل و التكامل
المعادلات التفاضلية و التكاملية
التحليل
التبلوجيا
نظرية الالعاب
الاحتمالات و الاحصاء
نظرية التحكم
بحوث العمليات
نظرية الكم
الشفرات
الرياضيات التطبيقية
نظريات ومبرهنات
علماء الرياضيات
الرياضيات في العلوم الاخرى
بحوث و اطاريح جامعية
هل تعلم
طرائق التدريس
الرياضيات العامة
نظرية البيان
الرياضيات : نظرية البيان :

Red-Black Tree

03:35 PM

22-5-2022

1587

Author : Bayer, R

Book or Source : "Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms." Acta Informat. 1

page : ...

+
-

Red-Black Tree

RedBlackTree

An extended rooted binary tree satisfying the following conditions:

1. Every node has two children, each colored either red or black.

2. Every tree leaf node is colored black.

3. Every red node has both of its children colored black.

4. Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.

Let n be the number of internal nodes of a red-black tree. Then the number of red-black trees for n=1, 2, ... is 2, 2, 3, 8, 14, 20, 35, 64, 122, ... (OEIS A001131). The number of trees with black roots and red roots are given by OEIS A001137 and OEIS A001138, respectively.

Let T_h be the generating function for the number of red-black trees of black-height h indexed by the number of tree leaves. Then

 T_(h+1)(x)=[T_h(x)]^2+[T_h(x)]^4,

(1)

where T_1(x)=x+x^2. If T(x) is the generating function for the number of red-black trees, then

 T(x)=x+x^2+T(x^2(1+x)^2)

(2)

(Ruskey). Let rb(n) be the number of red-black trees with n tree leaves, r(n) the number of red-rooted trees, and b(n) the number of black-rooted trees. All three of the quantities satisfy the recurrence relation

 R(n)=sum_(n/4<=n<=n/2)(2m; n-2m)R(m),

(3)

where (n; k) is a binomial coefficient, rb(1)=1rb(2)=2 for R(n)=rb(n)r(1)=r(3)=0r(2)=1 for R(n)=r(n), and b(1)=1 for R(n)=b(n) (Ruskey).


REFERENCES

Bayer, R. "Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms." Acta Informat. 1, 290-306, 1972.

Binstock, A.; and Rex, J. Practical Algorithms for Programmers. Reading, MA: Addison-Wesley, 1995.Cormen, T.; Leiserson, C.; and Rivest, R. Introduction to Algorithms. Cambridge MA: MIT Press, 1990.

Guibas, L. and Sedgewick, R. "A Dichromatic Framework for Balanced Trees." In Proc. 19th IEEE Symp. Foundations of Computer Science, pp. 8-21, 1978.

Rivest, R. L.; Leiserson, C. E.; and Cormen, R. H. Introduction to Algorithms. New York: McGraw-Hill, 1990.

Ruskey, F. "Information on Red-Black Trees." http://www.theory.csc.uvic.ca/~cos/inf/tree/RedBlackTree.html.Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, pp. 177 and 179, 1997.

Sloane, N. J. A. Sequences A001131, A001137, and A001138 in "The On-Line Encyclopedia of Integer Sequences."Wood, D. Data Structures, Algorithms, and Performance. Reading, MA: Addison-Wesley, 1993.

المولد النبوي الشريف . . . .
كيفيّة سلوك طريق الحق. . . . .
عدلٌ... لا مساواة . . . .
سيرة السيد الخرسان "رض" . . . .
الخطبة الفدكية . . . .
وصايا الرسول (صلّى اللّه عليه واله) . . . .
اجتنبوا كثيرا من الظن . . . .
وظائف المنتظرين . . . .
ثُمَّ اعْلَمْ يَا مَالكُ، أَنِّي قد . .
السلام على الرحمةِ المهداةِ من السم . .
الدين المعاملة . .
في معنى قوله تعالى:{وَمَن يُرِدْ فِ . .
معالجة الإسلام للرواسب الجاهلية . .
محاولات المشركين في الصدّ عن سبيل ا . .
ما الغاية من مشاورة النبي (صلى الله . .
قصّة وعِبرة: سرعة استجابة دعاء النب . .
علاج السرقة عند الأطفال . .
صِفاتُ المُربّي الناجحِ . .
الغضبُ المستحكَم . .
رَكيزةُ الإيمانِ لَدى الشَّبابِ . .
دَفعُ العاطلينَ إلى العَمَلِ . .
دورُ مُعلِّمَةِ رياضِ الأطفالِ . .
سُبُل اختيارِ الزوجَةِ . .
سِتُّ طرائقَ لرَفعِ مُستوى حَماسَةِ . .
علماء يعثرون على "مادة خطيرة" في ال . .
سويسرا شهدت "كارثة جليدية" خلال عام . .
الرابع والأخير في 2023.. كيف يمكنك . .
شاهد الشمس كما لم ترها من قبل . .
لأول مرة.. مصري يرأس مؤتمرا دوليا ح . .
وصول أول عينة جمعتها ناسا من كويكب . .
احتيال التبرعات الوهمية في الكوارث. . .
لمنافسة "شات جي بي تي".. سباق عربي . .
الأكياس القابلة للتحلل.. دراسة تنسف . .
تناول الموز قبل "النضج الكامل" يحمي . .
دراسة تكشف فوائد عظيمة لصعود السلال . .
هل التمارين الصباحية مفيدة لخسارة ا . .
يسبب فقدان البصر.. سحب "الدواء الخط . .
اليابان تقر عقار ليكيمبي لعلاج ألزه . .
طبيعة العلاقة الجنسية قد تكون السبب . .
"السجائر الإلكترونية" تسبب اضطراب ع . .
اللجنة التحضيريّة لمُلتقى التطبيقات . .
قسم المقام يحتفي بذكرى ولادة النبيّ . .
ضمن فعاليات أسبوع الصادقين الدولي.. . .
ضمن فعاليات أسبوع الصادقين .. العتب . .
بتوجيه ممثل المرجعية: العتبة الحسين . .
الامين العام للعتبة الحسينية: نبارك . .
سماحة الشيخ عبد المهدي الكربلائي في . .
الامين العام للعتبة العسكرية المقدس . .