# data[].attributes.body
Farrel Antonius - 2501960575
Yoel Eliawan K - 2502018266
Tatras Kenno - 2502031261
Nicholas Tristan - 2502000016
Caroline Dominica - 2502035801

Red-Black Tree (RBT) adalah sebuah BST (binary search tree) dimana tiap simpul memiliki atribut warna yang bernilai merah atau hitam.

Red black tree memiliki 4 ciri-ciri yaitu:
1. Node memiliki 2 warna, yaitu merah dan hitam.
2. Root akan selalu berwarna hitam
3. Semua node eksternal akan berwarna hitam
4. Jika sebuah node berwarna merah, maka anak nodenya akan berwarna hitam.

Insertion:
- Periksa apakah pohon itu kosong atau tidak. Jika pohon kosong, maka masukkan node baru dan warnai sebagai Hitam. (Karena Root Node harus selalu berwarna Hitam)

- Jika tidak jika Pohon tidak kosong maka masukkan simpul baru sebagai simpul daun ke ujung dan warnai sebagai Merah.

- Jika induk dari node baru adalah Merah dan node tetangganya (induk) juga Merah maka Balikkan warna tetangga dan Orang Tua dan Kakek-Nenek (Jika bukan Root Node Jika Tidak, Balik warna Induk dan tetangga saja) yaitu, Hitam.

- Jika induk dari node baru adalah Merah dan node tetangganya (induk) kosong atau NULL, maka Putar (rotasi Kiri-Kiri atau Kiri-Kanan) node dan induk baru.

Ada dua jenis rotasi yang akan berlaku- Rotasi Kiri Kiri dan Rotasi Kiri Kanan. Rotasi hanya akan berlaku dalam beberapa kondisi. Syaratnya adalah

- Jika induk dari node baru adalah Merah dan node tetangga kosong atau NULL, maka putar rotasi kiri atau kanan.

- Dalam Rotasi Kiri-Kiri balik warna orang tua dan kakek-nenek. Jadikan orang tua sebagai Kakek-nenek dan kakek-nenek sebagai anak.

Deletion :
Syarat untuk deletion dalam red black tree, yaitu:
1. Delete node seperti di binary tree (jika node mempunyai 2 child, gantikan kedudukan node yang telah didelete tersebut dengan node terbesar disebelah kiri atau node terkecil disebelah kanan.
2. Delete node berwarna hitam akan menyebabkan keseimbangan black height* terganggu.
3. Token double black menggantikan posisi node black yang dihapus.
4. Token double black pada node merah (red) mengubah warna jadi hitam, dan token akan dihapus
5. Token double black pada root yang sudah pasti berwarna hitam dapat dihapus, karena tidak ada pengaruh (jika data hanya satu saja)
6. Deletion leaf red dapat langsung dilakukan, karena tidak menggangu keseimbangan black height.
7. Dari node hitam yang akan dihapus:
a). Jika sibling berwarna merah, maka tukar warna parent dan sibling, dan rotasi dari parent .
b). Jika sibling dan 2 anaknya hitam, maka ubah warna sibling jadi merah.
c). Jika sibling hitam dan salah satu anaknya merahj, maka lakukan rotasi (single maupun double).

# data[].attributes.body
2540115225 - Calvin Anacia Suciawan

2501984341 - William Ng

2502017591 - Bagas Dwi Putra Majid

Red Black Tree adalah varian dari binary tree yang melakukan self balancing dengan indentifikasi warna merah dan hitam.

Properti:
- Root harus hitam
- Setiap node baru harus merah
- Node merah = Parent hitam dan sebaliknya
- Jika melanggar salah satu dari yang di atas maka akan dilakukan rotation dan color change karena terjadi violation.

Insertion:
- Node baru selalu berwarna merah
- Setelah di insert akan di cek bila parentnya hitam maka violation tidak terjadi, sedangkan bila parent merah maka violation terjadi dan harus dilakukan rotation atau color change.

Deletion:
- Bila node yang didelete berwarna merah dan childnya hitam maka tinggal digantikan oleh childnya
-Bila node yang didelete berwarna hitam dan childnya merah maka akan digantikan dengan childnya dan dilakukan color change.
- Bila node yang diganti warnanya sama - sama hitam maka siblingnya harus diubah menjadi merah dan parentnya jadi hitam.

# data[].attributes.body
Kelompok:
-Gregorius Michael Tanlain – 2501998920

-George Williams Arthur – 2501994563

-Georgius Vito Raditya - 2501986656

Binary Search Tree sama dengan Red Black Tree jika:
1. Setiap node memiliki warna, baik merah atau hitam.
2. Root berwarna hitam secara default.
3. Semua node leaf berwarna hitam.
4. Jika sebuah node berwarna merah, maka kedua children berwarna hitam.

Insert:
1. Jika tree kosong, maka dibuat node baru sebagai root node dengan warna hitam.

2. Jika tree tidak kosong, maka kita buat node baru sebagai node leaf dengan warna merah.

3. Jika parent dari node baru berwarna hitam, maka exit.

4. Jika parent dari node baru berwarna merah, maka kita harus memeriksa warna parent sibling dari node baru

Deletion:
1. Dilakukan aturan BST untuk deletion.
2.
Kasus 1: Jika node yang akan dihapus berwarna merah, kita cukup menghapusnya.
Kasus 2: Jika root node juga hitam ganda, maka cukup hapus hitam ganda dan buat menjadi hitam tunggal.
Kasus 3: Jika sibling ganda hitam itu hitam dan kedua children hitam.
-Hapus node hitam ganda.
-Tambahkan warna node ke parent node (P).
> Jika warna P merah maka menjadi hitam.
>Jika warna P hitam, maka menjadi hitam ganda.
-Warna sibling hitam berubah menjadi merah.
-Jika masih muncul situasi hitam ganda, maka akan diterapkan kasus lain.
Kasus 4: Jika sibling hitam ganda adalah Merah.
-Tukar warna parent dan sibling.
-Putar parent node ke arah hitam ganda.
-Ajukan kembali kasus.
Kasus 5: Jika sibling hitam ganda berwarna hitam, sibling child yang jauh dari hitam ganda adalah hitam, tetapi child yang dekat dengan hitam ganda berwarna merah.
-Tukar warna sibling hitam ganda dan sibling child yang lebih dekat ke node hitam ganda.
-Putar sibling ke arah yang berlawanan dari hitam ganda.
-Terapkan kasus 6
Kasus 6: Jika sibling hitam ganda itu hitam, far child adalah Merah
-Tukar warna parent dan node sibling.
-Putar parent ke arah Hitam Ganda
-Hapus Hitam Ganda
-Ubah warna Merah menjadi hitam.

# data[].attributes.body
Nicholas Baron Bramantyo - 2502033355

Rivele Rigel Soputra - 2502004771

Albert Geoffrey Gunawan - 2501996934

Properti:

setiap node memiliki warna merah / hitam

default hitam ( warna node)

node eksternal hitam

jika nodenya merah, kedua anaknya hitam.

Tidak ada node merah sebagi parent

Insertion:
Setiap node baru yang disisipkan selalu berwarna MERAH. Jika melanggar properti Red Black Tree (Violation yang berarti warna parent adalah merah), maka akan dilakukan recolor dan rotation. Tidak ada node merah yang boleh memiliki parent merah. Rotasi dan recoloring, hanya terjadi pada node yang di-insert, node parent dan greatparent.

Deletion:
Prinsip Deletion sama seperti deletion pada AVL Tree

Jika yang di-delete adalah node merah, maka akan digantikan oleh child-nya yg hitam

Jika terjadi imbalance setelah deletion, maka akan dilakukan rotasi

Jika node yang diganti sama-sama hitam, maka siblingnya akan diganti jadi merah.

Jika node yang dihapus berwarna hitam, dan anakannya merah, maka akan digantikan dengan child-nya dan warna child-nya akan menjadi hitam.

Jika parent dihapus, ada kemungkinan warna uncle bakal berubah.

# data[].attributes.body
Michael Haryanto - 2502019584
Dwiko Adani - 2502038532
Riccardo - 2502017572
Alvin - 2502045380
Aymeric Russel Taylor - 2502132885

Ciri-Ciri:
- Setiap node memiliki warna hitam atau merah
- Root dari RB Tree akan selalu hitam
- Node eksternal selalu black
- Jika node parent adalah merah, maka kedua anaknya akan berupa hitam
- Tidak ada parent yang berwarna merah yang memiliki child merah

Proses Insert :
Proses Insert pada RBT sama seperti proses Insert pada BST, namun memiliki beberapa aturan berikut :
- Root harus berwarna hitam
- Setiap node baru harus berwarna merah.
- Jika parent hitam, maka tidak terjadi violation.
- Jika parent berwarna merah, maka terjadi violation dan harus di fix.
- Jika uncle berwarna merah, maka ganti warna parent dan uncle ke warna hitam dan ganti warna grandparent ke warna merah.

Proses Search :
Proses search dalam RB Tree hampir sama dengan BST.
Mulai dari akar.
Bandingkan elemen penyisipan dengan root, jika kurang dari root, maka rekursi untuk kiri, yang lain rekursi untuk kanan.
Jika elemen yang akan dicari ditemukan di mana saja, kembalikan true, jika tidak, kembalikan false.
(Sumber : https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/)

Proses Delete :
Proses delete dalam RB Tree hampir sama dengan BST, tetapi dengan aturan tertentu.
Aturan-aturan tersebut adalah:
1. Jika node yang di-delete memiliki sub-tree, maka akan diganti dengan node paling kanan di sub-tree kiri atau node paling kiri di sub-tree kanan.
2. Anggap node yang ingin di-delete adalah P dan anak-nya adalah A.
Jika P adalah merah, maka langsung diganti dengan A.
Jika P adalah hitam dan A adalah merah, maka P diganti dengan A dan A diubah menjadi hitam.
Jika P dan A adalah hitam, maka P diganti menjadi C.
Posisi C akan ditandai sebagai X (double-black), anggap parentnya O, Sibling dari parent tersebut adalah S, Sl left child dari Sibling dan Sr right child dari Sibling.
Jika S merah, maka
Warna pada X dan O diganti, dan rotate pada O
Jika S, Sl, dan Sr adalah hitam, maka
Ubah S menjadi merah
Jika S hitam dan Sl atau Sr adalah merah, maka
Single rotate ataupun Double rotate lalu hapus X.

# data[].attributes.body
2501961180 - Muhammad Brahmantyo Oktaviga

2540120345 - Fabian Putera Djaja

2501960902 - Febrico Jonata

2540125270 - Michael Chrisandy

2502010300 - Joysun Wisesa Gunawan

Red-Black Tree (RBT) adalah sebuah self-balancing binary search tree, sama halnya dengan AVL Tree. Hal yang membedakannya adalah sebuah RBT harus mematuhi aturan-aturan ketat untuk memastikan bahwa ia tetap seimbang sehingga kompleksitas logaritmiknya tetap terjaga. Bahasa mudahnya AVL tree tapi menggunakan warna

karakteristik:
1. root dan leaves diwarnakan black
2. node baru dianggap red
3. kalau parent dari node baru adalah red, maka ada violation, tapi kalau parent adalah black aman

Insertion & deletion:
*ada 2 operasi, left and right rotation
*kurang lebih sama dengan AVL tree, namun ditambahkan kondisi pewarnaan (parent black anak red)

for insert:
Semua node yang masuk dianggap merah (kalo root jadi black)

Jika terdapat node merah yang terhubung dengan node merah lain, maka terjadi violation.

for delete:
Aturan deletion sama seperti AVL. Hanya saja setelah delete, kita perlu melakukan pengecekan terhadap warna yang ada dan melakukan rotate ulang.

# data[].attributes.body
Aldan Ramadani - 2501994872
Winnata - 2501961880
Julian Yondy - 2501982090
M.aurelio rafi - 2502032756
Galuh Yoga Bagaskara - 2502016374
Geraldo Pannanda Lutan -2502001920

Properti red black tree
-Setiap node harus berwarna merah atau hitam
-Node Root harus berwarna hitam

Perlanggaran red black tree
-Jika parent berwarna hitam, maka tidak ada pelanggaran.
-Jika parent berwarna merah, maka terjadi pelanggaran.

Cara memperbaiki pelanggaran red black tree
-biarkan simpul baru menjadi q, parentnya menjadi p, dan saudara dari parent menjadi s. jika orang tua tidak memiliki saudara, maka s berwarna hitam.

-Jika s berwarna merah, ubah p dan s menjadi hitam dan induk dari p menjadi merah.

-Jika s berwarna hitam, lakukan rotasi, ubah poros rotasi terakhir menjadi hitam dan anaknya menjadi merah.

Operasi Insertion:

a.     Cara insert sama seperti pada BST dan AVL

b.     Node yang baru diinsert selalu berwarna merah.

c.     Jika node yang baru diinsert parentnya hitam maka, tidak apa-apa

d.     Jika node yang baru diinsert parentnya merah maka,terjadi violation:

i.      Jika uncle dari node baru berwarna hitam maka lakukan rotasi(single/double) ke arah uncle berwarna hitam tersebut dan lalu lakukan recolor menjadi parent dari hasi rotation tadi menjadi hitam dan kedua anaknya menjadi merah.

# data[].attributes.body
Stanly Finnegan - 2540129306
Aldwin Suwardjo Ng - 2501962486
Nawfal Aisy - 2502009715
Hafizh Rifqi - 2502028891
Nicholas Suryatama - 2540117413

Red Black Tree :

1. Setiap node memiliki warna, baik merah atau hitam.

2. Root berwarna hitam secara default.

3. Semua node eksternal berwarna hitam.

4. Jika sebuah node berwarna merah, maka kedua anaknya berwarna hitam.

(Tidak ada node merah yang memiliki induk merah.)
5. Node baru harus berwarna merah.
6. Node akan recoloring untuk menyesuaikan sesuai levelnya
7. Jika deletion maka node yang dilakukan recoloring hanya Parent dan Grandparentnya saja

Red Black Tree Operations: Insertion

Insert node baru seperti di binary search tree. Node yang baru di insert berwarna merah.

Menyelesaikan violasi pada red black tree

1. Jika parent berwarna hitam, tidak ada violasi.

2. Jika parent berwarna merah, terdapat violasi.

Memperbaiki violasi
1. Biarkan simpul baru menjadi q, induknya menjadi p, dan saudara kandung dari induk menjadi s (paman dari q). Jika orang tua tidak memiliki saudara, maka s berwarna hitam (simpul eksternal berwarna hitam).
2. Jika s berwarna merah, maka ubah p dan s menjadi hitam dan induk dari p menjadi merah.
3. Jika s berwarna hitam, lakukan single rotation atau double rotation, ubah poros rotasi terakhir menjadi hitam dan anaknya menjadi merah.

Operasi RBT: Deletion
•Menghapus node sama seperti menghapus di BST

•jika itu adalah node dengan dua anak, temukan elemen maksimum di sub-pohon kirinya atau elemen minimum di sub-pohon kanannya.

•Biarkan node yang akan dihapus menjadi M, dan anaknya menjadi C.

•Jika M berwarna merah, maka cukup ganti dengan C

•Jika M berwarna hitam dan C berwarna merah, ganti dengan C dan warnai ulang C dengan warna hitam.

•Jika M dan C berwarna hitam, ganti M dengan C.

Mari kita nyatakan C dalam posisi barunya menjadi N (ini juga disebut hitam ganda) , induknya menjadi P, saudaranya menjadi S, SL menjadi anak kiri S dan SR menjadi anak kanan S.

•Jika S berwarna merah, balikkan warna N dan P, dan putar di P.

•Jika S, SL dan SR berwarna hitam, maka warnai ulang S menjadi merah.

•Jika S berwarna hitam dan SL atau SR berwarna merah, maka lakukan double rotation atau single rotation.

# data[].attributes.body
Alfrid Sanjaya Leo Putra - 2540124785

Thessalonica Maria Luisse Rosaline - 2501974391
Jonathan Raine Wiranata - 2540124854

ciri-ciri :

-2 warna node (red & black)

-root bewarna hitam

-jika node berwarna merah maka kedua anaknya bewarna hitam
-node baru yang ditambahkan bewarna merah

-tidak ada node merah yang memiliki parent bewarna merah

-setiap path memiliki jumlah node hitam yang sama

Insertion :

-node yang ditambahkan bewarna merah

-jika parent bewarna hitam, biarkan

-jika parent bewarna merah, perlu diperbaiki :

jika sibling dari parent bewarna merah, ubah parent dan sibling menjadi hitam

jika sibling dari parent bewarna hitam, lakukan rotasi, yang menjadi grandparent berubah menjadi hitam dan kedua anaknya menjadi merah

Deletion :

-jika node yang akan di delete bewarna merah, ganti dengan anaknya

-jika node yang akan di delete bewarna hitam dan anak yang menggantikan bewarna merah, maka ubah node tersebut dengan anaknya dan jadikan warna hitam

-jika node yang akan di delete dan anak yang menggantikan bewarna hitam :

ubah node yang di delete dengan anaknya

child direposisikan ke node n dengan p sebagai parentnya

jika sibling dari node tersebut bewarna merah, balik warna dari parent dan node tersebut lalu lakukan rotasi di parentnya

jika kedua anak dari node tersebut dan siblingnya bewarna hitam, ubah node tersebut menjadi warna merah

jika sibling bewarna hitam dan salah satu anak dari node bewarna merah, lakukan single rotate atau double rotate

# data[].attributes.body
Louie Llywton
Marcellinus Brian
Jonathan Woen
Claudya Salim
Gisela Audrey Limansagita

Red-Black Tree adalah tree yang mirip/sejenis dengan Self-Balancing Tree yang bitnya kita tafsirkan dengan menggunakan warna (hitam atau merah). Warna - warna tersebut digunakan untuk memastikan tree tetap seimbang ketika melakukan proses insertion atau deletion.

Note : setiap node hanya perlu 1 bit space untuk menyimpan informasi warna

Suatu BST akan menjadi RBT jika:
1. Setiap node punya suatu warna, antara merah atau hitam
2. Root berwarna hitam secara default
3. Semua node external adalah hitam
4. Kalo node merah, maka kedua anaknya hitam
4a. Tidak ada node merah dengan parent merah
4b. Semua jalur ke external nodes mempunyai jumlah node hitam yang sama

Hal yang harus diperhatikan ketika insert adalah : 1. jika dia adalah root maka dia berwarna hitam

Node yg diinsert adalah node berwarna merah, kecuali root yang berwarna hitam.

Ketika insert dan parent berwarna merah, cara untuk mengatasinya adalah:
- jika uncle berwarna merah, maka parent dan uncle menjadi hitam dan grandparent menjadi merah
- jika uncle berwarna hitam, maka lakukan rotasi dan mewarnai parent menjadi hitam dan anak menjadi merah.

Proses deleting node sama seperti di BST dimana :
- jika simpul dengan 2 child maka temukan elemen maksimum di sub.
- pohon kirinya atau elemen minimum di kanannya sub-pohon.
- Biarkan node yang dihapus menjadi M dan anaknya menjadi C
- Jika M berwarna merah maka ganti dengan C.
- Jika M berwarna hitam dan C warna merah, ganti dengan C dan warnai C dengan warna hitam

Kalau M dan C sama-sama hitam, maka node C akan menjadi node double black. Untuk mengatasi double black, maka yang harus dilihat adalah siblingnya. Jika sibling berwarna merah, tukar warna antara C dan siblingnya dan rotate pada siblingnya. Jika sibling berwarna hitam, maka ada 2 kondisi yang harus di cek lagi.
- Jika semua anak dari sibling berwarna hitam, maka sibling diwarnai menjadi merah.
- Jika terdapat salah satu anak dari sibling berwarna merah, maka lakukan single rotation / double rotation.

# data[].attributes.body
Kelompok 5

Pavel Ryan Susanto ( 2502019400 )

Shavarell Axel Ganendra ( 2501980860)

William Gunawan ( 2502018234 )

Ali Haidar ( 2502044043 )

Davyn Gondopratikto  ( 2540122565 )

RBL Tree

Atribut :

Warna

Nilai kunci atau isi data

Left child node

Right child node

Parent atau induk data

Poin - poin :

-     Self-Balancing Tree mirip avl namun dengan kombinasi pada recolor ( black dan red )

Setiap node wajib memiliki warna baik merah atau hitam

Node baru harus warna merah, anak dari node merah, warna hitam

Root ( induk utama )  harus hitam

Tidak ada parent warna merah (kalau ada violation)

Setiap leaf berlaku warna node hitam

Saat sub-root berwarna merah maka child berlaku warna hitam

Warna node yang sama tidak boleh muncul berurutan ( node warna merah tidak boleh berdekatan ).

Setiap pada turunan baik dari root berlaku ke salah satu turunan, node Null berlaku jumlah pada node hitam yang sama.

Memiliki 2 metode Balancing yaitu Rotation dan Recolor

Insertion :

Insert selalu berlaku awal node berwarna merah.

( left rotate atau right rotate ) Misalkan kita mau memasukkan node X, Parent dari X warna merah, sehingga terjadi violation. Maka parent dari X dan sibling dari parent X harus diubah menjadi hitam dan rootnya diubah menjadi warna merah.

Atau bisa menggunakan metode single rotation atau double rotation sesuai dengan bentuk treenya dengan mengubah parent menjadi hitam dan siblingnya menjadi merah.

Deletion :

Cara kerjanya itu sama dengan deletion yang ada di AVL Tree, namun penetapan warna berlaku pada saat operasi.

Jika ada parent yang akan delete, maka akan digantikan oleh child tetapi warna child akan diubah menjadi hitam ( warna berlainan dari warna awal )

Jika terjadi imbalance, maka akan ada rotation dan untuk beberapa kasus, warna node akan berubah.( recolor )

# data[].attributes.body
Christine Putri - 2502032705
Christopher Edbert - 2540129331
Gerald Evan Yauris - 2501999406
Stefano Vincent - 2501985086
Yoshua - 2501964472

Red black tree merupakan salah satu tipe self balancing Binary Search Tree yang juga disebut sebagai simetris binary B-tree.

Karakteristik red black tree :
1. Setiap node memiliki warna red (merah) atau black (hitam).
2. Warna node root selalu berwarna hitam.
3. Semua node leaf berwarna hitam.
4. Setiap node berwarna merah memiliki dua anak yang berwarna hitam.
5. Setiap jalur dari root ke semua leaf harus memiliki jumlah node black yang sama.

Operasi dalam Red Black Tree:

1. Searching
Proses searching pada Red Black Tree sama dengan proses searching Binary Search Tree. Karena setiap Red Black Tree adalah kasus khusus pohon biner sehingga algoritma pencarian pohon merah-hitam mirip dengan pohon biner.

https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/

2. Insertion
- Proses insertion sama dengan BST
- Node yang di-insert diberi warna merah
- Pastikan tidak ada violation
- Bila ada violation gunakan langkah berikut:
- Color Swap
- Single Rotation
- Double Rotation

3. Deletion
- Proses deletion pada RBT sama dengan deletion pada BST.
- Anggap node yang ingin dihapus adalah M dan anaknya adalah C.
- Jika M berwarna merah, maka gantikan M dengan C dan C harus hitam.
- Jika M berwarna hitam dan C berwarna merah, ganti M dengan C dan ganti warna C menjadi hitam.
- Jika M dan C berwarna hitam:
- Ganti M dengan C.
- Jika sibling berwarna merah, tukar warna sibling dan parent. Lalu lakukan single rotation pada parent.
- Jika sibling berwarna hitam dan kedua anaknya juga berwarna hitam, maka ubah warna sibling menjadi merah.
- Jika sibling berwarna merah dan salah satu anaknya berwarna merah, maka lakukan single rotation atau double rotation.

# data[].attributes.attachment_link.readable_text
Introduction:

A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the colour (red or black). These colours are used to ensure that the tree remains balanced during insertions and deletions. Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree. This tree was invented in 1972 by Rudolf Bayer.

It must be noted that as each node requires only 1 bit of space to store the colour information, these types of trees show identical memory footprint to the classic (uncoloured) binary search tree.

Rules That Every Red-Black Tree Follows:

1. Every node has a colour either red or black.

2. The root of the tree is always black.

3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).

4. Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes.

5. All leaf nodes are black nodes.

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of O(log n) for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree.

"n" is the total number of elements in the red-black tree.

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over Red-Black Tree.

How does a Red-Black Tree ensure balance?

A simple example to understand balancing is, a chain of 3 nodes is not possible in the Red-Black tree. We can try any combination of colours and see all of them violate Red-Black tree property.

A chain of 3 nodes is not possible in Red-Black Trees.
Following areNOT Red-Black Trees 30 30 30  / \ / \ / \20 NIL 20 NIL 20 NIL / \ / \ / \10 NIL 10 NIL 10 NIL Violates Violates Violates Property 4. Property 4 Property 3 Following are different possible Red-Black Trees with above 3 keys 20  20 / \ / \ 10 30 10 30 / \ / \ / \ / \ NIL NIL NIL NIL NIL NIL NIL NIL

Interesting points about Red-Black Tree:

1. Black height of the red-black tree is the number of black nodes on a path from the root node to a leaf node. Leaf nodes are also counted as black nodes. So, a red-black tree of height h has black height >= h/2.

2. Height of a red-black tree with n nodes is h<= 2 log₂(n + 1).

3. All leaves (NIL) are black.

4. The black depth of a node is defined as the number of black nodes from the root to that node i.e the number of black ancestors.

5. Every red-black tree is a special case of a binary tree.

Black Height of a Red-Black Tree :

Black height is the number of black nodes on a path from the root to a leaf. Leaf nodes are also counted black nodes. From the above properties 3 and 4, we can derive, a Red-Black Tree of height h has black-height >= h/2.

Number of nodes from a node to its farthest descendant leaf is no more than twice as the number of nodes to the nearest descendant leaf.

Every Red Black Tree with n nodes has height <= 2Log ₂(n+1)
This can be proved using the following facts:

1. For a general Binary Tree, let k be the minimum number of nodes on all root to NULL paths, then n >= 2k - 1 (Ex. If k is 3, then n is at least 7). This expression can also be written as k <= Log₂(n+1).

2. From property 4 of Red-Black trees and above claim, we can say in a Red-Black Tree with n nodes, there is a root to leaf path with at-most Log₂(n+1) black nodes.

3. From property 3 and 5 of Red-Black trees, we can claim that the number of black nodes in a Red-Black tree is at least ⌊ n/2 ⌋ where n is the total number of nodes.

From the above points, we can conclude the fact that Red Black Tree with n nodes has height <= 2Log ₂(n+1)

Search Operation in Red-black Tree:

As every red-black tree is a special case of a binary tree so the searching algorithm of a red-black tree is similar to that of a binary tree.
Algorithm:
searchElement (tree, val)
Step 1: If tree -> data = val OR tree = NULL Return tree Else If val < data Return searchElement (tree -> left, val) Else Return searchElement (tree -> right, val) [ End of if ] [ End of if ]Step 2: END

For the program, you can refer it for AVL tree.

Example: Searching 11 in the following red-black tree.

Solution:

1. Start from the root.

2. Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.

3. If the element to search is found anywhere, return true, else return false.

In this post, we introduced Red-Black trees and discussed how balance is ensured. The hard part is to maintain balance when keys are added and removed. We have also seen how to search an element from the red-black tree. We will soon be discussing insertion and deletion operations in coming posts on the Red-Black tree.

Exercise:

1) Is it possible to have all black nodes in a Red-Black tree?
2) Draw a Red-Black Tree that is not an AVL tree structure-wise?

Insertion and Deletion

Red-Black Tree Insertion
Red-Black Tree Deletion

Applications:

1. Most of the self-balancing BST library functions like map and set in C++ (OR TreeSet and TreeMap in Java) use Red-Black Tree.

2. It is used to implement CPU Scheduling Linux. Completely Fair Scheduler uses it.

3. Besides they are used in the K-mean clustering algorithm for reducing time complexity.

4. Moreover, MySQL also uses the Red-Black tree for indexes on tables.

References:

# data[].attributes.attachment_link.title
Red-Black Tree | Set 1 (Introduction) - GeeksforGeeks

# data[].attributes.attachment_link.description
Introduction: A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the colour (red or black). These colours are used to ensure that the tree remains balanced during insertions and deletions.

# data[].attributes.body
Berikut Anggota kelompok 6 :
1. 2502008523 - Veronica Dwiyanti
2. 2501963242 - Vania Paramitha S
3. 2502000174 - Reynard Octavius Tan
4. 2540121316 - Felicia Himawan
5. 2540118681 - Yonathan Handoyo

Red Black Tree Properties:

1. Setiap node harus mempunyai warna merah atau hitam sesuai dengan namanya RBT

2. Root ditetapkan sebagai warna hitam.

3. Dua node berwarna merah tidak boleh muncul berurutan yang artinya node berwarna merah harus memiliki parent dan child berwarna hitam

4. Semua node leaf berwarna hitam

5. Setiap jalur dari root ke null pointer N harus melewati jumlah node hitam yang sama. Jalur ini disebut unsuccessful search path karena jalur ini yang dilalui untuk mencari node yang tidak terdapat pada tree.

Insert:

1. Untuk insert root, warna node tersebut akan menjadi hitam dan untuk insert new node, warnanya akan menjadi merah.

2. Terdapat pelanggaran dalam aturan red black tree jika parent dari new node berwarna merah (berarti terdapat dua node berwarna merah yang berurutan)

3. Cara memperbaiki red black tree berdasarkan aturannya jika terdapat beberapa case:

4. Jika parent dari new node berwarna merah, dan parent mempunyai sibling berwarna merah maka ganti parent dan sibling menjadi warna hitam dan ancestor dari new node menjadi warna merah

5. Jika parent dari new node berwarna merah, sibling dari parent new node berwarna hitam, dan terdapat case path dari new node menuju parent sama dengan path menuju ke grandparent, maka lakukan single rotation. Kemudian parent akan menjadi warna hitam dan children berwarna merah

6. Jika parent dari new node berwarna merah, sibling dari parent new node berwarna hitam, dan terdapat case path dari new node menuju parent TIDAK sama dengan path menuju ke grandparent, maka lakukan double rotation seperti aturan AVL Tree. Kemudian pivot dari rotasi terakhir akan berwarna hitam dan childnya akan berwarna merah.

Delete:

1. Lakukan delete node dengan memilih predecessor atau successor.

2. Jika node yang ingin dihapus berwarna merah maka tidak terjadi violation

3. Jika node yang ingin dihapus berwarna hitam maka akan terjadi:

4. Jika node pengganti adalah warna hitam, node pengganti itu akan menjadi double black dan harus diubah menjadi single black. Terdapat beberapa poin:

Jika node pengganti itu bukan root, dan memiliki sibling berwarna hitam dengan sibling itu memiliki salah satu anak berwarna merah, maka dapat melakukan rotations.

Jika node pengganti itu bukan root, dan sibling berwarna hitam dan kedua anaknya hitam, lakukan pewarnaan ulang, dan ulangi untuk induknya jika induknya hitam.

Jika node pengganti itu bukan root dan salah satu anak berwarna merah, lakukan single / double rotation dan ubah warna anak menjadi hitam.

Jika node pengganti itu root, maka akan menjadi single black secara otomatis.