# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
class BSTree:
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rotate_right(self):
n = self.left
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n.left, n.right, n, self.right
def rotate_left(self):
n = self.right
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n, self.left, n.right, n.left
def __init__(self):
self.size = 0
self.root = None
def add(self, val):
assert(val not in self)
def add_rec(node):
if not node:
return BSTree.Node(val)
elif val < node.val:
node.left = add_rec(node.left)
return node
else:
node.right = add_rec(node.right)
return node
self.root = add_rec(self.root)
self.size += 1
def __contains__(self, val):
def contains_rec(node):
if not node:
return False
elif val < node.val:
return contains_rec(node.left)
elif val > node.val:
return contains_rec(node.right)
else:
return True
return contains_rec(self.root)
def __len__(self):
return self.size
def __delitem__(self, val):
assert(val in self)
def delitem_rec(node):
if val < node.val:
node.left = delitem_rec(node.left)
return node
elif val > node.val:
node.right = delitem_rec(node.right)
return node
else:
if not node.left and not node.right:
return None
elif node.left and not node.right:
return node.left
elif node.right and not node.left:
return node.right
else:
# remove the largest value from the left subtree as a replacement
# for the root value of this tree
t = node.left
if not t.right:
node.val = t.val
node.left = t.left
else:
n = t
while n.right.right:
n = n.right
t = n.right
n.right = t.left
node.val = t.val
return node
self.root = delitem_rec(self.root)
self.size -= 1
def pprint(self, width=64):
"""Attempts to pretty-print this tree's contents."""
height = self.height()
nodes = [(self.root, 0)]
prev_level = 0
repr_str = ''
while nodes:
n,level = nodes.pop(0)
if prev_level != level:
prev_level = level
repr_str += '\n'
if not n:
if level < height-1:
nodes.extend([(None, level+1), (None, level+1)])
repr_str += '{val:^{width}}'.format(val='-', width=width//2**level)
elif n:
if n.left or level < height-1:
nodes.append((n.left, level+1))
if n.right or level < height-1:
nodes.append((n.right, level+1))
repr_str += '{val:^{width}}'.format(val=n.val, width=width//2**level)
print(repr_str)
def height(self):
"""Returns the height of the longest branch of the tree."""
def height_rec(t):
if not t:
return 0
else:
return max(1+height_rec(t.left), 1+height_rec(t.right))
return height_rec(self.root)
t = BSTree()
for x in range(6):
t.add(x)
t.pprint()
0 - 1 - - - 2 - - - - - - - 3 - - - - - - - - - - - - - - - 4 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 5
import sys
sys.setrecursionlimit(100)
t = BSTree()
for x in range(100):
t.add(x)
--------------------------------------------------------------------------- RecursionError Traceback (most recent call last) <ipython-input-4-cc289388a5df> in <module> 4 t = BSTree() 5 for x in range(100): ----> 6 t.add(x) <ipython-input-2-92b98e4d96ea> in add(self, val) 21 node.right = add_rec(node.right) 22 return node ---> 23 self.root = add_rec(self.root) 24 self.size += 1 25 <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 19 return node 20 else: ---> 21 node.right = add_rec(node.right) 22 return node 23 self.root = add_rec(self.root) <ipython-input-2-92b98e4d96ea> in add_rec(node) 14 def add_rec(node): 15 if not node: ---> 16 return BSTree.Node(val) 17 elif val < node.val: 18 node.left = add_rec(node.left) RecursionError: maximum recursion depth exceeded
class AVLTree(BSTree):
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rotate_right(self):
n=self.left
self.val,n.val=n.val,self.val
self.left,n.left, self.right, n.right = n.left, n.right, n, self.right
def add(self, val):
assert(val not in self)
def add_rec(node):
if not node:
return AVLTree.Node(val)
elif val < node.val:
node.left = add_rec(node.left)
return node
else:
node.right = add_rec(node.right)
return node
self.root = add_rec(self.root)
self.size += 1
t = AVLTree()
for x in range(6, 0, -1):
t.add(x)
t.pprint()
6 5 - 4 - - - 3 - - - - - - - 2 - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
t.root.rotate_right()
t.pprint()
5 4 6 3 - - - 2 - - - - - - - 1 - - - - - - - - - - - - - - -
t.root.rotate_right()
t.pprint()
4 3 5 2 - - 6 1 - - - - - - -
t.root.left.rotate_right()
t.pprint()
4 2 5 1 3 - 6
class AVLTree(BSTree):
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rotate_right(self):
n = self.left
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n.left, n.right, n, self.right
def rotate_left(self):
n = self.right
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n, self.left, n.right, n.left
@staticmethod
def height(n): # number of edges to furthest leaf from node n
# runtime? O(the number of nodes in the subtree rooted at n) O(n) at root
# not the best approach
if not n:
return 0
else:
return max(1+AVLTree.Node.height(n.left), 1+AVLTree.Node.height(n.right))
def __init__(self):
self.size = 0
self.root = None
self.rebalanceDone=False
def add(self, val):
assert(val not in self)
def add_rec(node):
if not node:
return AVLTree.Node(val)
elif val < node.val:
node.left = add_rec(node.left)
else:
node.right = add_rec(node.right)
# detect and fix imbalance AFTER RETURN FROM RECURSIVE CALLS
# on each node along the search path for the add, in reverse order bottom up
# is there an height imbalance more than 1 between left and right subtree
if AVLTree.Node.height(node.left) > AVLTree.Node.height(node.right)+1:
#assume it is a left-left issue, so we can fix with a single rotate right
# a left-right issue needs 2 rotations
node.rotate_right()
return node
#
self.root = add_rec(self.root)
self.size += 1
val = 50
t = AVLTree()
# (evaluate multiple times with ctrl-enter)
t.add(val)
val -= 1
t.pprint()
47 45 49 44 46 48 50
val = 0
t = AVLTree()
# (evaluate multiple times with ctrl-enter)
t.add(val)
val += 1
t.pprint()
0 - 1 - - - 2 - - - - - - - 3
# "left-left" scenario
t = BSTree()
for x in [3, 2, 1]:
t.add(x)
t.pprint()
3 2 - 1 - - -
t.root.rotate_right()
t.pprint()
2 1 3
# "left-right" scenario
t = BSTree()
for x in [3, 1, 2]:
t.add(x)
t.pprint()
3 1 - - 2 - -
t.root.left.rotate_left()
t.root.rotate_right()
t.pprint()
2 1 3
# "right-right" scenario
t = BSTree()
for x in [1, 2, 3]:
t.add(x)
t.pprint()
1 - 2 - - - 3
t.root.rotate_left()
t.pprint()
2 1 3
# "right-left" scenario
t = BSTree()
for x in [1, 3, 2]:
t.add(x)
t.pprint()
1 - 3 - - 2 -
t.root.right.rotate_right()
t.root.rotate_left()
t.pprint()
2 1 3
class AVLTree(BSTree):
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rotate_right(self):
n = self.left
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n.left, n.right, n, self.right
def rotate_left(self):
n = self.right
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n, self.left, n.right, n.left
@staticmethod
def height(n):
if not n:
return 0
else:
return max(1+AVLTree.Node.height(n.left), 1+AVLTree.Node.height(n.right))
def __init__(self):
self.size = 0
self.root = None
self.rebalanceDone=False
@staticmethod
def rebalance(t):
if AVLTree.Node.height(t.left) > AVLTree.Node.height(t.right):
if AVLTree.Node.height(t.left.left) >= AVLTree.Node.height(t.left.right):
# left-left
print('left-left imbalance detected')
# fix?
t.rotate_right()
else:
# left-right
print('left-right imbalance detected')
# fix?
t.left.rotate_left()
t.rotate_right()
else: # problem must be on right side
if AVLTree.Node.height(t.right.right) >= AVLTree.Node.height(t.right.left):
# right-right
print('right-rightt imbalance detected')
# fix?
t.rotate_left()
else:
# right-left
print('right-left imbalance detected')
# fix?
t.right.rotate_right()
t.rotate_left()
def add(self, val):
assert(val not in self)
def add_rec(node):
if not node:
return AVLTree.Node(val)
elif val < node.val:
node.left = add_rec(node.left)
else:
node.right = add_rec(node.right)
if not self.rebalanceDone and abs(AVLTree.Node.height(node.left)-AVLTree.Node.height(node.right)) > 1 : # detect imbalance
AVLTree.rebalance(node)
self.rebalanceDone=True
return node
self.root = add_rec(self.root)
self.size += 1
self.rebalanceDone=False
t = AVLTree()
for x in [10, 5, 1]:
t.add(x)
t.pprint()
left-left imbalance detected 5 1 10
t = AVLTree()
for x in [1, 5, 10]:
t.add(x)
t.pprint()
right-rightt imbalance detected 5 1 10
t = AVLTree()
for x in [5, 10, 7]:
t.add(x)
t.pprint()
right-left imbalance detected 7 5 10
t = AVLTree()
for x in [5, 1, 3]:
t.add(x)
t.pprint()
left-right imbalance detected 3 1 5
# broken!
t = AVLTree()
for x in [10, 5, 1, 2, 3]:
t.add(x)
t.pprint()
left-left imbalance detected right-rightt imbalance detected 5 2 10 1 3 - -
class AVLTree(BSTree):
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
self.height=1
def rotate_right(self):
n = self.left
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n.left, n.right, n, self.right
n.height = max(AVLTree.Node.h(n.left), AVLTree.Node.h(n.right))+1
self.height = max(AVLTree.Node.h(self.left), AVLTree.Node.h(self.right))+1
def rotate_left(self):
n = self.right
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n, self.left, n.right, n.left
n.height = max(AVLTree.Node.h(n.left), AVLTree.Node.h(n.right))+1
self.height = max(AVLTree.Node.h(self.left), AVLTree.Node.h(self.right))+1
@staticmethod
def h(n): # returns the height of a node in O(1)
if not n:
return 0
else:
if not n.left:
leftHeight=0
else:
leftHeight=n.left.height
if not n.right:
rightHeight=0
else:
rightHeight=n.right.height
return max(leftHeight, rightHeight)+1
@staticmethod
def height(n):
if not n:
return 0
else:
return max(1+AVLTree.Node.height(n.left), 1+AVLTree.Node.height(n.right))
def __init__(self):
self.size = 0
self.root = None
self.rebalanceDone=False
@staticmethod
def rebalance(t):
if AVLTree.Node.height(t.left) > AVLTree.Node.height(t.right):
if AVLTree.Node.height(t.left.left) >= AVLTree.Node.height(t.left.right):
# left-left
print('left-left imbalance detected')
# fix?
t.rotate_right()
else:
# left-right
print('left-right imbalance detected')
# fix?
t.left.rotate_left()
t.rotate_right()
else: # problem must be on right side
if AVLTree.Node.height(t.right.right) >= AVLTree.Node.height(t.right.left):
# right-right
print('right-rightt imbalance detected')
# fix?
t.rotate_left()
else:
# right-left
print('right-left imbalance detected')
# fix?
t.right.rotate_right()
t.rotate_left()
def add(self, val):
assert(val not in self)
def add_rec(node):
if not node:
return AVLTree.Node(val)
elif val < node.val:
node.left = add_rec(node.left)
else:
node.right = add_rec(node.right)
# if not self.rebalanceDone and abs(AVLTree.Node.height(node.left)-AVLTree.Node.height(node.right)) > 1 : # detect imbalance
if not self.rebalanceDone and abs(AVLTree.Node.h(node.left)-AVLTree.Node.h(node.right)) > 1 : # detect imbalance
AVLTree.rebalance(node)
self.rebalanceDone=True
node.height = max(AVLTree.Node.h(node.left), AVLTree.Node.h(node.right)) + 1
return node
self.root = add_rec(self.root)
self.size += 1
self.rebalanceDone=False
def pprint(self, width=64):
"""Attempts to pretty-print this tree's contents."""
height = self.height()
nodes = [(self.root, 0)]
prev_level = 0
repr_str = ''
while nodes:
n,level = nodes.pop(0)
if prev_level != level:
prev_level = level
repr_str += '\n'
if not n:
if level < height-1:
nodes.extend([(None, level+1), (None, level+1)])
repr_str += '{val:^{width}}'.format(val='-', width=width//2**level)
elif n:
if n.left or level < height-1:
nodes.append((n.left, level+1))
if n.right or level < height-1:
nodes.append((n.right, level+1))
repr_str += '{val:^{width}}'.format(val=str(n.val)+","+str(n.height), width=width//2**level)
print(repr_str)
t = AVLTree()
for x in [5, 1, 3]:
t.pprint()
t.add(x)
t.pprint()
- 5,1 5,2 1,1 - left-right imbalance detected 3,2 1,1 5,1
class AVLTree(BSTree):
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rotate_right(self):
n = self.left
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n.left, n.right, n, self.right
def rotate_left(self):
pass
@staticmethod
def height(n):
if not n:
return 0
else:
return max(1+AVLTree.Node.height(n.left), 1+AVLTree.Node.height(n.right))
@staticmethod
def rebalance(t):
if AVLTree.Node.height(t.left) > AVLTree.Node.height(t.right):
if AVLTree.Node.height(t.left.left) >= AVLTree.Node.height(t.left.right):
# left-left
print('left-left imbalance detected')
t.rotate_right()
else:
# left-right
print('left-right imbalance detected')
t.left.rotate_left()
t.rotate_right()
else:
pass
def add(self, val):
assert(val not in self)
def add_rec(node):
if not node:
return AVLTree.Node(val)
elif val < node.val:
node.left = add_rec(node.left)
else:
node.right = add_rec(node.right)
if abs(AVLTree.Node.height(node.left) - AVLTree.Node.height(node.right)) >= 2:
AVLTree.rebalance(node)
return node
self.root = add_rec(self.root)
self.size += 1
def __delitem__(self, val):
assert(val in self)
def delitem_rec(node):
if val < node.val:
node.left = delitem_rec(node.left)
elif val > node.val:
node.right = delitem_rec(node.right)
else:
if not node.left and not node.right:
return None
elif node.left and not node.right:
return node.left
elif node.right and not node.left:
return node.right
else:
# remove the largest value from the left subtree (t) as a replacement
# for the root value of this tree
t = node.left
if not t.right:
node.val = t.val
node.left = t.left
else:
n = t
while n.right.right:
n = n.right
t = n.right
n.right = t.left
node.val = t.val
# detect and fix imbalance
return node
self.root = delitem_rec(self.root)
self.size -= 1
t = AVLTree()
for x in [10, 5, 15, 2]:
t.add(x)
t.pprint()
del t[15]
t.pprint()
t = AVLTree()
for x in range(31, 0, -1):
t.add(x)
t.pprint()
del t[15]
del t[14]
t.pprint()
del t[16]
t.pprint()