Melanjutkan dari modul sebelumnya, pada modul ini akan diimplementasikan dalam Python.
Buat fungsi baru diluar class dengan nama rotateRight dan rotateLeft.
def rotateRight(root):
pivot = root.left
reattachNode = pivot.right
root.left = reattachNode
pivot.right = root
return pivot
def rotateLeft(root):
pivot = root.right
reattachNode = pivot.left
root.right = reattachNode
pivot.left = root
return pivotBerikut 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)
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)
def rotateRight(root):
pivot = root.left
reattachNode = pivot.right
root.left = reattachNode
pivot.right = root
return pivot
def rotateLeft(root):
pivot = root.right
reattachNode = pivot.left
root.right = reattachNode
pivot.left = root
return pivot
unbalancedLL = Tree(Node(30), 'unbalanced left-left')
unbalancedLL.root.left = Node(20)
unbalancedLL.root.right = Node(40)
unbalancedLL.root.left.left = Node(10)
unbalancedLL.root.left.right = Node(25)
unbalancedLL.root.left.left.left = Node(5)
unbalancedLL.root.left.left.right = Node(15)
unbalancedLL.printTree()
unbalancedLL.root = rotateRight(unbalancedLL.root)
unbalancedLL.printTree()
unbalancedRR = Tree(Node(30), 'unbalanced right-right')
unbalancedRR.root.left = Node(20)
unbalancedRR.root.right = Node(40)
unbalancedRR.root.right.left = Node(35)
unbalancedRR.root.right.right = Node(60)
unbalancedRR.root.right.right.left = Node(55)
unbalancedRR.root.right.right.right = Node(75)
unbalancedRR.printTree()
unbalancedRR.root = rotateLeft(unbalancedRR.root)
unbalancedRR.printTree()
Jika dijalankan maka sesuai ekspektasi program diatas berhasil melakukan rebalancing.
$ python tree.py
unbalanced left-left
30*
/ \
20 40
/ \ / \
10 25 _ _
/ \ / \ / \ / \
5 15 _ _ _ _ _ _
unbalanced left-left
20
/ \
10 30
/ \ / \
5 15 25 40
unbalanced right-right
30*
/ \
20 40
/ \ / \
_ _ 35 60
/ \ / \ / \ / \
_ _ _ _ _ _ 55 75
unbalanced right-right
40
/ \
30 60
/ \ / \
20 35 55 75Bagaimana dengan left-right unbalanced tree? Seperti yang sudah dibahas dimodul sebelumnya, kita cukup melakukan rotasi left rotation yang kemudian diikut right rotation.
Perhatikan code dibawah melakukan dua kali rotasi yaitu, unbalancedLR.root.left = rotateLeft(unbalancedLR.root.left) dan unbalancedLR.root = rotateRight(unbalancedLR.root)
unbalancedLR = Tree(Node(30), 'unbalanced left-right')
unbalancedLR.root.left = Node(10)
unbalancedLR.root.right = Node(40)
unbalancedLR.root.left.left = Node(5)
unbalancedLR.root.left.right = Node(20)
unbalancedLR.root.left.right.left = Node(15)
unbalancedLR.root.left.right.right = Node(25)
unbalancedLR.printTree()
unbalancedLR.root.left = rotateLeft(unbalancedLR.root.left)
unbalancedLR.root = rotateRight(unbalancedLR.root)
unbalancedLR.printTree()PS F:\Project\bst> python tree.py
unbalanced left-right
30*
/ \
10 40
/ \ / \
5 20 _ _
/ \ / \ / \ / \
_ _ 15 25 _ _ _ _
unbalanced left-right
20
/ \
10 30
/ \ / \
5 15 25 40Untuk Latihan, silakan mencoba untuk melakukan rebalancing right-left unbalanced tree.