Struktur Data Tree (Pohon) Husni
Based on Problem Solving with Algorithms & Data Structures - Release 3.0 - September 22, 2013
Introduction to Trees Chapter 6
Why Trees? • Tree atau pohon sangat berdayaguna di bidang Informatika (Computer Science). • Pohon menyediakan suatu struktur bagi penyimpanan, manipulasi dan penemuan kembali informasi yang efisien. • Pohon dapat digunakan untuk memetakan relasi antar obyek atau sistem klasifikasi dalam dunia nyata. • Tree juga mengantarkan dasar untuk memahami Graph Theory. By Ptelea (Own work) [CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons
3
Different Types of Trees • Kita sering bekerja dengan pohon berakar atau rooted trees (berbentuk graf berarah) dan terlihat seperti ini: Root atau akar edge atau cabang Node interior daun
http://en.wikipedia.org/wiki/File:Binary_tree.svg
4
What is Special? • Our trees are upside down. The root is at the top and the leaves are at the bottom. • The only reason for this is that we normally write and read from the top of the page to the bottom. • It is easier to add things to the bottom of our diagrams. • We start at the root and move down the tree. • Usually our trees will be binary trees (a maximum of two branches from a node).
5
Example: 20 questions • One person chooses a subject and answers 20 questions with “yes” or “no” answers. • This is an example of following one branch of a binary tree as each question leads to only two possible answers. • In theory (with well designed questions) this can lead to differentiating 220 (over a million) different subjects.
6
Example: Sistem File • Most file systems are trees (folders or directories and files)
• Note the line at the bottom - this shows the path to the current directory. • There is a unique path from the root to the leaf. • This tree is not a binary tree (many files and directories can be descendants of one directory)
7
Sub-Pohon • Karena semua node di dalam pohon (kecuali node root) adalah keturunan dari tepat satu node lain maka kita dapat secara rekursif menganggap setiap node sebagai noe root dari pohon yang lebih kecil. • Pohon-pohon yang lebih kecil ini dinamakan sub-pohon (subtrees).
• Contoh: Node Users adalah root dari subtree direktori pengguna dalam diagram berikut:
8
XML dan HTML <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
simple A simple web page
- List item one
- List item two
XYZ
9
Istilah Penting • Parent - a node is the parent of all nodes it connects to with outgoing edges. • Children - all nodes with incoming edges from the same parent node are children of that node.
• Siblings - all nodes with the same parent are siblings. • Level - the number of edges from the root node to this node. The root node is therefore level 0. • Height - the height of a tree is the maximum level of all the nodes in the tree. 1 0
Tree definition 1 • A tree • has a root node • every node (except the root node) is connected by one edge from its unique parent node • a unique path goes from the root to each node • (and remember that a binary tree is one where the maximum number of children from a node is 2)
11
Tree definition 2 • A tree • can be empty • or consists of a root node and zero or more subtrees (subtrees are trees) • the root of a subtree is connected to the root of the tree by an edge • (a binary tree has no more than 2 subtrees from any root) 12
Binary Trees • Pohon yang umum digunakan dalam informatika adalah pohon biner (kecuali disebutkan khusus) • Mudah dimanfaatkan: setiap node induk mempunyai nilai kiri dan/atau kanan. • Dapat direpresentasikan seperti:
class BinaryTree(): def __init__(self, root_data): self.data = root_data self.left = None self.right = None 13
Pohon dengan List • Biasanya dibuatkan kelas BinaryTree dengan link ke sub-pohon kiri dan kanan.
• Bentuk sederhana adalah dengan List. ['a', ['b', [], ['d', [], [] ] ], ['c', ['e', [], [] ], ['f', [], [] ] ] ]
a
b
c
d
e
f
List Sebenarnya: 14 ['a', ['b', [], ['d', [], []]], ['c', ['e', [], []], ['f', [], []]]]
[data, left, right] Setiap node dalam pohon adalah list dengan 3 elemen: • Data atau nilai atau payload atau key (kunci) • Sub-pohon kiri (left subtree, berupa list) • Sub-pohon kanan (right subtree, juga suatu list)
15
ADT BinaryTree • Beberapa operasi pohon yang disediakan kelas BinaryTree: • BinaryTree() - create a new BinaryTree
• set_value(new_value) - sets the value of the node to new_value • get_value() - gets the value of the node
• insert_left(value) - creates a new node with value to the left of the current node, the existing left node becomes the left node of the new one • insert_right(value) - as above but to the right • get_left_subtree() - gets the subtree to the left of this node • get_right_subtree() - gets the subtree to the right of this node
• Catatan: Karena definisi rekursif, setiap node adalah root dari suatu16 subtree.
Kelas BinaryTree Sedikit berbeda dengan textbooks 6.4.1 class BinaryTree: DATA = 0 LEFT = 1 RIGHT = 2
# hanya agar mudah dibaca # dapat dirujuk dengan, misalnya: # BinaryTree.DATA atau self.DATA
def __init__(self, root_value, left=None, right=None): self.node = [root_value, left, right] Adanya nilai default untuk “left” dan “right” berarti bahwa konstruktor dapat dipanggil hanya dengan nilai unutk node root, sehingga subtree kiri dan kanan masih kosong (empty).
17
Penambahan/Penyisipan # Pendekatan di textbook untuk insert_left def insert_left(root, new_branch): t = root.pop(1) if len(t) > 0: root.insert(1, [new_branch, t, []]) else: root.insert(1, [new_branch, [], []]) return root
# Pendekatan alternatif def insert_left(self, value): self.node[self.LEFT] = BinaryTree(value, self.node[self.LEFT], None) def insert_right(self, value): self.node[self.RIGHT] = BinaryTree(value, None, self.node[self.RIGHT])
18
Fungsi-fungsi lain def set_value(self, new_value): """Sets the value of the node.""" self.node[self.DATA] = new_value def get_value(self): """Gets the value of the node.""" return self.node[self.DATA] def get_left_subtree(self): """Gets the left subtree of the node.""" return self.node[self.LEFT] def get_right_subtree(self): """Gets the right subtree of the node.""" return self.node[self.RIGHT]
19
Printing dengan str() • Printing pada versi textbook lebih mudah karena hanya mencetak isi list. • Pendekatan alternative di sini adalah menggunakan rekursi dan fungsi khusus __str__. • __str__(self) dipanggil ketika fungsi str() digunakan, misalnya oleh fungsi print().
def __str__(self): return '['+str(self.node[self.DATA])+', '+\ str(self.node[self.LEFT])+', '+\ str(self.node[self.RIGHT])+']'
20
Output
1
r = BinaryTree(1) r.insert_left(2) r.insert_right(3) r.insert_right(4) r.get_left_subtree().insert_left(5) r.get_left_subtree().insert_right(6)
2
5
4
3
6
print(r) print(r.get_left_subtree()) print(r.get_right_subtree()) print(r.get_left_subtree().get_left_subtree()) Menghasilkan:
[1, [2, [5, None, None], [6, None, None]], [4, None, [3, None, None]]] [2, [5, None, None], [6, None, None]] [4, None, [3, None, None]] [5, None, None]
21
K.I.S.S. • Normally if you can use a built-in or standard Python data type to represent your data you should. • Or as we just did create a new class with Python standard types as “instance variables” of the class. • Sometimes you may subclass an existing class or data type to provide additional behaviour but this is beyond the scope of this course. • Dengan kelas BinaryTree kita dapat menggunakan implementasi yang sangat berbeda yang tidak bersandar pada list dari Python.
22
Node & Referensi # lihat kelas BinaryTree di Textbook sebagai bandingan class MyBinaryTree:
def __init__(self, root_key, left=None, right=None): self.key = root_key self.left = left self.right = right Sehingga kelas diatas dapat dipanggil dengan banyak cara: MyBinaryTree(3) MyBinaryTree(3, existing_left, None) MyBinaryTree(3, MyBinaryTree(4), MyBinaryTree(5)) MyBinaryTree(3, MyBinaryTree(4, MyBinaryTree(2), MyBinaryTree(7)), MyBinaryTree(5, MyBinaryTree(6)) 23
Implementasi Lanjutan def insert_left(self, value): self.left = MyBinaryTree(value, left=self.left) # kanan? def insert_right(self, value): self.right = MyBinaryTree(value, right=self.right) # kiri?
def get_left_subtree(self): return self.left def get_right_subtree(self): return self.right def set_value(self, new_value): self.data = new_value
def get_value(self): return self.data 24
Priority Queues & Binary Heaps Chapter 6.5
Some animals are more equal than others • Suatu antrian (queue) adalah struktur data FIFO • the first element in is the first element out • which of course means the last one in is the last one out • But sometimes we want to sort of have a queue but we want to order items according to some characteristic the item has.
26
Priorities • Prioritas: karakteristik penempatan atau pengurutan. • Saat kita menarik sesuatu dari “queue” ini kita selalu mendapatkan elemen dengan prioritas terbaik (kadang kala terbaik berarti paling rendah). • Sangat umum di Sistem Operasi menggunakan prioritas untuk menjadwal saat sesuatu terjadi, misal: • Proses yang sangat penting sebaiknya berjalan sebelum proses yang tidak begitu penting • data dari disk sebaiknya diambilkan untuk proses-proses sangat penting lebih dahulu.
27
Priority Queue • A priority queue always produces the element with the best priority when queried.
• You can do this in many ways • keep the list sorted • or search the list for the minimum value (if like the textbook and Unix actually - you take the smallest value to be the best) • You should be able to estimate the Big O values for implementations like this. e.g. O(n) for choosing the minimum value of an unsorted list. • There is a clever data structure which allows all operations on a priority queue to be done in O(log n). 28
Binary Heap Fokus pada min-heap biner
• Properti bentuk: pohon biner lengkap, semua level kecuali terakhir harus penuh. Node level akhir diisi dari kiri. • Properti heap: semua induk harus kurang atau sama (<) dengan anak-anaknya.
http://en.wikipedia.org/wiki/Binary_heap
29
Cara Cerdas • Pohon biner lengkap dapat direpresentasikan sangat bagus dalam array atau list.
• Karena tak ada gap kita dapat merepresentasikan baris dari tree sebagai rentetan list yang dapat kemudian digabungkan ke dalam satu list.
1 2
3
17 19 36 7 25
1
2
30
100
3
17 19 36 7
25
100
Anak dua kali Induk • Jika kita menambahkan suatu elemen kosong (empty) pada awal list, maka kita kemudian dapat menjumpai anak kiri dari node tertentu pada posisi p pada 2p dan anak kanan pada posisi 2p + 1. • Misal: anak dari elemen pada posisi 2 ada pada posisi 4 dan 5. Anak dari 2 adalah 17 dan 19.
0
1
2
3
17 19 36 7
25 100
1
2
3
4
8
5
31
6
7
9
Pohon biner lengkap & Representasinya
32
Operasi Binary Heap • Create an empty binary heap • Insert an item in the heap • Retrieve the smallest item (removing it) • Get the size of the heap • Build a heap from a list
33
Membuat Heap Biner Baru # dapat dimulai dengan sesuatu seperti: class BinHeap: def __init__(self): self.heap_list = [0] # akan dikembangkan lebih baik nantinya. # Catatan: tidak mencatat size seperti dalam Textbook # karena dapat digunakan len(self.heap_list) - 1. def size(self): """Mengembalikan ukuran dari heap.""" return len(self.heap_list) - 1
34
Penambahan ke dalam Heap • Kita perlu menjaga dua properti min-heap: • Properti bentuk (shape): tree harus tetap lengkap (complete)
• Properti heap: nilai terkecil berada pada root • Properti bentuk mudah dijaga. Kita cukup menambahkan nilai baru ke dalam posisi daun berikutnya. Dalam list ini berarti menambahkan elemen ke list.
35
Mempertahankan Heap • To keep the heap property we may need to move the new value further up the tree. • We repeatedly compare it to its parent exchanging them if it is smaller than its parent. • This is sometimes called percolating because the smallest values bubble to the top.
36
37
Menapis node baru ke posisi tepatnya
Why is the exchange safe? • When we are swapping a value with its parent (say we are halfway up the tree) we know that the heap property will still be true for the subtree we are currently looking at because
• The new value is smaller than its parent and if the other child was greater than or equal to the parent value it must be greater than the new value. • Any subtree below the current position of the new value must have values all greater than the parent so they are still in the correct positions.
38
Kode Penyisipan (Penambahan) def insert(self, k): self.heap_list.append(k) self.perc_up(self.size()) def perc_up(self, i): # we keep comparing with the parent until we reach the top # or the parent is smaller than the child while i // 2 > 0 and self.heap_list[i] < self.heap_list[i // 2]: self.heap_list[i], self.heap_list[i // 2] = \ self.heap_list[i // 2], self.heap_list[i] i = i // 2
39
Mengambil Nilai Minimum • Dengan suatu min heap ini cukup gampang. • Itu adalah elemen root atau dalam implementasi list adalah elemen pada indeks 1. • Jika kita menghapusnya maka harus memastikan property bentuk dan heap. • Bentu mudah untuk ditetapkan lagi: kita memindahkan daun terakhir di dalam heap ke posisi pertama (atau root).
40
Memelihara Heap (lagi) • Saat ini kita telah (hamper pasti) memindahkan suatu nilai yang lebih besar ke dalam root. • Kita perlu menapis nilai ini turun ke bawah tree.
41
42
Penapisan Node Root ke Bawah Tree
43
Penapisan Node Root ke Bawah Tree
Going down is a little trickier than going up • Percolating up was straight-forward because each child only has one parent. • Percolating down we want to swap with the smallest child (to preserve the heap property).
44
Kode: Penghapusan def del_min(self): ret_val = self.heap_list[1] replacement = self.heap_list.pop() if self.size() > 0: self.heap_list[1] = replacement self.perc_down(1) return ret_val
45
Penalisan (Percolating) Turun def perc_down(self, i): while (i * 2) <= self.size(): child = self.min_child(i) if self.heap_list[i] > self.heap_list[child]: self.heap_list[child], self.heap_list[i] = self.heap_list[i], self.heap_list[child] i = child def min_child(self, i): ”””Mengembalikan indeks dari anak minimum ber-indeks i.””” left = i * 2 right = left + 1 if right > self.size(): return left if self.heap_list[left] < self.heap_list[right]: return left else: return right 46
Membangun Heap dari List • We can do it the boring way. • Start with an empty list and insert each element in turn. • This will be O(n log n) as there are n elements to add and each could percolate up the levels of the tree. • Or we can do it the clever way.
47
Cara Efisien • We start half way through the list. • Any nodes in the last half of the list are leaves because of the shape of our complete binary tree. Each level of the tree has one more node than the sum of the nodes in all previous levels. • Moving backwards through the list percolate each element down to its correct position. • This is O(n) - but I am not going to prove it :).
48
Membangun Heap dari List [9, 6, 5, 2, 3]
49
This is what Figure 6.12 should look like.
Pegeseran Naik & Turun • Nomor di dalam lingkaran menunjukkan jumlah maksimum pertukaran yang diperlukan saat penambahan node ke heap
50
Kode: Membangun Heap def __init__(self, a_list=[]): """Constructs a BinHeap object. Can either create an empty BinHeap or can construct it from a_list. """ self.heap_list = [0] + a_list # add the dummy to list for i in range(self.size() // 2, 0, -1): self.perc_down(i)
51
Heap Beda Hasilnya sama bh = BinHeap() bh.insert(9) bh.insert(6) bh.insert(5) bh.insert(2) bh.insert(3) print(bh) bh = BinHeap([9,6,5,2,3]) print(bh)
Output [2, 3, 6, 9, 5]
[2, 3, 5, 6, 9]
52
And by the way • The BinHeap class has a special __str__ method to print out the heap values but leave out the dummy first element. def __str__(self): return str(self.heap_list[1:])
53
Aplikasi Pohon Biner Chapter 6.6
Parse Trees • What is parsing? • Originally from language study • The breaking up of sentences into component parts e.g. noun phrase • In computing compilers and interpreters parse programming languages. • One aspect is parsing expressions.
55
Expression Trees • The leaves are values and the other nodes are operators. • We can use them to represent and evaluate the expression.
• We work up from the bottom evaluating subtrees. • Compilers can use this to generate efficient code - e.g. how many registers are needed to calculate this expression.
56
Tokens • Parsing starts with recognising tokens. • A token is a symbol made up of one or more characters (commonly separated by white space). • e.g. a variable name or a number or an operator “+”. • For an expression tree the tokens are numbers, operators and parentheses.
57
Parsing Rules • As we identify tokens we can apply rules to what we should do. • If the expression is fully parenthesised • a left parenthesis “(“ starts a subtree • a right parenthesis “)” finishes a subtree
58
4 Rules 1. If the current token is a ‘(’, add a new node as the left child of the current node, and descend to the left child.
2. If the current token is in the list [‘+’,’−’,’*’,‘/’], set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child. 3. If the current token is a number, set the root value of the current node to the number and return to the parent.
4. If the current token is a ‘)’, go to the parent of the current node.
59
(3 + (4 * 5)) Node Aktif
60
(3 + (4 * 5))
Node Aktif
6 1
(3 + (4 * 5)) Node Aktif
3
6 2
(3 + (4 * 5)) +
3
Node Aktif
63
(3 + (4 * 5)) +
3
Node Aktif
64
(3 + (4 * 5)) +
3
Node Aktif
4
65
(3 + (4 * 5)) +
3
*
4
66
(3 + (4 * 5)) +
3
*
4
Node Aktif
5
67
(3 + (4 * 5)) Node Aktif
+
3
*
4
5
68
(3 + (4 * 5)) +
3
*
4
5
69
Giliran Anda! • Bangkitkan expression tree untuk notasi matematika berikut: ((2 * ((3 - 4) + 6)) + 2)
70
Keeping Track of the Parent • We need to be able to move back up the tree.
• So we need to keep track of the parent of the current working node. • We could do this with links from each child node back to its parent. • Or we could store the tree in a list and use the 2 x n trick (if the tree is not complete - most won’t be) then there will be lots of empty space in this list. • Or we could push the parent node onto a stack as we move down the tree and pop parent nodes off the stack when we move back up. 71
Kode: Membangun Pohon set up def build_expression_tree(parenthesized_expression): """Builds an expression parse tree. parenthesized_expression -- a fully parenthesized expression with spaces between tokens """ token_list = parenthesized_expression.split() parent_stack = Stack() expression_tree = BinaryTree('') parent_stack.push(expression_tree) current_tree = expression_tree
72
Menerapkan Aturan (Rule) 1.If the current token is a ‘(’, add a new node as the left child of the current node, and descend to the left child. for token in token_list: if token == '(': current_tree.insert_left('') parent_stack.push(current_tree) current_tree = current_tree.get_left_child()
73
Menerapkan Rule 2.If the current token is in the list [‘+’,‘−’,‘*’,‘/’], set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child. elif token in ['+', '-', '*', '/']: current_tree.set_value(token) current_tree.insert_right('') parent_stack.push(current_tree) current_tree = current_tree.get_right_child()
74
Menerapkan Rule 3.If the current token is a number, set the root value of the current node to the number and return to the parent. elif is_number(token): current_tree.set_value(float(token)) current_tree = parent_stack.pop()
def is_number(token): """Check if the token is a number.""" try: float(token) except: return False else: return True
75
Menerapkan Rule 4.If the current token is a ‘)’, go to the parent of the current node. elif token == ')': current_tree = parent_stack.pop() else: raise ValueError
76
Evaluasi Ekspresi • Once we have generated the expression tree we can easily evaluate the expression. • In a compiler the expression would contain variables which we wouldn’t know the value of until the program ran, so the evaluation would be done at run time.
77
Bagaimana Evaluasi Dilaksanakan? +
3
*
4
Evaluasi sub-pohon ini
5
78
Algoritma • To evaluate the subtree under a node • if the node has children • the node holds an operator • return the result of applying the operator on the left and right subtrees • else the node held a number
• return the number
79
Kode: Evaluasi import operator def evaluate(expression_tree): """Return the result of evaluating the expression.""" token = expression_tree.get_value() operations = {'+':operator.add, '-':operator.sub, '*':operator.mul, ‘/':operator.truediv} left = expression_tree.get_left_child() right = expression_tree.get_right_child() if left and right: return operations[token](evaluate(left), evaluate(right)) else: return token
80
What is that operator stuff? • The operator module provides functions to add, subtract etc. • We use a dictionary “operations” to connect the tokens “+”, “-”, “*” and “/” with the corresponding function. • The line operations[token](evaluate(left), evaluate(right)) evokes the function on its parameters.
81
Penjelajahan Pohon Text book sub-bab 6.7
• With a binary tree we can recursively travel through all of the nodes (or traverse) in three standard ways.
• We can deal with the node first then deal with the left subtree, then the right subtree. • This is a preorder traversal.
• We can deal with the left subtree, then with the node, then with the right subtree. • This is an inorder traversal (and as we will see this keeps things in order). • We can deal with the left subtree, then the right subtree and lastly the node itself.
• This is a postorder traversal (we used this to evaluate expression trees).
82
Kode: Cetak Penjelajahan Pohon def print_preorder(tree): """Print the preorder traversal of the tree.""" if tree: print(tree.get_value(), end=' ') print_preorder(tree.get_left_child()) print_preorder(tree.get_right_child()) def print_postorder(tree): """Print the postorder traversal of the tree.""" if tree: print_postorder(tree.get_left_child()) print_postorder(tree.get_right_child()) print(tree.get_value(), end=' ') def print_inorder(tree): """Print the inorder traversal of the tree.""" if tree: print_inorder(tree.get_left_child()) print(tree.get_value(), end=' ') print_inorder(tree.get_right_child())
83
Pohon Pencarian Biner Sub-bab 6.8
Trees are efficient • Many algorithms can be performed on trees in O(log n) time. • Searching for elements using a binary search can work on a tree if the elements are ordered in the obvious way. • Adding and removing elements is a little trickier.
85
The Binary Search Tree property • All values in the nodes in the left subtree of a node are less than the value in the node. • All values in the nodes in the right subtree of a node are greater than the value in the node.
http://en.wikipedia.org/wiki/Binary_search_tree
86
Membangun BST • We can go through a list of elements adding them in the order they occur. • Misal: 70, 31, 93, 94, 14, 23, 73
87
70, 31, 93, 94, 14, 23, 73 70
88
70, 31, 93, 94, 14, 23, 73 70
31
89
70, 31, 93, 94, 14, 23, 73 70
31
93
90
70, 31, 93, 94, 14, 23, 73 70
31
93
94
91
70, 31, 93, 94, 14, 23, 73 70
31
93
94
14
92
70, 31, 93, 94, 14, 23, 73 70
31
93
94
14
23 93
70, 31, 93, 94, 14, 23, 73 70
31
93
73
14
94
23 94
Giliran Anda! • Tambahkan elemen 17, 5, 25, 2, 11, 35, 9, 16, 29, 38, 7 ke suatu pohon pencarian biner!
95
ADT Map dan BST • If we use a key as the ordering component in our BSTs we can also store a separate value. • We can then use a BST as a Map with functions such as: • put(key, value) - stores value using key
• get(key) - returns the value found from key • The text book does this.
• Most introductions just use a value - this is what I will use. 96
Kode: Binary Search Tree class BST: """A Binary Search Tree (BST) class.""" def __init__(self, value, parent=None): """Construct a BST. value -- the value of the root node parent -- the parent node (of this BST subtree) """ self.value = value self.left = None self.right = None self.parent = parent # useful for some operations
97
Menyisipkan Suatu Nilai def insert(self, value): """Insert value into the BST.""" if value == self.value: # already in the tree return elif value < self.value: if self.left: self.left.insert(value) else: self.left = BST(value, parent=self) else: if self.right: self.right.insert(value) else: self.right = BST(value, parent=self)
98
A Factory Method def create(a_list): """Create a BST from the elements in a_list.""" bst = BST(a_list[0]) for i in range(1, len(a_list)): bst.insert(a_list[i]) return bst # A factory method is one which creates and returns # a new object. # e.g. this would be called like this bst = BST.create([70, 31, 93, 94, 14, 23, 73])
99
Doing something in order def inorder(self, function): """Traverse the BST in order performing function.""" if self.left: self.left.inorder(function) function(self.value) if self.right: self.right.inorder(function) # for example: bst = BST.create([70, 31, 93, 94, 14, 23, 73]) bst.inorder(print) # The output is 14 23 31 70 73 93 94
100
Giliran Anda • Tuliskan metode __contains__ yang akan mengembalikan True jika BST mengandung nilai, jika tidak False. def __contains__(self, value):
101
Menghapus Nilai • We need to find the node the value is stored in. • There are three cases • the node has no children • the node has one child • the node has two children
102
Menemukan Node def locate(self, value): """Return the node holding value.""" if value == self.value: return self elif value < self.value and self.left: return self.left.locate(value) elif value > self.value and self.right: return self.right.locate(value) else: return None
103
Tidak Punya Anak Menghapus No 16 (tanpa anak)
104
Node Tanpa Anak • Cukup hapus node tersebut dan betulkan induknya.
105
Satu anak Menghapus node 25 (memiliki satu anak)
106
Satu Anak • Hapus node dan geser anaknya (menempati tempatnya) dengan mengubah induknya.
107
Dua Anak Menghapus Node 5 (dua anak)
108
Dua Anak • Ganti nilai dalam node dengan suksesor inorder-nya. • Juga hapus node suksesor inorder-nya. • Tetapi ini tidak dapat mempunyai lebih dari satu anak. • Mengapa tidak?
109
Gambarkan BST • Masukkan elemen dengan urutan berikut: 50, 70, 30, 37, 43, 81, 12, 72, 99
110
Hapus Elemen Merah 33
23 17 9
40 32
51
28
45
26
76
80
111
Hapus Elemen Merah 33
23 17 9
40 32
51
28
45
26
76
80
112
Hapus Elemen Merah 33
23 17 9
40 32
51
28
45
26
76
80
113
Hapus Elemen Merah 33
23 17 9
40 32
51
28
45
26
76
80
114
Kode: Penghapusan • •
Harus menemukan node yang menyimpan nilai yang akan dihapus. Ada 3 kasus: • Node mempunyai dua anak • Node mempunyai satu anak • Node tidak mempunyai anak
def delete(self, value): """Delete value from the BST.""" node = self.locate(value) # saw this last lecture if node: node.delete_this_node() def delete_this_node(self): left = self.left right = self.right if left and right: # two children self.delete_with_children() elif left or right: # one child self.delete_with_child() else: # no children self.delete_no_children() 115
Penghapusan Tanpa Anak •
Hanya hapus node tersebut dan betulkan induknya def delete_no_children(self): if self.parent: if self.parent.left == self: self.parent.left = None else: self.parent.right = None else: # special case the root node self.value = None
116
Penghapusan Dengan Satu Anak •
Hapus node tersebut dan geser naik untuk mendapatkan tempat baru dengan mengubah induknya. def delete_with_child(self): child = self.left if self.left else self.right if self.parent: if self.parent.left == self: self.parent.left = child else: self.parent.right = child child.parent = self.parent else: # special case the root node self.replace(child)
117
Mengganti Isi Node # Kita telah menghapus nilai root namun kita tidak ingin # menghapus node root tersebut (karena ini mendefinisikan BST). # Jadi letakkan info baru ke dalam node root tersebut. def replace(self, other): """Ganti node ini dengan nilai dari yang lain.
Juga perlu melekatkan-ulang anak-anak lain. """ self.value = other.value self.left = other.left if self.left: self.left.parent = self self.right = other.right if self.right: self.right.parent = self
118
Penghapusan Dengan Anak def delete_with_children(self): replacement = self.right.min() # the successor successor_value = replacement.value replacement.delete_this_node() # max of one child of this self.value = successor_value
•
Ganti nilai dalam node tersebut dengan suksesor inordernya
•
Juga hapus node suksesor inorder-nya.
119
Kode: Inorder successor def min(self): """Mengembalikan node paling kiri dari BST.""" min_node = self while min_node.left: min_node = min_node.left return min_node
120
Big O Dari Operasi • It depends on how the tree has been constructed. • A full binary tree or one close to it (every node not a leaf node has two children) is ideal. • The algorithms depend on how far down the tree you have to go in order to insert or delete nodes. • With a full binary tree the number of nodes in level d is 2d. And the number of nodes in a tree of height h+1 h is 2 - 1.
121
Balanced dan Unbalanced • A balanced tree has approximately the same number of nodes in the left subtree as in the right subtree. This will give O(log n) operations for retrieval, insertion and deletion. • Unbalanced trees have runs of single children. This can be as bad as a simple list and so has O(n) operations.
Pohon Pencarian Biner Miring akan memberikan kinerja buruk 122
