Teori Singkat
Untuk menghapus node, langkah pertama adalah mencari node tersebut. Kemudian melakukan delete node.
Ada tiga kondis penghapusan, yaitu zero, one dan two child.
Zero Child, jika node yang dihapus tidak memiliki children. Kita bisa langsung delete node tersebut. Lihat gambar-1, contoh yang akan dihapus adalah node 25.
One Child, jika node yang dihapus memiliki 1 children. Maka node children tersebut akan menjadi posisi parent (node yang dihapus). Lihat gambar-2, node yang akan dihapus adalah 70.
Two Child, jika node yang dihapus memiliki 2 children. Gunakan metoda RTFM, Right Tree Find Minimum. Jadi telusuri node di kaki kanan, cari nilai minimum. Gunakan node minimum tersebut untuk menggantikan node yang dihapus.
Lihat gambar-3, node yang akan dihapus adalah node 70. Langkah pertama telesuri kaki kanan untuk mencari node minimum, yaitu node 80. Karena node minimum, sudah dipastikan hanya memiliki kaki kanan (jika memiliki kaki kiri, node tersebut bukan node minimum).
Pindahkan node 80 untuk menggantikan node 70. Jika memiliki child, maka pindahkan child ke posisi node 80 sebelumnya.
Implementasi Pada Python
Pertama kita buat helper function untuk mencari minimum node.
def findMinNode(self):
if self.left:
return self.left.findMinNode()
return self.dataLalu kita buat fungsi untuk delete Node
def delNode(self, target):
if self.data == target:
if self.left and self.right:
#do RTFM
minNode = self.right.findMinNode()
self.data = minNode
self.right = self.right.delNode(minNode)
return self
else:
#one child or two child
return self.left or self.rightJangan lupa untuk menambahkan fungsi delNode pada class wrapper Tree.
def delNode(self, target):
self.root = self.root.delNode(target)Berikut isi lengkap program tree.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def search(self, target):
if self.data == target:
print("Node found")
return self
if self.left and self.data > target:
return self.left.search(target)
if self.right and self.data < target:
return self.right.search(target)
print("No Node Found")
def traversePreorder(self):
print(self.data)
if self.left:
self.left.traversePreorder()
if self.right:
self.right.traversePreorder()
def traverseInorder(self):
if self.left:
self.left.traverseInorder()
print(self.data)
if self.right:
self.right.traverseInorder()
def traversePostorder(self):
if self.left:
self.left.traversePostorder()
if self.right:
self.right.traversePostorder()
print(self.data)
def height(self, h=0):
leftHeight = self.left.height(h+1) if self.left else h
rightHeight = self.right.height(h+1) if self.right else h
return max(leftHeight, rightHeight)
def getNodeAtDepth(self, depth, nodes=[]):
if depth==0:
nodes.append(self.data)
return nodes
if self.left:
self.left.getNodeAtDepth(depth-1, nodes)
else:
nodes.extend([None]*2**(depth-1))
if self.right:
self.right.getNodeAtDepth(depth-1, nodes)
else:
nodes.extend([None]*2**(depth-1))
return nodes
def addNode(self, val):
if self.data == val:
return
if val < self.data:
if self.left is None:
self.left = Node(val)
else:
self.left.addNode(val)
if val > self.data:
if self.right is None:
self.right = Node(val)
else:
self.right.addNode(val)
def findMinNode(self):
if self.left:
return self.left.findMinNode()
return self.data
def delNode(self, target):
if self.data == target:
if self.left and self.right:
#do RTFM
minNode = self.right.findMinNode()
self.data = minNode
self.right = self.right.delNode(minNode)
return self
else:
return self.left or self.right
if self.right and target > self.data:
self.right = self.right.delNode(target)
if self.left and target < self.data:
self.left = self.left.delNode(target)
return self
class Tree:
def __init__(self, root, name=''):
self.root = root
self.name = name
def search(self, target):
return self.root.search(target)
def traversePreorder(self):
self.root.traversePreorder()
def traverseInorder(self):
self.root.traverseInorder()
def traversePostorder(self):
self.root.traversePostorder()
def height(self):
return self.root.height()
def getNodeAtDepth(self, depth):
return self.root.getNodeAtDepth(depth)
def _nodeToChar(self, n, space):
if n is None:
return '_' + (' '*space)
space = space - len(str(n))+1
return str(n)+(' '*space)
def printTree(self, label=''):
print(self.name + ' ' + label)
height = self.root.height()
space = 3
width = int((2**height-1) * (space+1) +1)
offset = int((width-1)/2)
for depth in range(0, height+1):
if depth>0:
print(' '*(offset+1) + (' '*(space+2)).join(['/' + (' '*(space-2)) + '\\']*(2**(depth-1))))
row = self.root.getNodeAtDepth(depth, [])
print ((' '*offset)+ ''.join([self._nodeToChar(n,space) for n in row]))
space = offset + 1
offset = int(offset/2)-1
print ('')
def addNode(self, val):
self.root.addNode(val)
def delNode(self, target):
self.root = self.root.delNode(target)
node = Node(55)
node.left = Node(25)
node.right = Node(70)
node.right.left = Node(60)
node.right.right = Node(90)
node.right.right.left = Node(80)
node.right.right.right = Node(120)
node.right.right.left.right = Node(85)
myTree = Tree(node, 'Basic BST')
myTree.printTree()
myTree.delNode(70)
myTree.printTree()
$ python tree.py
Basic BST
55
/ \
25 70
/ \ / \
_ _ 60 90
/ \ / \ / \ / \
_ _ _ _ _ _ 80 120
/ \ / \ / \ / \ / \ / \ / \ / \
_ _ _ _ _ _ _ _ _ _ _ _ _ 85 _ _
Basic BST
55
/ \
25 80
/ \ / \
_ _ 60 90
/ \ / \ / \ / \
_ _ _ _ _ _ 85 120Pada program dilakukan penghapusan node 70, sesuai ekspektasi, node 80 akan menggantikan node 70, dan node 85 akan menggantikan posisi node 80.