Outline Struktur Data & Algoritme (Data Structures & Algorithms)
2-3 Trees
Pengantar Definisi 2-3 Tree Operasi: Search Insert Delete (a,b)-Tree
Denny (
[email protected]) Suryana Setiawan (
[email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester Genap - 2004/2005
Version 2.0 - Internal Use Only
Pengantar
SDA/TOPIC/V2.0/2
Definisi
AVL tree dalam pembahasan sebelumnya adalah salah satu suatu bentuk binary search tree yang kompleksitas operasioperasi insert, search, delete-nya logaritmik. hal tsb dicapai karena AVL berusaha untuk menyeimbangkan tree, tetapi tidak sempurna (almost balanced) Dalam kasus terburuk, AVL tree lebih tinggi 44 persen dibandingkan dengan binary tree yang seimbang dengan sempurna (perfectly balanced). Alternatif struktur hirarkis lain untuk mencapai perfect balance adalah memperbolehkan lebih dari satu search key di dalam setiap node (mempunyai anak lebih dari dua). 2-3 Tree adalah versi yang paling sederhana dan B-Tree adalah versi yang paling populer digunakan dalam sistem basis data. Kelebihan struktur ini adalah dalam kestabilan performance pencarian logaritmisnya. Sebagaimana yang kita ketahui, AVL tree masih memungkinkan adanya perbedaan performance worse-case dan best-case. SDA/TOPIC/V2.0/3
Definisi: suatu 2-3 tree adalah search tree yang Node interior adalah node-2 or a node-3 • node-2: 2 children, 1 key value • node-3: 3 children, 2 key values
Node-node leaf selalu berada pada level yang sama.
SDA/TOPIC/V2.0/4
1
Definisi
Example
Keterurutan key pada Node-2 dengan key K1: key-key di sub-tree kiri < K1 < key-key di sub-tree kanan Keterurutan pada Node-3 dengan key K1 dan K2 (K1 < K2): key-key di sub-tree kiri < K1 < key-key di sub-tree tengah key-key di sub-tree tengah < K2 < key-key di sub-tree kanan
6 2 1
4 3
8 5
SDA/TOPIC/V2.0/5
Counter-Example
1
4 3
10 8
5
9
11
13
15
Karakteristik
2
7
12 14
SDA/TOPIC/V2.0/6
6
10
12 14 9
11
13
15
Dengan definisi demkian maka apabila setiap node dalam 2-3 tree merupakan node-2 maka akan terbentuk perfect binary tree. Apabila setiap node dalam 2-3 tree merupakan node-3 maka akan terbentuk perfect ternary tree. Pertanyaan: untuk jumlah node N, berapa tinggi minimal dan maksimal dari 2-3 tree yang dapat terbentuk?
Different levels
SDA/TOPIC/V2.0/7
SDA/TOPIC/V2.0/8
2
Search a 2-3 Tree
Search for 9
Works just like any search of any search tree: Compare the target to the elements of the nodes If not found, move to the proper child Quit if the child is an external node, else repeat
Start here 6 2 1
4 3
10 8
5
12 14
7
9
11
SDA/TOPIC/V2.0/9
Search for 9
1
4 3
SDA/TOPIC/V2.0/10
10 8
5
15
Search for 9
6 2
13
7
6 Move here 9
12 14 11
13
2 15
SDA/TOPIC/V2.0/11
1
4 3
10 8
5
7
Move here 9
12 14 11
13
15
SDA/TOPIC/V2.0/12
3
Insert
Penyisipan Suatu Key K
We need a way to insert so as to: Preserve the search tree properties Keep all external nodes at the same level We will need to figure out how to re-shift nodes with each inset to accomplish this We want to make sure we spend no more than O(log n) time on the re-shifting
Mula-mula cari suatu leaf yang sesuai untuk menempatkan K tersebut. Masukanlah key tersebut pada node leaf tersebut. Kita sebut secara umum node ini sebagai P. Selanjutnya terdapat kasus-kasus pada P. Jika node P sebelumnya adalah node-2 (berisi satu key) maka operasi insert selesai karena masih di dalam kapasitas node. P kemudian menjadi node-3.
SDA/TOPIC/V2.0/13
Sample Insert: 70
SDA/TOPIC/V2.0/14
Sample Insert: 70
40
10 20
40
80
10 20
80
Insert 70 into this node
Search stops here SDA/TOPIC/V2.0/15
SDA/TOPIC/V2.0/16
4
Sample Insert: 70
Penyisipan Suatu Key K (2)
40
10 20
70 80
Jika P sebelumnya node-3, sekarang P kelebihan muatan dengan tiga key: K1, K2, dan K3 (K1 < K2 < K3), maka split / "pecah" node P (sebenarnya yang terjadi adalah, create satu node lainnya) menjadi dua node: P1 dan P2; jika P adalah internal node maka pemecahan menyertakan cabang-cabang disebelahnya P1 (node yang di sebelah kiri) ditempati oleh K1, P2 (node yang di sebelah kanan) ditempati oleh K3, sementara untuk K2 dilakukan: • jika P bukan root maka K2 disisipkan ke node parent dari P, dan pada parent P di tambahkan satu pointer baru untuk menghubungkan parent P dengan P1 dan P2. • Jika P adalah root maka create node baru untuk menempatkan K2 yang kemudian menjadi root baru dan menghubungkan pointer kiri ke P1 dan pointer kanan ke P2.
Ulangi prosedur pemeriksaan ini untuk parent P sebagai P.
SDA/TOPIC/V2.0/17
Sample Insert: 30
Sample Insert: 30
We can’t put 30 in here – we need a new node
40
10 20
SDA/TOPIC/V2.0/18
70 80
10 20
40
70 80
Search stops here SDA/TOPIC/V2.0/19
SDA/TOPIC/V2.0/20
5
Sample Insert: 30
Split the node
10
30
40
Sample Insert: 30 Insert 20 here. Since this is a 2-node, its easy to insert 20 the node
70 80
20 40
10
30
70 80
Done
SDA/TOPIC/V2.0/21
Sample Insert: 60
SDA/TOPIC/V2.0/22
Sample Insert: 60
20 40
10
30
20 40
70 80
10
Search ends here
SDA/TOPIC/V2.0/23
30
Insert 70 here. The root is already a three node – we can’t just convert it to make room. We need to split the root.
60
80
Split the node
SDA/TOPIC/V2.0/24
6
Sample Insert: 60
Runtime
40
We are working out way up the tree At each level, we may split a node and/or swap a value • Constant time
10
20
70
30
60
log n levels Takes O(log n) time
80
SDA/TOPIC/V2.0/25
Delete
SDA/TOPIC/V2.0/26
Penghapusan suatu Key K
We also need to be able to delete nodes so as to: Preserve the search-tree structure Keep all leaf nodes at the same level As always, we want to accomplish this in O(log n) time Trick: Cari node yang berisi key tersebut. Jika node ini bukan leaf, maka cari node leaf yang berisikan key yang merupakan inorder predecessor dari K misalnya L dan memindahkan L tersebut ke tempat K semula. Masalahnya menjadi menghapus key dalam leaf. Untuk selanjutnya node leaf ini kita sebut P secara umum. P awalnya bisa merupakan node-2 atau node3, sehingga setelah dihapus menjadi bersisa satu key atau kosong. SDA/TOPIC/V2.0/27
Jika P adalah node-3 (berisi 2 key), setelah dihapus masih bersisa satu key. proses selesai. Jika P adalah node-2 (berisi 1 key), setelah dihapus menjadi kosong: jika P adalah root, maka hapus node P, dan selesai jika P bukan root, maka terdapat kasus-kasus yang masing-masing memerlukan transformasi yang berbeda: • Kasus 1: P memiliki sibling tepat di kirinya yang memiliki 2 key. Sibling tersebut adalah Q dan kedua key adalah K1 dan K2 (dimana K1 < K2), maka apabila key yang memperantarainya di node ayah P adalah K3 maka dilakukan rotasi: K3 menempati P, K2 menggantikan K3, dan K1 tinggal sendirian di Q. Perpindahan ini disertai oleh perpindahan subtreesubtree yang berkaitan dengan key ybs. SDA/TOPIC/V2.0/28
7
Penghapusan suatu Key K
Penghapusan suatu Key K
jika tidak (bukan root) maka terdapat kasus-kasus yang masing-masing memerlukan operasi transformasi yang berbeda: Kasus 1: P memiliki sibling tepat di kirinya yang memiliki 2 key. Sibling tersebut adalah Q dan kedua key adalah K1 dan K2 (dimana K1 < K2), maka apabila key yang memperantarainya di node ayah P adalah K3 maka dilakukan rotasi: K3 menempati P, K2 menggantikan K3, dan K1 tinggal sendirian di Q. Perpindahan ini disertai oleh perpindahan subtreesubtree yang berkaitan dengan key ybs. Kasus 2: P tidak memenuhi kasus 1, tapi memiliki sibling tepat di kanannya yang memiliki 2 key sibling tersebut adalah R dan kedua key adalah K1 dan K2 (di mana K1 < K2). Apabila ada dan key K3 di ayah P memperantarai P dan R maka dilakukan rotasi: K3 menempati P, K1 menggantikan K3, dan K2 tinggal sendirian di R.
Kasus 3: P tidak memenuhi kasus 1 dan 2, tapi memiliki sibling tepat dikirinya yang hanya memiliki 1 key. Misalkan sibling tersebut adalah Q tersebut dan S adalah node ayah dari P dan Q. Pindahkan key yang memperantarai P dan Q dalam S ke Q sehingga kemudian Q berisi dua key, serta P dapat di hapus berikut pointer pada S. Kasus 4: P tidak memenuhi hasus 1, 2, dan 3, tapi memiliki sibling tepat dikanannya yang hanya memiliki 1 key. Misalkan sibling tersebut adalah Q tersebut dan S adalah node ayah dari P dan Q. Pindahkan key yang memperantarai P dan Q dalam S ke Q sehingga kemudian Q berisi dua key, serta P dapat di hapus berikut pointer pada S. Khusus pada kasus 3 atau 4, node S sekarang bisa menjadi kosong atau masih bersisa 1 key, maka jika S menjadi kosong lanjutkan proses dengan S sekarang sebagai P.
SDA/TOPIC/V2.0/29
Delete 70
SDA/TOPIC/V2.0/30
Delete 70
50 80
10 20
60 70
50 80
90 95
10 20
Find the node
60
90 95
Karena P adalah node-3 (berisi 2 key), setelah dihapus masih bersisa satu key. proses selesai. SDA/TOPIC/V2.0/31
SDA/TOPIC/V2.0/32
8
Delete 90
Delete 90
50 80
10 20
60
50 80
90 95
10 20
Find the node
60
90 95
Karena P adalah node-3 (berisi 2 key), setelah dihapus masih bersisa satu key. proses selesai. SDA/TOPIC/V2.0/33
Delete 90
SDA/TOPIC/V2.0/34
Delete 60
50 80
10 20
60
50 80
95
10 20
60
95
Find node
SDA/TOPIC/V2.0/35
SDA/TOPIC/V2.0/36
9
Delete 60
Delete 60 20 80 50 80 10
10 20
50
95
95
Remove value Now we need to remove or refill the “empty” node Î Kasus 1
Kasus 1. Since the left sibling is a three-node, we refill the empty node with a rotation from the left sibling If the left sibling is a two-node and the right sibling is a three-node (kasus 2), we refill the empty node with a rotation from the right sibling
SDA/TOPIC/V2.0/37
Delete 60
SDA/TOPIC/V2.0/38
Delete 95 S 20 80 20 80 Q 10
10
50
P 50
95
95 Kasus 3: P memiliki sibling tepat dikirinya yang hanya memiliki 1 key. Misalkan sibling tersebut adalah Q tersebut dan S adalah node ayah dari P dan Q. Pindahkan key yang memperantarai P dan Q dalam S ke Q sehingga kemudian Q berisi dua key, serta P dapat di hapus berikut pointer ke P pada S. SDA/TOPIC/V2.0/39
SDA/TOPIC/V2.0/40
10
Delete 95
Delete 50
20
10
20
50 80
10
50 80
Find node
SDA/TOPIC/V2.0/41
Delete 50
SDA/TOPIC/V2.0/42
Delete 10 S
20
P
Q 10
10
20
80
80 Kasus 4: P memiliki sibling tepat dikanannya yang hanya memiliki 1 key. Misalkan sibling tersebut adalah Q tersebut dan S adalah node ayah dari P dan Q. Pindahkan key yang memperantarai P dan Q dalam S ke Q sehingga kemudian Q berisi dua key, serta P dapat di hapus berikut pointer ke P pada S. SDA/TOPIC/V2.0/43
Node S menjadi kosong, lanjutkan proses dengan S sekarang SDA/TOPIC/V2.0/44 sebagai P.
11
Delete 10
Delete 10 P
20 80
20 80
Karena P adalah root, hapus node P. (combine)
SDA/TOPIC/V2.0/45
Components of a Delete
SDA/TOPIC/V2.0/46
(a,b)-Tree
In general, there are two things that may need to be done in a delete: Rotations
• Takes constant time • We will never need to do more than one of these
Combining node
• Takes constant time • When we combine, we move up the tree and deal with the parent node • Never need to do more than O(h) combines
Generalisasi dari 2-3 Tree adalah (a,b)-tree yaitu suatu tree di mana setiap internal nodenya dapat memiliki a atau a+1 atau a+2 atau . . . atau b cabang serta (a < b) node leaf selalu berada pada level yang sama. Penyisipan dan penghapusan data mirip dengan operasi penyisipan dan penghapusan pada 2-3 tree.
Overall: O(log n) time
SDA/TOPIC/V2.0/47
SDA/TOPIC/V2.0/48
12
B Trees
Summary
B-tree adalah (a,b)-tree di mana b = 2a - 1. a dan b biasanya merupakan angka-angka yang cukup besar, misalnya a = 100 dan b = 199. Key disimpan dalam internal node dan juga dalam leaf B+tree adalah variant dari B-tree di mana pada node leaf (node berisi data) disertakan suatu pointer tambahan untuk menghubungkan setiap leaf node tersebut sebagai suatu linear linked-list. Struktur ini memungkinkan akses sequential data dalam B-tree tanpa harus turun-naik pada struktur hirarkisnya. Key hanya disimpan dalam leaf
SDA/TOPIC/V2.0/49
A search tree can be generalized past binary trees Allows to reduce the actual height of the tree 2-3 Trees are a type of generalized search tree Each node has two or three children All external nodes are at the same level • h = O(log n)
SDA/TOPIC/V2.0/50
What’s Next
B Trees
SDA/TOPIC/V2.0/51
13
