BST coding Flashcards
initilaizing BSTNode class:
self.key = key;
self.value = value;
self.left = None;
self.right = None;
self.weight = 1
BST: get(self, key):
self.key == key: return self;
if self.key > key:
>if self.left: return self.left.get(key);
if self.key < key:
>if self.right: return self.right.get(key);
raise KeyError(“key {} is not in tree”.format(key))
-# recursive binary search
BSTNode get keyerror
raise KeyError(key: {} is not in tree”.format(key))
BST: put(self, key, value
if self.key == key: self.value = value;
elif self.key < key:
> if self.left: self.left.put(key, value);
else: self.left = BSTNode(key, value);
elif self.key > key:
> if self.right: self.right.put(key, value);
else: self.right = BSTNode(key, value);;
update_weight(self)
-# if <, out on left; if >, put on right; if self.l/r DNE, create one there
BST: update_weight(self):
left_weight = self.left.weight if self.left else 0;
right_weight = self.right.weight if self.right else 0;
self.weight = left_weight + right_weight + 1
BST runtime
generally, O(logn) operations
Priority Queue runtime
O(n)
Priority queue runtime - reverse sorted
O(n) insert;
O(1) findmin()
upheap runtime
O(logn)
upheap
append, swap w parent until order is restored
downheap
swap last element w root;
pop; removes old root;
swap new root with min child until order is restored
downheap runtime
O(n)
