2-3 tree haqida tanişib çiqqan bölsangiz, unda node qöşişda köp şartlarni hisobga oliş kerak bölardi. Umuman, 2-3 tree'ni kodda ifodalaş qiyin edi. Red-black tree mana şu insertdagi qiyinçiliklarga yeçim sifatida keladi.

Red-black tree ham aslida 2-3 tree, lekin unda 3-node çap tarafdagi qizil boğlaniş bilan ajratiladi. Qizil çiziqli boğlaniş sababli Red-black tree binary search tree'ga öxşab qoladi.

3-node'ni red-black tree'da ifodalaş. Image credit: algs4.cs.princeton.edu

Şu yöl bilan biz 2-3 tree ustida amallarni bajariş uçun kod yoza olamiz. Va albatta, binary search tree'ning API'sidagi köp amallar ham red-black tree'da işlaydi.

2-3 tree'ni red-black tree'da ifodalaş:

Red-black tree hususiyatlari

• Qizil boğlanişlar 3-node'lar uçun yelim vazifasini ötaydi.
• Node'da ikki qizil boğlaniş bölişi mumkin emas, bu holda 4-node bölib qoladi va 2-3 tree'dagi kabi u uçta 2-node'ga ajratiladi.
• root'dan leaf'gaça barça yönalişlarda bir xil sonda qora boğlanişlar (odatiy boğlanişlar) böladi - ya'ni mukammal qora balansga ega.
• 3-node'ning katta qiymati parent'ga ötadi, şu sababli qizil boğlaniş node'ning faqat çap tarafida böladi (Biz faqat çap taraflama - Left leaning red-black tree'ni körib çiqamiz).

Red-black tree ustida amallar

Aynan red-black tree'ga tegişli bölgan amallar uçta, ularning barçasi qizil boğlanişni çap tarafga ötkaziş yoki ikki qizil boğlaniş bölgan holatda ularni qora boğlanişga özgartirişga xizmat qiladi.

Çapga buriş (Rotate left).

Ba'zi amallardan keyin qizil boğlaniş node'ning öng tarafida bölib qoladi. Şunda tree'ni töğrilaş uçun qizil boğlanişni çap tarafga ötkazişimiz kerak böladi. Çapga buriş deganda 3-node'ning ikkinçi qiymatini parent'ga ötkaziş tuşuniladi. Quyidagi rasmda tuşuntirişga harakat qilaman.

Çapga buriş (kodni biz keyinroq Javascriptda yozamiz ;))

3-node (E S) da E parent bölib turipti va S uning öng tarafiga boğlangan. Biz S ni parent qilib olamiz. Şunda E qiymat S ning çap çild'i böladi va qizil boğlaniş çapga ötadi. S parentning oldingi çap çild'i E'ning öng çild'iga ötadi.

Öngga buriş (Rotate right)

Tree'ga element qöşilgandan söng, ba'zi hollarda 3-node 4-node'ga aylanib, qizil boğlanişli çap tarafdagi ketma-ket ikki node körinişiga kelib qoladi.

C parentli (abc) 4-node.

Uni töğrilaş uçun 4-node öngga buriladi va B ikki tarafida qizil boğlanişli parent'ga aylanadi. Keyin ikki qizil çiziq qoraga özgartiriladi, ya'ni 4-node B parent bölgan 3 ta 2-node'ga ajratiladi.

Qayd etiş kerakki, öngga buriş faqatgina eng katta qiymati parent bölgan 4-node uçun amal qiladi. Boşqa holatlarda öngga burişning hojati bölmaydi.

Rangni özgartiriş (Color flip)

Öngga buriş misolida körganimiz, node'ning ikki tarafida qizil boğlaniş bölib qolganda uning rangi qoraga özgartiriladi. 2-3 tree qoidasi böyiça 4-node 3 ta 2-node'ga ajratiladi.

Yuqoridagi amallardan red-black tree'ni simmetrik tartibda, mukammal balansda uşlab turiş, şuningdek 2-3 treebilan bir xil körinişda qoldiriş uçun foydalaniladi.

Qöşiş (Insert)

Binary search tree kabi, element qöşişdan oldin u red-black tree'da qidiriladi. Topilmasa, yangi element tree'ga qöşiladi. Qöşişning birneça şakli mavjud:

2-node'ga qöşiş. Element şunçaki 2-node'ga qöşiladi va u 3-node'ga aylanadi. Agar qizil boğlaniş öng tarafda bölib qolsa, 3-node çapga buriladi (katta elementi parent böladi).

3-node'ga qöşiş.

• Qöşilayotgan element parent'dan katta bölsa, öng child sifatida qöşiladi. 3-node 4-node'ga aylanib qolgani uçun qizil boğlanişlar qoraga özgaradi.
• Qöşilayotgan element parentdan kiçik bölsa, u çap child sifatida qöşiladi. 4-node'ga aylanib qolgani uçun, öngga buriladi va qizil boğlaniş qoraga özgaradi.
• Qöşilayotgan element 3-node'ning ikki elementi orasida bölsa, kiçik elementning öng çild'i bölib qöşiladi. Öng qizil boğlanişni yöqotiş uçun pastdan birinçi va ikkinçi node'lar çapga buriladi, söng parent'i öngga buriladi. Ohirida ikki qizil boğlaniş qoraga özgaradi.

Qöşiş şakllarini umumlaştiradigan bölsak:

• Öng child qizil boğlanişda: çapga buriladi.
• Çap child va uning çap childi qizil boğlanişda: öngga buriladi.
• Ikki child qizil boğlanişda: qizil boğlaniş qoraga özgaradi.

Öçiriş (Delete)

Öçiriş qiyin bölgani uçun, töxtalib ötirmadim. Binary search tree'dagi delete funksiyasi ham red-black tree uçun işlaydi ammo bunda daraxtning uzunligi ortadi.

Tahlil

Boşqa tree'larda bölgani kabi, işlaş vaqti daraxtning uzunligiga teng. Red-black tree deyarli mukammal balansga ega bölgani uçun, time complexity kafolatlangan O(log N).

• eng yomon holatda - root'dan leaf'gaça yölda qizil va qora boğlanişlar bir xil sonda bölganda tree uzunligi ikki baravar oşadi. Uzunlik ≤ (2 LogN) böladi.
• örtaça holatda daraxt uzunligi ~ 1.00 Log N (1.00 - 1 dan kattaroq son, lekin 1 ga juda yaqin).
• eng yaxşi holatda - daraxt mukammal balansga ega bölsa, daraxt uzunligi Log N ga teng böladi.

---

Red-black tree ustida amallar uçun API yoziş - bu yerda.