الشجرة الحمراء والأسود هي شجرة بحث متوازنة ثنائية. كل عقدة لديها بت تخزين لتمثيل لون العقدة ، والتي يمكن أن تكون حمراء أو أسود.
الأشجار الحمراء والأسود لها الخصائص التالية:
(1) كل عقدة حمراء أو أسود
(2) عقدة الجذر سوداء
(3) إذا كانت العقدة حمراء ، فإن ولدينها أسود
(4) لكل عقدة ، تحتوي جميع المسارات من تلك العقدة إلى أحفادها على نفس عدد العقد السوداء.
من خلال خصائص شجرة اللون الأسود الأحمر ، من الممكن أن تتضمن جميع التطبيقات القائمة على الأشجار السوداء الحمراء أن يكون وقت تشغيل التشغيل لوغاريتمي (باستثناء البحث في المدى. الوقت الإضافي الذي يستغرقه يتناسب مع عدد المفاتيح التي تم إرجاعها).
يتم تنفيذ Java's Treemap من خلال الأشجار الحمراء والأسود.
إذا لم ترسم صورة ، فمن السهل الخلط. فيما يلي رسم بياني لتوضيح عملية الإدراج للشجرة الحمراء والأسود.
بعد إدخال عقدة حمراء في الشجرة الحمراء والأسود ، سيكون هناك 6 حالات: n يمثل العقدة المدرجة ، تمثل p العقدة الأصل ، ويمثل U عقدة العم ، ويمثل G عقدة الجد ، ويمثل x عقدة التشغيل الحالية
الرمز كما يلي:
الفئة العامة RedBlackBst <key يمتد قابلة للمقارنة <key> ، value> {private node root ؛ static static النهائي النهائي الأحمر = صواب ؛ الأسود الثابت الأساسي الأسود = خطأ ؛ عقدة الفئة الخاصة {مفتاح المفتاح الخاص ؛ // مفتاح القيمة الخاصة Val ؛ // قيمة العقدة الخاصة اليسار ، اليمين ، الوالدين ؛ // اليسار واليسرى أشجار الطفل والأمهات لون منطقي خاص ؛ . this.val = val ؛ this.color = اللون ؛ }} القيمة العامة GET (مفتاح المفتاح) {node x = root ؛ بينما (x! = null) {int cmp = key.compareto (x.key) ؛ if (cmp <0) x = x.left ؛ آخر إذا (cmp> 0) x = x.right ؛ عودة أخرى x.val ؛ } إرجاع فارغ ؛ } public void put (مفتاح المفتاح ، القيمة val) {if (root == null) {// إذا كانت عقدة جذر ، قم بإنشاء العقدة كأسود = عقدة جديدة (مفتاح ، val ، null ، Black) ؛ يعود؛ } // ابحث عن عقدة موضع إدراج مناسبة = null ؛ عقدة cur = الجذر ؛ بينما (cur! = null) {parent = cur ؛ if (key.compareto (cur.key)> 0) cur = cur.right ؛ آخر cur = cur.left ؛ } node n = new node (key ، val ، parent ، red) ؛ . else parent.left = n ؛ // بعد إدخال عقدة جديدة ، يجب عليك ضبط الألوان وخصائص بعض العقد في الشجرة للتأكد من عدم تدمير ميزات الشجرة الحمراء والأسود. fixafterinsertion (n) ؛ } node node parentof (node x) {return (x == null؟ null: x.parent) ؛ } private boolean colorof (node x) {return (x == null؟ null: x.right) ؛ } العقدة الخاصة LeftOf (Node X) {return (x == null؟ null: x.right) ؛ } العقدة الخاصة اليمنى (العقدة x) {return (x == null؟ null: x.right) ؛ } private void setColor (Node X ، Boolean Color) {if (x! = null) x.color = color ؛ } private void fixafterinsertion (Node X) {بينما (x! = null && colorof (parentof (x)) == red) {node grandpa = parentof (parentof (x)) ؛ Node Parent = parentof (x) ؛ if (parent == Leftof (Grandpa)) {// case 1 || Case2 || Case3 Node Uncle = rightof (Grandpa) ؛ if (colorof (stcle) == red) {// case1 ، Uncle هو setColor أحمر (الوالد ، الأسود) ؛ // العقدة الأصل هي setColor سوداء (العم ، الأسود) ؛ // عقدة العم هي setcolor سوداء (الجد ، الأحمر) ؛ // عقدة الجد هي أحمر x = الجد ؛ // لأن عقدة الجد هي حمراء من الأسود إلى الأحمر ، والسمات الحمراء والأسود للعقدة الأصل وأسلافها بحاجة إلى إعادة تعديل} {// case2 || Case3 ، العم أسود إذا (x == rightof (parent)) {// case2 x = parent ؛ rotateleft (x) ؛ } // case3 setColor (الوالد ، الأسود) ؛ setColor (Grandpa ، Red) ؛ Rotateight (الجد) ؛ }} آخر {// case4 || الحالة 5 || Case6 Node Uncle = Leftof (Grandpa) ؛ if (colorof (العم) == أحمر) {// case4 || Case5 || case6 setColor (الوالد ، الأسود) ؛ setColor (العم ، الأسود) ؛ setColor (Grandpa ، Red) ؛ x = الجد ؛ } آخر {// case5 || Case6 ، العم أسود إذا (x == LeftOf (parent)) {// case5 x = parent ؛ الدوار (X) ؛ } // case6 setColor (الوالد ، الأسود) ؛ setColor (Grandpa ، Red) ؛ rotateleft (الجد) ؛ }}}} private void rotateleft (node x) {if (x == null) return ؛ العقدة y = x.right ؛ x.right = y.left ؛ if (y.ft! = null) y.left.parent = x ؛ y.left = x ؛ y.parent = x.parent ؛ if (x.parent == null) {root = y ؛ } آخر إذا (x.parent.left == x) {x.parent.left = y ؛ } آخر {x.parent.right = y ؛ } x.parent = y ؛ } private void rotateright (Node X) {if (x == null) return ؛ العقدة y = x.left ؛ x.left = y.right ؛ if (y.right! = null) y.right.parent = x ؛ y.right = x ؛ y.parent = x.parent ؛ if (x.parent == null) {root = y ؛ } آخر إذا (x.parent.left == x) {x.parent.left = y ؛ } آخر {x.parent.right = y ؛ } x.parent = y ؛ }}من الضروري رسم رسم تخطيطي لـ Rotateleft و Rotateletight أعلاه:
تستند المقالة أعلاه إلى مبدأ تشغيل إدخال الأشجار الأحمر والأسود وطريقة تنفيذ Java (المشاركة) التي تشاركك في كل المحتوى الذي أشاركه معك. آمل أن تتمكن من إعطائك مرجعًا وآمل أن تتمكن من دعم wulin.com أكثر.