Data Structures and Algorithms in Python Describe a modification to the binary s
ID: 3763951 • Letter: D
Question
Data Structures and Algorithms in Python
Describe a modification to the binary search tree data structure that would support the following two index-based operations for a sorted map in O(h) time, where h is height of the tree.
at_index(i): Return the position p of the item at index i of a sorted map.
index_of(p): Return the index i of the item at position p of a sorted map.
Please also give details of algorithms for implementing the above two operations, describe your modification and algorithm. Pseudo-code is preferred. All details of your modification and algorithm are required.
Explanation / Answer
LEFT = 0
_RIGHT = 1
_INDEX = 2
_SORT_ELEMENT = -1
class BinarySearchTree(object):
def
self._root = []
self._sort_element = sort_element
self._len = 0
def insert(self, index):
.
if self._sort_element is None:
sort_element = index
else:
sort_element = self._sort_element(index)
node = self._root
while node:
if sort_element < node[_SORT_ELEMENT]:
node = node[_LEFT]
else:
node = node[_RIGHT]
if sort_element is index:
node[:] = [[], [], index]
else:
node[:] = [[], [], index, sort_element]
self._len += 1
def minimum(self):
return self._extreme_node(_LEFT)[_INDEX]
def maximum(self):
return self._extreme_node(_RIGHT)[_INDEX]
def find(self, sort_element):
return self._find(sort_element)[_INDEX]
def pop_min(self):
return self._pop_node(self._extreme_node(_LEFT))
def pop_max(self):
return self._pop_node(self._extreme_node(_RIGHT))
def pop(self, sort_element):
return self._pop_node(self._find(sort_element))
def indexs(self, reverse=False):
if reverse:
return self._iter(_RIGHT, _LEFT)
else:
return self._iter(_LEFT, _RIGHT)
__iter__ = index
def __len__(self):
return self._len
def __nonzero__(self):
return self._len>0
def __repr__(self):
return '<BST: (%s)>' % ', '.join('%r' % v for v in self)
def __str__(self):
return self.pprint()
def pprint(self, max_depth=10, frame=True, show_element=True):
t,m,b = self._pprint(self._root, max_depth, show_element)
lines = t+[m]+b
if frame:
width = max(40, max(len(line) for line in lines))
s = '+-'+'MIN'.rjust(width, '-')+'-+ '
s += ''.join('| %s | ' % line.ljust(width) for line in lines)
s += '+-'+'MAX'.rjust(width, '-')+'-+ '
return s
else:
return ' '.join(lines)
def _extreme_node(self, side):
if not self._root:
raise IndexError('Empty Binary Search Tree!')
node = self._root
while node[side]:
node = node[side]
return node
def _find(self, sort_element):
node = self._root
while node:
node_element = node[_SORT_ELEMENT]
if sort_element < node_element:
node = node[_LEFT]
elif sort_element > node_element:
node = node[_RIGHT]
else:
return node
raise elementError("Element %r not found in BST" % sort_element)
def _pop_node(self, node):
index = node[_INDEX]
if node[_LEFT]:
if node[_RIGHT]:
successor = node[_RIGHT]
while successor[_LEFT]: successor = successor[_LEFT]
node[2:] = successor[2:]
successor[:] = successor[_RIGHT]
else:
node[:] = node[_LEFT]
else:
if node[_RIGHT]:
node[:] = node[_RIGHT]
else:
del node[:]
self._len -= 1
return index
def _iter(self, pre, post):
stack = []
node = self._root
while stack or node:
if node:
stack.append(node)
node = node[pre]
else:
node = stack.pop()
yield node[_INDEX]
node = node[post]
def _pprint(self, node, max_depth, show_element, spacer=2):
if max_depth == 0:
return ([], '- ...', [])
elif not node:
return ([], '- EMPTY', [])
else:
top_lines = []
bot_lines = []
mid_line = '-%r' % node[_INDEX]
if len(node) > 3: mid_line += ' (element=%r)' % node[_SORT_ELEMENT]
if node[_LEFT]:
t,m,b = self._pprint(node[_LEFT], max_depth-1,
show_element, spacer)
indent = ' '*(len(b)+spacer)
top_lines += [indent+' '+line for line in t]
top_lines.append(indent+'/'+m)
top_lines += [' '*(len(b)-i+spacer-1)+'/'+' '*(i+1)+line
for (i, line) in enumerate(b)]
if node[_RIGHT]:
t,m,b = self._pprint(node[_RIGHT], max_depth-1,
show_element, spacer)
indent = ' '*(len(t)+spacer)
bot_lines += [' '*(i+spacer)+'\'+' '*(len(t)-i)+line
for (i, line) in enumerate(t)]
bot_lines.append(indent+'\'+m)
bot_lines += [indent+' '+line for line in b]
return (top_lines, mid_line, bot_lines)
try:
from optimize_constants import bind_all
bind_all(BinarySearchTree)
except:
pass
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.