Update: Code bisa di-download di bawah Zed234Tree.zip
Ah, akhirnya bisa juga mereply pertanyaan kolega sebelah saya (Risman Adnan's What's Your Favorite Data Structure?) walaupun telat banget :)
Data Struktur favorit saya adalah "Balanced Tree", dan dalam blog ini saya akan paparkan contoh implementasi dengan 2-3-4 Tree.
Kalo Binary Tree, mungkin rekan-rekan sudah banyak yg tahu:
1. Problem dgn Binary Tree adalah dalam hal "worst-case scenario", dimana data yg dimasukkan sudah dalam order (entah ascending atau descending):
Yg terjadi di atas adalah Binary Tree menjadi seperti LINKED LIST, dan waktu asymptot berubah dari O(logN) menjadi O(N)...
2. Problem kedua dgn Binary Tree adalah karena sifatnya yg biner, satu node hanya boleh punya maksimal 2 children. Dengan banyaknya data, berarti semakin tinggi level tree tersebut (level = jarak dari root sampai ke children paling bawah). Semakin banyak data, semakin besar level tree.
Kenapa 2-3-4 Tree?
- 2-3-4 Tree dalam worst-case-scenario memberikan:
Search = O(logN)
Insert = O(logN)
Delete = O(logN) Tentunya dibandingkan Linked List [Search O(N), Insert O(1), Delete O(N)] lebih baik. Namun masih kalah dibandingkan dengan Hashtable (yg memiliki O(1) untuk Search, Insert, Delete). Tapi 2-3-4 Tree ini berguna untuk sesuatu (lihat Point 3).
- 2-3-4 Tree adalah multiway tree, artinya dalam 1 node bisa lebih dari 1 data item, dan 1 node bisa memiliki lebih dari 2 children.
- Salah satu spesies special dari multiway tree adalah B-Tree. B-Tree ini sangat bagus untuk external storage. Pertama kali dipaparkan oleh Bayer & McCreight di 1972 paper:
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
Oleh karena sifat O(logN) nya dlm semua aspek, B-Tree digunakan untuk filesystem. Contoh filesystem yg implementasinya menggunakan B-Tree:
- Apple HFS (http://developer.apple.com/technotes/tn/tn1150.html)
- ReiserFS ("All of reiserfs is a single B-tree..." http://zork.net/~nick/mail/why-reiserfs-is-teh-sukc)
- Windows NTFS ("Because of the B-tree structure, NTFS outperforms FAT for large folders because FAT must scan all file names in a large folder before listing all of the files..." http://technet2.microsoft.com/windowsserver/en/library/8cc5891d-bf8e-4164-862d-dac5418c59481033.mspx?mfr=true)
Ouch, sepertinya developer FAT tidak pernah belajar data struktur dulu waktu coding filesystem :)
Ok, enuff teori dan ngeceng-in orang... mari kita lihat apa itu 2-3-4 Tree.
Nama 2-3-4
Untuk non-leaf nodes (non-leaf adalah nodes yg paling bawah dan tidak punya children), berikut properties-nya:
a. Node dgn 1 data item selalu punya 2 children.
b. Node dgn 2 data item selalu punya 3 children.
c. Node dgn 3 data item selalu punya 4 children.
Lihat gambar dibawah:
Tiap node memiliki 3 data item. Jika 3 data item ini terisi semua, maka akan ada 4 node children dibawahnya. Contohnya untuk gambar 4-node diatas: (27|33) lebih kecil dari 40, (51|55) diantara 40-62, (70|75w) diantara 62-80, dan (90|99) lebih besar dari 80.
Search 2-3-4
Searching di 2-3-4 Tree mirip dgn search di BINARY TREE. Contoh untuk gambar 4-node diatas, kita akan mencari 75:
1. Masuk ke node (40|62|80). 75 tidak ditemukan.
2. Karena 75 diantara 62-80, kita masuk ke node (70|75). Disini 75 ditemukan.
Insert 2-3-4 (Tanpa Split)
Jika node belum full (ingat, maksimum 3 data item), maka data dapat dimasukkan di posisi yang sesuai. Lihat gambar di bawah:
Insert 2-3-4 (Dgn Split)
Jika node sudah full ketika mencari insertion point, maka split diperlukan agar tree tetap balance:
1. Node baru dibuat di sebelah kanan node yg di-split.
2. Data item C dari (A|B|C) pindah ke node baru.
3. Data item B dari (A|B|C) pindah ke parent.
4. Data item A dari (A|B|C) tetap.
5. Children ketiga dan keempat dari node yg di-split dipindahkan ke node baru.
Lihat gambar dibawah untuk jelasnya:
Insert 2-3-4 (Dgn Split di Root)
Jika root sudah full ketika mencari insertion point, maka dibutuhkan root baru pada waktu split agar tree tetap balance:
1. Node baru dibuat dan menjadi parent node yg di-split.
2. Node baru dibuat di sebelah kanan node yg di-split.
3. Data item C dari (A|B|C) pindah ke node baru.
4. Data item B dari (A|B|C) pindah ke root baru.
5. Data item A dari (A|B|C) tetap.
6. Children ketiga dan keempat dari node yg di-split dipindahkan ke node baru yg di-kanan.
Lihat gambar dibawah untuk jelasnya:
Code
Update: Code bisa di-download di bawah Zed234Tree.zip
Satu Node berisi maksimum 3 DataItem.
Satu Node me-link maksimum 4 Children.
Class yg diciptakan untuk implementasi adalah DataItem, Node, dan Zed234Tree<T>.
Zed234Tree<T> dibuat Generics agar bisa menyimpan data type apapun tanpa kena boxing...
DataItem Class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class DataItem
{
private T _data;
public T Data
{
get {
return _data; }
set { _data =
value; }
}
public DataItem(T val)
{
_data = val;
}
public override string ToString()
{
return string.Format(
"|{0}", _data.ToStrin
g());
}
}
Node Class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
public class Node
{
private const int ORDER = 4;
private int _numOfDataItems = 0;
private Node _parent;
private Node[] _children =
new Node[ORDER];
private DataItem[] _items =
new DataItem[ORDER
- 1];
public void ConnectChild(
int childNum, Node ch
ild)
{
_children[childNum] = child;
if (child !=
null) child._parent =
this;
}
public Node DisconnectChild(
int childNum)
{
Node tempNode = _children[childNum];
_children[childNum] =
null;
return tempNode;
}
public Node GetChild(
int childNum)
{
return _children[childNum];
}
public Node Parent
{
get {
return _parent;
}
}
public bool IsLeaf
{
get {
return (_children[0] ==
null) ?
true :
false;
}
}
public int DataItemsCount
{
get {
return _numOfDataItems;
}
}
public DataItem GetDataItem(
int index)
{
return _items[index];
}
public bool IsFull
{
get {
return (
this.DataItemsCount == ORDER -
1) ?
true :
false;
}
}
public int FindItem(T key)
{
for (
int i = 0; i < ORDER - 1; ++i)
{
if (_items
==
null)
break;
else if (_items
.Data.CompareTo(key)
== 0)
return i;
}
return -1;
}
public int InsertItem(DataItem newItem)
{
++_numOfDataItems;
T newKey = newItem.Data;
for (
int i = ORDER - 2; i >= 0; i--)
{
if (_items
==
null)
continue;
else {
T currKey = _items
.Data;
if (newKey.CompareTo(currKey) < 0)
_items[i + 1] = _items
;
else {
_items[i + 1] = newItem;
return i + 1;
}
}
}
_items[0] = newItem;
return 0;
}
public DataItem RemoveItem()
{
DataItem temp = _items[_numOfDataItems - 1
];
_items[_numOfDataItems - 1] =
null;
--_numOfDataItems;
return temp;
}
public override string ToString()
{
StringBuilder sb =
new StringBuilder();
for (
int i = 0; i < _numOfDataItems; ++i)
{
sb.Append(_items
.ToString());
}
sb.Append(
"|");
return sb.ToString();
}
}
Zed234Tree Class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
using System;
using System.Collections.Generic;
using System.Text;
namespace Zed234Tree
{
public class Zed234Tree<T>
where T : IComparab
le<T>
{
public class DataItem {
. . .
}
public class Node {
. . .
}
private Node _root =
new Node();
public int Find(T key)
{
Node curNode = _root;
int childNumber = 0;
while (
true)
{
if ((childNumber = curNode.FindIte
m(key)) != -1)
return childNumber;
else if (curNode.IsLeaf)
return -1;
else curNode = GetNextChild(curNode
, key);
}
}
public void Insert(T val)
{
Node curNode = _root;
DataItem tempItem =
new DataItem(val);
while (
true)
{
if (curNode.IsFull)
{
Split(curNode);
curNode = curNode.Parent;
curNode = GetNextChild(curNode
, val);
}
else if (curNode.IsLeaf)
{
break;
}
else {
curNode = GetNextChild(curNode
, val);
}
}
curNode.InsertItem(tempItem);
}
public void Split(Node thisNode)
{
DataItem itemB, itemC;
Node parent, child2, child3;
int itemIndex;
itemC = thisNode.RemoveItem();
itemB = thisNode.RemoveItem();
child2 = thisNode.DisconnectChild(2);
child3 = thisNode.DisconnectChild(3);
Node newRight =
new Node();
if (thisNode == _root)
{
_root =
new Node();
parent = _root;
_root.ConnectChild(0, thisNode);
}
else parent = thisNode.Parent;
itemIndex = parent.InsertItem(itemB);
int n = parent.DataItemsCount;
for (
int i = n - 1; i > itemIndex; i--
)
{
Node temp = parent.DisconnectChild
(i);
parent.ConnectChild(i + 1, temp);
}
parent.ConnectChild(itemIndex + 1,
newRight);
newRight.InsertItem(itemC);
newRight.ConnectChild(0, child2);
newRight.ConnectChild(1, child3);
}
public Node GetNextChild(Node theNode, T v
al)
{
int i;
int numOfItems = theNode.DataItemsCoun
t;
for (i = 0; i < numOfItems; ++i)
{
if (val.CompareTo(theNode.GetDataI
tem(i).Data) < 0)
return theNode.GetChild(i);
}
return theNode.GetChild(i);
}
public void DisplayTree()
{
RecursiveDisplayTree(_root, 0, 0);
}
private void RecursiveDisplayTree(Node thi
sNode,
int level,
int childNumber)
{
Console.Write(
"Level={0}, Child={1} :
",
level, childNumber);
Console.WriteLine(thisNode.ToString())
;
int numItems = thisNode.DataItemsCount
;
for (
int i = 0; i < numItems + 1; ++i)
{
Node nextNode = thisNode.GetChild(
i);
if (nextNode !=
null)
RecursiveDisplayTree(nextNode,
level + 1, i);
else return;
}
}
}
}
CARA PENGGUNAAN:
Lihat kode Main berikut:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
static void Main(
string[] args)
{
Zed234Tree<Person> tree =
new Zed234Tree<Perso
n>();
int id = 0;
tree.Insert(
new Person(++id,
"Abdul"));
tree.Insert(
new Person(++id,
"Badut"));
tree.Insert(
new Person(++id,
"Cica"));
tree.Insert(
new Person(++id,
"Dani"));
tree.Insert(
new Person(++id,
"Eka"));
string line;
while (
true)
{
Console.Write(
"(S)how, (I)nsert, (F)ind: ");
char c = Console.ReadLine().ToLower()[0];
switch (c)
{
case 's':
tree.DisplayTree();
break;
case 'i':
Console.Write(
"Enter name: ");
line = Console.ReadLine();
tree.Insert(
new Person(++id, line)
);
break;
case 'f':
Console.Write(
"Find name: ");
line = Console.ReadLine();
Person p =
new Person(++id, line);
int found = tree.Find(p);
if (found != -1)
Console.WriteLine(
"Found: " +
p);
else Console.WriteLine(
"NOT Found:
" + p);
break;
default:
Console.WriteLine(
"Type s, i, or f
only.");
break;
}
}
}
Person Class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using System;
using System.Collections.Generic;
using System.Text;
namespace Zed234Tree
{
class Person : IComparable<Person>
{
private int _id;
private string _name;
public int Id
{
get {
return _id; }
set { _id =
value; }
}
public string Name
{
get {
return _name; }
set { _name =
value; }
}
public Person(
int id,
string name)
{
Id = id;
Name = name;
}
public override string ToString()
{
return string.Format(
"{0} - {1}",
Name, Id);
}
#region IComparable<
string> Members
public int CompareTo(Person other)
{
int res =
this.Name.ToLower()
.CompareTo(other.Name.ToLower());
if (res < 0)
return -1;
else if (res == 0)
return 0;
else return 1;
}
#endregion
}
}
Jika di-run dan muncul output berikut:
Bisa digambarkan tree-nya seperti berikut:
Performance
Yang menarik dari 2-3-4 Tree adalah Performance Searching-nya.
Dengan menggunakan Timer Win32 (lihat blog ttg ZedTimer), saya melihat 2-3-4 Tree ini lebih cepat dari List<T> untuk Searching.
Berikut kode test saya:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
TimerAkurat t =
new TimerAkurat();
Zed234Tree<Person> tree1 =
new Zed234Tree<Person>(
);
List<Person> list1 =
new List<Person>();
Person zeddy =
new Person(0,
"Zeddy");
const int N = 500000;
t.Reset(); t.Mulai();
for (
int i = 0; i < N; i++)
list1.Add(RandomPerson());
t.Berhenti();
Console.WriteLine(
"\nInsertion List<T> dgn {0:N} P
ersons = {1} milidetik",
N, t.HasilDlmMilliDetik);
list1.Add(zeddy);
t.Reset(); t.Mulai();
bool res2 = list1.Contains(zeddy);
if (res2) Console.WriteLine(
"FOUND!");
t.Berhenti();
Console.WriteLine(
"Searching List<T> dgn {0:N} Per
sons = {1} milidetik",
N, t.HasilDlmMilliDetik);
t.Reset(); t.Mulai();
for (
int i = 0; i < N; i++)
tree1.Insert(RandomPerson());
t.Berhenti();
Console.WriteLine(
"\nInsertion 2-3-4 Tree dgn {0:N
} Persons = {1} milidetik",
N, t.HasilDlmMilliDetik);
tree1.Insert(zeddy);
t.Reset(); t.Mulai();
int res = tree1.Find(zeddy);
if (res != -1) Console.WriteLine(
"FOUND!");
t.Berhenti();
Console.WriteLine(
"Searching 2-3-4 Tree dgn {0:N}
Persons = {1} milidetik",
N, t.HasilDlmMilliDetik);
Berikut output-nya:
Tentunya not surprising, karena di MSDN dijelaskan bahwa List.Contains melakukan Linear Search "This method performs a linear search; therefore, this method is an O(n) operation, where n is Count." (http://msdn2.microsoft.com/en-us/library/bhkz42b3.aspx)
Sedangkan seperti saya jelaskan diatas, 2-3-4 Tree melakukan Search dlm O(logN) dan memangkas tinggi level Tree.
Konklusi
2-3-4 Tree adalah awal untuk mempelajari Balanced Tree dan Multiway Tree (B-Tree). Kode-nya pun bisa dibilang paling gampang diantara Balanced Tree lainnya.
B-Tree digunakan untuk coding External Storage, paling penting untuk FileSystem dan Database Engine. Bahkan di CodeProject pun ada yg membuat Embedded Database dgn B-Tree: http://www.codeproject.com/database/btreedbclass.asp
Dalam praktek filesystem programming, satu Node di B-Tree merupakan satu "block" di hard disk. Diatas sudah dipaparkan bagaimana 2-3-4 Tree mereduksi tingginya level tree, begitu *** di B-Tree, akan mereduksi jumlah "blocks" yg harus di-baca oleh hard disk. Selanjutnya setelah satu "block" ini ditransfer ke main memory, Insert/Delete/Search file dapat dilakukan dgn O(logN) di memory tanpa perlu disk seek time lagi, kecuali file tidak ketemu di "block" ini.
Update: Code bisa di-download di bawah Zed234Tree.zip