RED BLACK TREE

  • Root selalu warna hitam
  • External node selalu warna hitam
  • Node baru selalu warna merah
  • Node merah tidak boleh mempunyai anak warna merah

 

INSERTION

 

Picture1

Jika paman berwarna merah, maka tukar warna parent dan paman nya menjadi hitam, dan grand parent menjadi merah.

 

Picture2                         Picture3

Jika paman berwarna hitam, maka lakukan single rotation atau double rotation.

 

 

DELETION

 

Jika menghapus node berwarna merah, maka langsung hapus.

Jika menghapus node berwarna hitam, maka langsung hapus dan digantikan oleh anaknya, lalu ubah warnanya menjadi hitam.

Jika terjadi double black:

Picture4           Picture5          Picture6

 

 

2-3 TREE

Tree yang memungkinkan untuk memiliki 2 atau 3 data dlam sebuah node.

2-node : Node yang berisi 1 data dan mempunyai 2 child.

2node

3-node : Node yang berisi 2 data dan mempunyai 3 child.

3node

 

INSERTION

Data yang dimasukkan pasti masuk ke leaf.

Jika dimasukkan ke 2-node, maka langsung masukkan.

Jika dimasukkan ke 3-node, maka data tengah naik menjadi parent.

 

DELETION

Tentukan di node mana data yang ingin dihapus

Jika berada dalam 3-node, langsung hapus saja datanya.

Jika berada dalam 2-node:

I. Jika parent adalah 3-node: ambil satu data dari parent.

  • Jika sibling adalah 3-node, ambil salah satu datanya untuk dijadikan data parent.
  • Jika sibling adalah 2-node, buat parent menjadi 2-node dengan menggabungkan sibling dengan node tempat data didelete.

II. Jika parent adalah 2-node:

  • Jika sibling adalah 3-node, turunkan data parent ke node dan ambil satu data dari sibling untuk menggantikan parent.
  • Jika sibling adalah 2-node, gabungkan sibling dengan node yang dihapus datanya.