binary search tree
Post on 15-Jan-2016
276 Views
Preview:
DESCRIPTION
TRANSCRIPT
Binary Search Tree
Teknik Informatika - Universitas Muhammadiyah Malang (UMM)Tahun Akademik 2010-2011
Oleh : Nur Hayatin, S.ST
Sub Topik
• Heap Tree• Binary Search Tree• AVL Tree• Red-Black Tree
Heap Tree
4
Heap Tree
• Definisi :– Heap tree adalah pohon biner yang tiap node nya
memenuhi heap property.
• Heap Property :– Kondisi 1:
Nilai pada node induk harus lebih besar ( > ) atau lebih besar sama dengan ( >= ) dari node anak.
– Kondisi 2:Nilai pada node induk harus lebih besar ( < ) atau lebih besar sama dengan ( <= ) dari node anak.
5
Contoh Heap Tree
12
8 3
12
8 12
Node 12 memiliki properti heap
12
8 14
Node 12 tidak memiliki properti heap
Node 12 memiliki properti heap
6
Sift Up• Penukaran posisi node induk terhadap node
anak yang nilainya paling besar sehingga binary tree memenuhi heap property.
• Proses ini disebut juga sifting up
14
8 12
Tree memenuhi heap property
12
8 14
Tree tidak memenuhi heap property
Sift Up
• Proses sift up ini dilakukan berulang kali hingga :– Node berada di posisi yang tepat dalam arti
nilai node tsb masih lebih kecil daripada node induknya, atau
– Prosesnya telah sampai pada node root
Jenis Heap Tree
• Berdasarkan Heap Property :– Max heap tree– Min heap tree
Max Heap Tree
• Nilai node induk (root) lebih besar atau sama dengan nilai subtree. (heap property kondisi 1)
Contoh max heap tree9
8
6 7 2 6
5 1
7
Min Heap Tree• Nilai dari node induk (root) lebih
kecil atau sama dengan nilai dari subtree. (heap property kondisi 2)
Contoh min heap tree2
4
6 7 9 3
8 6
3
Representasi Heap Tree
• Representasi Heap Tree lebih efisien menggunakan Array.
9 8 7 6 7 2 6 5 1
1 2 3 4 5 6 7 8 9 100
Contoh representasi heap tree
9
8
6 7 2 6
5 1
7
Aturan Penambahan Node
• Penambahan node baru di posisi paling kiri pada level terbawah.
• Jika level terbawah penuh, tambahkan node pada level baru.
• Harus mengikuti aturan heap property. Jika tidak lakukan sift up.
16
Contoh Penambahan Node
Tambahkan node baru
disini
Tambahkan node baru
disiniContoh 1 : penambahan node dari cabang kiri ke kanan
Contoh 2 : Penambahan nodepada level baru
Penambahan Node Pada Max Heap Tree
9
8
6 7 2 6
5 1
7
1
2 3
4 5 6 7
8 9
Penambahan Node Baru
Complete binary tree with 10 nodes.
9
8
6 7 2 6
5 1
7
7
Penambahan Node(5)
New element is 5.
9
8
6 7 2 6
5 1
7
75
Penambahan Node(20)
New element is 20.
9
8
6
7
2 6
5 1
7
7
7
Sifting Up(7)
New element is 20.
9
8
6
7
2 6
5 1
7
77
Sifting Up(8)
New element is 20.
9
86
7
2 6
5 1
7
77
Hasil Penambahan Node(20)
New element is 20.
9
86
7
2 6
5 1
7
77
20
Penambahan Node(15) ????
New element is 15.
9
86
7
2 6
5 1
7
77
20
Sifting Up(8)
New element is 15.
9
8
6
7
2 6
5 1
7
77
20
8
Sifting Up(9)
New element is 15.
8
6
7
2 6
5 1
7
77
20
8
9
Hasil Penambahan Node(15)
New element is 15.
8
6
7
2 6
5 1
7
77
20
8
9
15
Penghapusan Max Node
Max element is in the root.
8
6
7
2 6
5 1
7
77
20
8
9
15
Removed Root
After max element is removed.
8
6
7
2 6
5 1
7
77 8
9
15
Sifting Up(15)
Reinsert 15 into the heap.
6
7
2 6
5 1
7
77
9
15
8
Sifting Up(9)
Reinsert 9 into the heap.
6
7
2 6
5 1
7
77
9
15
8
Sifting Up(8)
Reinsert 8 into the heapMax element is 15.
6
7
2 6
5 1
7
77
9
15
8
Penghapusan Max Node
After max element is removed.
6
7
2 6
5 1
7
77
9
8
Sifting Up(9)
6 2 6
5 1
7
9
8
7
Sifting Up(8)
6 2 6
5 1
7
9
8
7
8
Sifting Up(7)
6 2 6
5 1
7
9
8
7
Hasil Remove Max Element (15)
6 2 6
5 1
7
9
8
7
7
Latihan
input array = [-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
8
4
7
6 7
8 9
3
710
1
11
5
2
Max Heap Tree
Start at rightmost array position that has a child.
8
4
7
6 7
8 9
3
710
1
11
5
2
Sifting up(11)
Move to next lower array position.
8
4
7
6 7
8 9
3
710
1
5
11
2
Initializing A Max Heap
8
4
7
6 7
8 9
3
710
1
5
11
2
Initializing A Max Heap
8
9
7
6 7
8 4
3
710
1
5
11
2
Initializing A Max Heap
8
9
7
6 7
8 4
3
710
1
5
11
2
Initializing A Max Heap
8
9
7
6 3
8 4
7
710
1
5
11
2
Initializing A Max Heap
8
9
7
6 3
8 4
7
710
1
5
11
2
Initializing A Max Heap
8
9
7
6 3
8 4
7
710
1
5
11
Find a home for 2.
Initializing A Max Heap
8
9
7
6 3
8 4
7
75
1
11
Find a home for 2.
10
Initializing A Max Heap
8
9
7
6 3
8 4
7
72
1
11
Done, move to next lower array position.
10
5
Initializing A Max Heap
8
9
7
6 3
8 4
7
72
1
11
10
5
Find home for 1.
11
Initializing A Max Heap
8
9
7
6 3
8 4
7
72
10
5
Find home for 1.
Initializing A Max Heap
8
9
7
6 3
8 4
7
72
11
10
5
Find home for 1.
Initializing A Max Heap
8
9
7
6 3
8 4
7
72
11
10
5
Find home for 1.
Hasil Akhir
8
9
7
6 3
8 4
7
72
11
10
5
Done.
1
Binary Search Tree(BST)
Definisi
• Sebuah binary tree dimana subtree sebelah kiri lebih kecil dari subtree sebelah kanan.
Contoh BST
20
10
6
2 8
15
40
30
25
Binary Search Tree
• Operasi BST : penambahan, penghapusan, pencarian node tertentu, pencarian niai terkecil dan pencarian nilai terbesar.
• Properti Binary Search Tree :– Untuk setiap node X, semua elemen di
subpohon kirinya bernilai lebih kecil dari nilai X dan semua elemen di subpohon kanannya bernilai lebih besar dari nilai X.
Contoh
Binary Search Tree Bukan Binary Search Tree
Insert• Dimulai dengan penelusuran dari root
untuk mencari posisi yang tepat. • Jika elemen X ditemukan (berarti X
sudah ada di BST), maka tidak perlu melakukan aksi apapun.
• Jika tidak, maka letakkan X sebagai node terakhir pada jalur penelusuran
• Time complexity = O(height of the tree)
Delete
• Saat akan menghapus sebuah node, kita juga harus memikirkan seluruh node anak dari node tsb.– Hal penting adalah agar pohon setelah
dihapus tetap merupakan BST.
Operasi Penghapusan / remove()
Ada 3 kasus :
Elemen ada di leaf/daun.
Elemen yang memiliki degree 1.
Elemen yang memiliki degree 2.
Penghapusan Node Daun (Node 7)
Remove a leaf element. key = 7
20
10
6
2 8
15
40
30
25 35
7
18
Penhapusan Node Daun (Node 35)
Remove a leaf element. key = 35
20
10
6
2 8
15
40
30
25 35
7
18
Penghapusan Node Ber-degree 1
Remove from a degree 1 node. key = 40
20
10
6
2 8
15
40
30
25 35
7
18
Penghapusan Node Ber-degree 1
Remove from a degree 1 node. key = 15
20
10
6
2 8
15
40
30
25 35
7
18
Penghapusan Node Ber-degree 2
Remove from a degree 2 node. key = 10
20
10
6
2 8
15
40
30
25 35
7
18
Remove From A Degree 2 Node
20
10
6
2 8
15
40
30
25
Replace with largest key in left subtree (or smallest in right subtree).
35
7
18
Penghapusan Node Ber-degree 2
20
10
6
2 8
15
40
30
25
Replace with largest key in left subtree (or smallest in right subtree).
35
7
18
Penghapusan Node Ber-degree 2
20
8
6
2 8
15
40
30
25
Replace with largest key in left subtree (or smallest in right subtree).
35
7
18
Latihan
Remove from a degree 2 node. key = 20
20
10
6
2 8
15
40
30
25 35
7
18
Penghapusan Node Ber-degree 2
20
10
6
2 8
15
40
30
25
Replace with largest in left subtree.
35
7
18
Penghapusan Node Ber-degree 2
20
10
6
2 8
15
40
30
25
Replace with largest in left subtree.
35
7
18
Penghapusan Node Ber-degree 2
18
10
6
2 8
15
40
30
25
Replace with largest in left subtree.
35
7
18
Hasil Akhir18
10
6
2 8
15
40
30
25 35
7
Pencarian pada BST
• Jika mencari elemen bernilai 15, maka akan langsung ditemukan.
• Jika mencari elemen bernilai < 15, maka kita cari di subpohon kiri.
• Jika mencari elemen bernilai > 15, maka kita cari di subpohon kanan.
findMin/ findMax
• findMin : mengembalikan node dengan elemen terkecil pada BST
• Pencarian dimulai dari root dan bergerak ke kiri terus sepanjang subpohon kiri dan berhenti pada elemen terakhir.
• Proses serupa terhadap metode findMax
Red-Black Tree
Struktur Data - Tree 79
Red-Black Tree
• Red-black tree adalah binary search tree yang memenuhi properti sbb :– Setiap node adalah red atau black– Node root adalah black– Setiap daun adalah black– Semua anak dari node red adalah black– Setiap jalur (path) dari sebuah node ke
daun berisi node black yang jumlahnya sama
Struktur Data - Tree 80
Contoh Red-Black Tree
AVL Tree
AVL Tree
• AVL Properti :– Sebuah node memiliki AVL property jika
height (tinggi) subpohon kiri & subpohon kanan node tsb sama atau berbeda 1.
– Height (tinggi) pohon adalah jarak dari root menuju daun terbawah yang dimiliki pohon tsb
• AVL Tree adalah pohon yang setiap node nya memiliki AVL property
Pustaka
• Sartaj Sahni , “Data Structures & Algorithms”, Presentation L1.
• Mitchell Waite, “Data Structures & Algorithms in Java”, SAMS, 2001
top related