Based on the following code fragments: - Code Fragment 8.1 - page 307 - Code Fragment 8.2 - page 308 - Code Fragment 8.7 - page 314 - Code Fragment 8.8 - page 320 - Code Fragment 8.9 - page 321 - Code Fragment 8.10- page 322 - Code Fragment 8.11 - page 323 1. Add support in LinkedBinaryTree for a method, delete_subtree(p), that removes the entire subtree rooted at position p, making sure to maintain the count on the size of the tree. 2. Add support in LinkedBinaryTree for a method, swap(p,q), that has the effect of restructuring the tree so that the node referenced by p takes the place of the node referenced by q, and vice versa. Make sure to properly handle the case when the nodes are adjacent. 3. Use one of the traversal algorithm to display() the LinkedBinaryTree elements. Inpplementing Trees 323 120 def delete(self, p): 121 "*"Delete the node at. Position p. and replace it with its child, if any. 122 Retarn the element that had been stored at Position p. 124 Raise ValueError if Position p is invalid or has two children. 125 node = selt._validate(p) if self.num_children (p)==2 : raise ValueError( ' p has two children') child = node.left if node. -left else node. -right \# might be None if child is not None: child._parent = node__parent \# child's grandparent becomes parent if node is self._root: self._root = child \# child becomes root else: parent = node._parent if node is parent._left: parent._left = child else: parent_right = child self.-size =1 node.-parent = node # corriention for deprecated node return node._element def -attach(self, p,t1,t2) : "." Attach trees t1 and t2 as left and right subtrees of external p."." node = self.-validate( p ) if not self. is Jeaf(p): raise ValueError('position must be leaf') if not type(self) is type(t1) is type(t2): \# all 3 trees must be same type raise TypeError("Tree types must mateh') self.-size +=len(t1)+len(t2) if not t1 is_empty( ): \# attached ti as left subtree of node t1._root_parent = node node. Jeft =t1. root t1._root = None \# set. t1 inseance to empty. t1. size =0 if not t2 is_empty(). \# attached 12 as right subtree of node t2._root_-parent = node node.right =12.-root t2. root = None \# set t2 instance to empty t2. size =0 Chapter \&. Trees def _add_root(self, e): "" "Place element e at the root of an empty tree and retum new Position. Raise Valuefrme if tree nneemnty if self._root is not None: raise ValueError('root exists') self._size =1 self._root = self._Node(e) return self._make_position(self.-root) def _add_left(self, , e): "" "Create a new left child for Position p. storing element e. Return the Position of new node. Raise ValueError if Position p is invalid or p already has a left child. node = self._validate( p) if node._left is not None: raise ValieeError('Left child exists') self. size t=1 node.left = self.. Node(e, node ) \# node is its parent. return self._make_position(node._left) def_add_right(self, p,e) : "'" Create a new right child for Position p, storing element e Return the Position of new node. Raise ValueError if Position p is invalid or p already has a right child. node = self. validate (p) if node.-right is not None: raise ValueError("Right child exists") self._size t=1 node._right = self._Node(e, node) \# node is its parent. return self._make_position(node__right) def_replace(self, p, e): "" Replace the element at position p with e, and return oid element.""." node = self._validate( p ) old = node-element node. element =e return old: mplementing Trees 321 Chapter \& Trees class LinkedBinary Tree(BinaryTree): "" "Linked representation of a binary tree structure." " class _Node: \# Lightweight, nonpublic class for storing a node. - slots.n= '_element', '_parent', "_left', '_right' def _init__(self, element, parent=None, left = None, right = None): self._element = element. self__parent = parent self.-left = left self.-right = right class Position(BinaryTree. Position): "n" An abstraction representing the location of a single element" def _ init__(self, container, node): ".". Lonstructor should not be invoked by aser.' self. . container = container self._node = node def element(self): "n" Return the element stored at this Position. "" return self._node..element def -eq-(self, other): "*" Retum True if other is a Position representing the same location." "" return type(other) is type(self) and other. -node is self _node def _validate(self, p) : "w" Retum associated node, if position is valid." if not isinstance( p, self.Position): raise TypeError(' p nust be proper Position type') if p._container is not self. raise ValueError('p does not: belong to this container') if p-node.-parent is p.-node: # convention for deprecated nodes raise ValueError('p is no longer valid') return p._node def make.position(self, node): "" Retum Position instance for given node (or None if no node)."" return self.Position (self, node) if node is not None else None Code Fragment 8.8: The beginning of our LinkedBinary Tree class (continued in Code Fragments 8.9 through 8.11 ). eral Trees 307 class Tree: "Tr" "Abstract base class representing a tree structure." " \# abstract methods that concrete subclass must support - def root(self): "" "Return Position representing the tree's toot (or None if empty)."" raise NotlmplementedError('must be implemented by subelass') def parent(self, p): "'" Return Position representing p s parent (or None if p is root)." .'. raise NotImplementedError('must be implemented by subelass') def numuchildren(self, p): "" Return the number of children that Position p has." " raise NotlmplementedError('must be implemented by subclass') def children(self, p): "" "Generate an iteration of Positions representing p15 children," "= raise NotlmplementedError( 'nust be implemented by subclass") def -len-m(self): "" "Return the total number of elements in the tree."" raise NotlmplementedError('must be implemented by subclass') Code Fragment 8.1: A portion of our Tree abstract base class (continued in Code Fragment 8.2). 8 Chapter \&. Trees class Binary Tree(Tree): "*" Abstract base class representing a binary tree structure." def left(self, p): "*" Return a Position representing p s left child. Return None if does not have a left chid. raise NotlmplementedError('must be implenented by subclass') def right(self, p) "n" Return a Position representing p s right child. Return None if p does not have a right child raise NotimplementedError('must be inplenented by subclass') \# concrete methods implemented in this class - def sibling(self, p): ""Return a Position representing p s sibling (or None if no sibling)."n" parent = self.parent(p) if parent is None: \# P must be the root return None else: if p== self.left(parent): return self.right(parent) \# \# possibly None else: return self.left(parent) \# possibly None def children(self, p ): "" Generate an iteration of Positions representing. pI5 s children."." if self.left(p) is not None: yield self.left (p) if self.right (p) is not None: yield self.right(p) Code Fragment 8.7: A Binary Tree abstract base class that extends the existing Tree abstract base class from Code Fragments 8.1 and 8.2