# 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 __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-5-cc289388a5df> in <module> 4 t = BSTree() 5 for x in range(100): ----> 6 t.add(x) <ipython-input-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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-3-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()
t.add(3)
t.add(2)
t.add(1)
t.pprint()
3
2 -
1 - - -
t.root.rotate_right()
t.pprint()
2
1 3
t = AVLTree()
t.add(12)
t.add(15)
t.add(10)
t.add(8)
t.add(11)
t.add(13)
t.add(17)
t.add(5)
t.add(2)
t.pprint()
12
10 15
8 11 13 17
5 - - - - - - -
2 - - - - - - - - - - - - - - -
t.root.left.left.rotate_right()
t.pprint()
12
10 15
5 11 13 17
2 8 - - - - - -
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
@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 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))
ht = AVLTree.Node.height(n)
repr_str += '{val:^{width}}'.format(val=str(n.val)+','+str(ht), width=width//2**level)
print(repr_str)
class BSTree:
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
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)
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
@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.rebalanceOnInsert=False
def add(self, val):
assert(val not in self)
self.rebalanceOnInsert=False
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)
#after we come back to a node from its child (on the way back up from recursion)
# check right of left child and right, if differ by more than one, rotate
#assume we are only fixing left left imbalance
if not self.rebalanceOnInsert:
if AVLTree.Node.height(node.left)>AVLTree.Node.height(node.right)+1:
# we know the issue is to the left of "node"
if AVLTree.Node.height(node.left.left)>AVLTree.Node.height(node.left.right):
node.rotate_right() # case 1 L L
self.rebalanceOnInsert=True
else:
pass # case 2 L R
elif AVLTree.Node.height(node.left)+1<AVLTree.Node.height(node.right):
# we know the issue is to the right of "node"
if AVLTree.Node.height(node.left.left)>AVLTree.Node.height(node.left.right):
pass # case 3 R L
else:
pass # case 4 R R
node.rotate_left()
self.rebalanceOnInsert=True
# at most one imbalance per insert
return node
self.root = add_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))
ht = AVLTree.Node.height(n)
repr_str += '{val:^{width}}'.format(val=str(n.val)+','+str(ht), width=width//2**level)
print(repr_str)
val = 50
t = AVLTree()
# (evaluate multiple times with ctrl-enter)
t.add(val)
t.pprint()
50,1
t.add(49)
t.pprint()
50,2
49,1 -
t.add(48)
t.pprint()
49,2
48,1 50,1
t.add(47)
t.pprint()
49,3
48,2 50,1
47,1 - - -
t.add(46)
t.pprint()
49,3
47,2 50,1
46,1 48,1 - -
val = 0
t = AVLTree()
# (evaluate multiple times with ctrl-enter)
t.add(val)
val += 1
t.pprint()
# "left-left" scenario
t = BSTree()
for x in [3, 2, 1]:
t.add(x)
t.pprint()
3
2 -
1 - - -
# "left-right" scenario
t = BSTree()
for x in [3, 1, 2]:
t.add(x)
t.pprint()
3
1 -
- 2 - -
# "right-right" scenario
t = BSTree()
for x in [1, 2, 3]:
t.add(x)
t.pprint()
1
- 2
- - - 3
# "right-left" scenario
t = BSTree()
for x in [1, 3, 2]:
t.add(x)
t.pprint()
1
- 3
- - 2 -
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.right, n.right, self.left, n.left = n.right, n.left, n, self.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 rebalance(self, t):
if AVLTree.Node.height(t.left) > AVLTree.Node.height(t.right)+1:
if AVLTree.Node.height(t.left.left) > AVLTree.Node.height(t.left.right):
# left-left
t.rotate_right() # case 1 L L
self.rebalanceOnInsert=True
else:
# left-right
t.left.rotate_left()
t.rotate_right() # case 2 L R
self.rebalanceOnInsert=True
elif AVLTree.Node.height(t.left)+1 < AVLTree.Node.height(t.right):
# we know the issue is to the right of "node"
if AVLTree.Node.height(t.right.left)>AVLTree.Node.height(t.right.right):
# case 3 R L
t.right.rotate_right()
t.rotate_left()
self.rebalanceOnInsert=True
else:
# case 4 R R
t.rotate_left()
self.rebalanceOnInsert=True
def __init__(self):
self.size = 0
self.root = None
self.rebalanceOnInsert=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)
if not self.rebalanceOnInsert: # detect imbalance
self.rebalance(node)
return node
self.rebalanceOnInsert=False
self.root = add_rec(self.root)
self.size += 1
t = AVLTree()
for x in [10, 5, 1]:
t.add(x)
t.pprint()
5
1 10
t = AVLTree()
for x in [1, 5, 10]:
t.add(x)
t.pprint()
5
1 10
t = AVLTree()
for x in [1, 10, 5]:
t.add(x)
t.pprint()
5
1 10
t = AVLTree()
for x in [10, 1, 5]:
t.add(x)
t.pprint()
5
1 10
class AVLTree(AVLTree):
def __delitem__(self, val):
assert(val in self)
def delitem_rec(node):
nodes_to_check_for_imbalance=[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
nodes_to_check_for_imbalance.append(t)
if not t.right:
node.val = t.val
node.left = t.left
else:
n = t
while n.right.right:
n = n.right
nodes_to_check_for_imbalance.append(n)
t = n.right
n.right = t.left
node.val = t.val
# detect and fix imbalance
while nodes_to_check_for_imbalance:
self.rebalance(nodes_to_check_for_imbalance.pop()) #check all the nodes on the unwinding of the recursion
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()
10
5 15
2 - - -
del t[15]
t.pprint()
5
2 10
t = AVLTree()
for x in range(31, 0, -1):
t.add(x)
t.pprint()
16
8 24
4 12 20 28
2 6 10 14 18 22 26 30
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
del t[15]
del t[14]
t.pprint()
16
8 24
4 12 20 28
2 6 10 13 18 22 26 30
1 3 5 7 9 11 - - 17 19 21 23 25 27 29 31
del t[16]
t.pprint()
13
8 24
4 11 20 28
2 6 10 12 18 22 26 30
1 3 5 7 9 - - - 17 19 21 23 25 27 29 31