python - insert node then re-balance avl tree -
i'm creating 3 functions run off of insert function avl tree class. rebalance takes node unbalanced , uses rotate left , rotate right methods depeding on nodes situation. when load avl (avl = avl()) data1 = "abcdefghijklmnopqrstuvwxyz" , print using level order print method definitly doesnt turn out how supposed be. of see going wrong?
import copy list_array_1 import list class _avlnode: def __init__(self, value): """ ------------------------------------------------------- creates node containing value. use: node = _avlnode( value ) ------------------------------------------------------- preconditions: value - data node (?) postconditions: initializes avl node containing value. child pointers none, height 1. ------------------------------------------------------- """ self._value = copy.deepcopy(value) # new node added @ leaf. self._left = none self._right = none self._height = 1 return def _update_height(self): """ ------------------------------------------------------- updates height of current node. use: node._update_height() ------------------------------------------------------- postconditions: returns: true if node height has been changed, false otherwise. _height 1 plus maximum of node's 2 children. ------------------------------------------------------- """ old_height = self._height if self._left none: left_height = 0 else: left_height = self._left._height if self._right none: right_height = 0 else: right_height = self._right._height self._height = max(left_height, right_height) + 1 return self._height != old_height def _balance(self): """ ------------------------------------------------------- returns difference in height between left , right children of current node. use: balance = node._balance() ------------------------------------------------------- postconditions: returns: balance - difference in height between left , right children of node. value of -1, 0, or 1 indicates balance. -2 or less node unbalanced right; 2 or more node unbalanced left. (int) ------------------------------------------------------- """ if self._left none: left_height = 0 else: left_height = self._left._height if self._right none: right_height = 0 else: right_height = self._right._height balance = left_height - right_height return balance def __str__(self): """ ------------------------------------------------------- returns string version of node. debugging purposes. ------------------------------------------------------- postconditions: prints: contents of node in form "h: height, v: value" ------------------------------------------------------- """ return "h: {}, v: {}".format(self._height, self._value) class avl: def __init__(self): """ ------------------------------------------------------- initializes empty avl. use: avl = avl() ------------------------------------------------------- postconditions: initializes empty avl. ------------------------------------------------------- """ self._root = none self._count = 0 self.comparisons = 0 return def is_empty(self): """ ------------------------------------------------------- determines if avl empty. use: b = avl.is_empty() ------------------------------------------------------- postconditions: returns: true if avl empty, false otherwise (boolean) ------------------------------------------------------- """ return self._root none def __len__(self): """ ------------------------------------------------------- returns number of elements in avl tree. use: n = len( avl ) ------------------------------------------------------- postconditions: returns: number of values in avl tree (int) ------------------------------------------------------- """ return self._count def insert(self, value): """ ------------------------------------------------------- inserts new node containing value avl. avl may contain 1 copy of value. use: b = avl.insert(value) ------------------------------------------------------- preconditions: value - value insert avl (?) postconditions: returns: inserted - true if value has been inserted tree, false otherwise. ------------------------------------------------------- """ self._root, inserted = self._insert_aux(self._root, value) return inserted def _insert_aux(self, node, value): """ ------------------------------------------------------- inserts new node containing value new leaf of avl. avl may contain 1 copy of value. tree may rebalanced after insertion. private recursive operation called insert. use: node, inserted = self._insert_aux(node, value) ------------------------------------------------------- preconditions: node - current node examine existence of value (_avlnode) value - value insert avl (?) postconditions: returns: node - current node (_avlnode) inserted - true if value has been inserted tree, false otherwise (boolean) ------------------------------------------------------- """ if node none: # base case: create new node , increment node count. node = _avlnode(value) self._count += 1 inserted = true elif value < node._value: # general case: attempt insert value left. node._left, inserted = self._insert_aux(node._left, value) elif value > node._value: # general case: attempt insert value right. node._right, inserted = self._insert_aux(node._right, value) else: # base case: value in tree. inserted = false if inserted: # rebalance current node if necessary. node = self._rebalance(node) # return node. return node, inserted def retrieve(self, key): """ ------------------------------------------------------- retrieves value matching key in avl. (iterative) use: v = avl.retrieve( key ) ------------------------------------------------------- preconditions: key - data search (?) postconditions: returns: value - full value matching key, otherwise none (?) ------------------------------------------------------- """ node = self._root value = none while node not none , value none: self.comparisons += 1 if key < node._value: node = node._left elif key > node._value: node = node._right else: value = copy.deepcopy(node._value) return value def _rebalance(self, node): """ ------------------------------------------------------- rebalances current node if children not balanced. private operation called on insertion , deletion. use: node = self._rebalance(node) ------------------------------------------------------- preconditions: node - avl node rebalance (_avlnode) postconditions: node - avl node replaces original node (_avlnode) ------------------------------------------------------- """ if node._balance() <= -2 , node._right._balance() <= -1: node = node._rotate_left(node) elif node._balance() >= 2 , node._left._balance() >= 1: node = node.rotate_right(node) elif node._balance() <= -2 , node._left._balance() >= 1: node._right = node._right._rotate_right(node._right) node = node._rotate_left(node) elif node._balance() >= 2 , node._right._balance() <= -1: node._left = node._left._rotate_left(node._left) node = node.rotate_right(node) return node def _rotate_left(self, node): """ ------------------------------------------------------- rotates pivot left around right child. updates heights of rotated nodes. private operation called on rebalancing. use: node = self._rotate_left(node) ------------------------------------------------------- preconditions: node - pivot node rotate around (_avlnode) postconditions: node - node replaces pivot node (_avlnode) ------------------------------------------------------- """ temp = node._right._left new_root = node._right new_root._left = node node._right = temp node._update_height() return new_root def _rotate_right(self, node): """ ------------------------------------------------------- rotates pivot right around left child. updates heights of rotated nodes. private operation called on rebalancing. use: node = self._rotate_right(node) ------------------------------------------------------- preconditions: node - pivot node rotate around (_avlnode) postconditions: node - node replaces pivot node (_avlnode) ------------------------------------------------------- """ temp = node._left._right new_root = node._left new_root._right = node node._left = temp node._update_height() return new_root def __contains__(self, key): """ --------------------------------------------------------- determines if avl contains key. use: b = key in avl ------------------------------------------------------- preconditions: key - comparable data element (?) postconditions: returns: true if avl contains key, false otherwise (boolean) ------------------------------------------------------- """ value = self.retrieve(key) return value not none def height(self): """ ------------------------------------------------------- returns height of avl. use: h = avl.height() ------------------------------------------------------- postconditions: returns: h - current height of avl (int) ------------------------------------------------------- """ if self._root none: h = 0 else: h = self._root._height return h def inorder(self): """ ------------------------------------------------------- prints contents of tree in inorder order. use: avl.inorder() ------------------------------------------------------- postconditions: prints: contents of tree printed inorder. ------------------------------------------------------- """ self._inorder_aux(self._root) return def _inorder_aux(self, node): """ --------------------------------------------------------- traverses node subtree in inorder. private recursive operation called inorder. use: self._inorder_aux(node) --------------------------------------------------------- preconditions: node - avl node (_avlnode) postconditions: prints: children of node printed inorder. --------------------------------------------------------- """ if node not none: self._inorder_aux(node._left) print(node._value) self._inorder_aux(node._right) return def postorder(self): """ ------------------------------------------------------- prints contents of tree in postorder order. use: avl.postorder() ------------------------------------------------------- postconditions: prints: contents of tree printed postorder. ------------------------------------------------------- """ self._postorder_aux(self._root) return def _postorder_aux(self, node): """ --------------------------------------------------------- traverses node subtree in postorder. private recursive operation called postorder. use: self._postorder_aux(node) --------------------------------------------------------- preconditions: node - avl node (_avlnode) postconditions: prints: children of node printed postorder. --------------------------------------------------------- """ if node not none: self._postorder_aux(node._left) self._postorder_aux(node._right) print(node._value) return def preorder(self): """ ------------------------------------------------------- prints contents of tree in preorder order. use: avl.preorder() ------------------------------------------------------- postconditions: prints: contents of tree printed preorder. ------------------------------------------------------- """ self._preorder_aux(self._root) return def _preorder_aux(self, node): """ --------------------------------------------------------- traverses node subtree in preorder. private recursive operation called preorder. use: self._preorder_aux(node) --------------------------------------------------------- preconditions: node - avl node (_avlnode) postconditions: prints: children of node printed preorder. --------------------------------------------------------- """ if node not none: print(node._value) self._preorder_aux(node._left) self._preorder_aux(node._right) return def is_valid(self): """ --------------------------------------------------------- determines if avl valid. use: b = avl.is_valid() --------------------------------------------------------- postconditions: returns: valid - true if tree avl, false otherwise. --------------------------------------------------------- """ valid = self._is_valid_aux(self._root) return valid def _is_valid_aux(self, node): """ --------------------------------------------------------- helper function determine avl validity of node. private operation called is_valid. use: b = self._is_valid_aux(node) --------------------------------------------------------- preconditions: node - node check validity of (_avlnode) postconditions: returns: result - true if node avl, false otherwise (boolean) --------------------------------------------------------- """ if node none or (node._left none , node._right none): # base case: node empty or leaf, tree must avl. result = true elif abs(self._node_height(node._left) - \ self._node_height(node._right)) > 1: # base case: left or right subtree deep. print("height violation @ value: {}".format(node._value)) result = false elif (node._left not none , node._left._value > node._value) \ or (node._right not none , node._right._value < node._value): # base case: not follow bst property. print("binary tree violation") result = false else: # general case: check nodes children validity. result = self._is_valid_aux(node._left) , \ self._is_valid_aux(node._right) return result def _node_height(self, node): """ --------------------------------------------------------- helper function determine height of node - handles empty node. private operation called _is_valid_aux. use: h = self._node_height(node) --------------------------------------------------------- preconditions: node - node height of (_avlnode) postconditions: returns: height - 0 if node none, node._height otherwise (int) --------------------------------------------------------- """ if node none: height = 0 else: height = node._height return height def levelorder(self): """ ------------------------------------------------------- prints contents of tree in levelorder order. use: bst.levelorder() ------------------------------------------------------- postconditions: contents of tree printed levelorder. ------------------------------------------------------- """ if self._root not none: thislevel = [self._root] while thislevel not none: nextlevel = list() n in thislevel: print(n._value) if n._left not none: nextlevel.append(n._left) if n._right not none: nextlevel.append(n._right) thislevel = nextlevel print() if n._right none , n._left none: thislevel = none
Comments
Post a Comment