CMPT 225 Lecture Notes - Lecture 6: Binary Search Tree, Priority Queue, Binary Tree

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: John Edgar

Document Summary

First thing to be removed is item with highest priority. Actual priority could be based on anything you want. Inserting and remove in at most o(log n) time. Removal can only be done efficiently if ordered in some way. Bsts are fully ordered and insertion and removal can be implemented in o(log n) time. Operations complex (esp removal), though, and require a lot of structural overhead. Connected graph made up of nodes and edges. Exactly one less edge than number of nodes. Tree has leaves - nodes with no children. Binary tree - at most 2 children per node. In trees, nodes are only connected to 3 other nodes at most - parent and 2 children. Complete: all levels except bottom are completely filled in. Leaves on bottom are as far to the left as possible. (every node has two children other than bottom) Partially ordered: value of every node is greater than or equal to children.