Kondisi tree yang balanced akan membuat proses searching pada tree lebih cepat.
Jadi apa yang dimaksud dengan imbalance tree?
Kondisi imbalance atau tidak seimbang dari tree adalah jika salah satu kaki memiliki kedalaman >= 2 dibanding kaki lainnya.
Kondisi unbalanced pada tree dilihat dari perspektif root node. Kita pun bisa melihat imbalance pada tingkat node.
Untuk mendeteksi apakah suatu node balanced atau tidak, kita tambahkan fungsi pada class Node, pada tutorial digunakan nama isBalanced()
Gunakan fungsi height yang sudah kita buat pada modul sebelumnya, untuk menghitung kedalaman node pada sisi kiri dan kanan. Lalu kembalikan nilai boolean dengan melakukan perbandingan abs(leftHeight-rightHeight) < 2
def isBalanced(self):
leftHeight = self.left.height()+1 if self.left else 0
rightHeight = self.right.height()+1 if self.right else 0
return abs(leftHeight-rightHeight) < 2Kita implementasikan fungsi diatas pada fungsi print tree untuk menunjukan node mana saja yang unbalanced.
Pertama tambahkan fungsi helper pada Node class, untuk menambahkan tanda asterisk (*)
def unbalanced_indikator(self):
if not self.isBalanced():
return str(self.data) + "*"
return str(self.data)Lalu lakukan modifikasi pada fungsi _nodeToChar(self, n, space) dari class Tree menjadi seperti dibawah. Perhatikan bagian yang diubah adalah n.unbalanced_indikator.
def _nodeToChar(self, n, space):
if n is None:
return '_' + (' '*space)
space = space - len(n.unbalanced_indikator())+1
return n.unbalanced_indikator()+(' '*space)Agar fungsi print berjalan baik, kita juga modifikasi fungsi getNodeAtDepth(self, depth, nodes=[]) menjadi seperti berikut:
def getNodeAtDepth(self, depth, nodes=[]):
if depth==0:
nodes.append(self)
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 nodesBerikut isi lengkap program tree.py
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)
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
def isBalanced(self):
leftHeight = self.left.height()+1 if self.left else 0
rightHeight = self.right.height()+1 if self.right else 0
return abs(leftHeight-rightHeight) < 2
def unbalanced_indikator(self):
if not self.isBalanced():
return str(self.data) + "*"
return str(self.data)
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(n.unbalanced_indikator())+1
return n.unbalanced_indikator()+(' '*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()
$ python .\tree.py
Basic BST
55*
/ \
25 70*
/ \ / \
_ _ 60 90
/ \ / \ / \ / \
_ _ _ _ _ _ 80 120
/ \ / \ / \ / \ / \ / \ / \ / \
_ _ _ _ _ _ _ _ _ _ _ _ _ 85 _ _Dapat dilihat pada node 55 dan 70 ditambahkan tanda asterisk (*), menunjukan node tersebut imbalance.