COSC 2320 Study Guide - Final Guide: Adjacency Matrix, Treap, Avl Tree

• School: University of Houston
• Department: Computer Science
• Course: COSC 2320
• Professor: Hilford Victoria

Document Summary

Binary trees: definitions, binary tree - a node with up to two children. If current node = key: return current node, else if key < current node, check left subtree, repeat if key not found. Else: check right subtree, repeat if key not found. Insert algorithm: obeys bst ordering property at all times. If key < current node: assigns the node to left subtree, else key > current node, assigns the node to right subtree, remove algorithm, removing leaf node, removes leaf, removing internal node. If single child: assign single child to parent/root. If two children: assign successor to current node, takes o(log2(n)) long, bst traversal, preorder traversal root, left, right. Inorder traversal left, root, right: postorder traversal left, right, root, levelorder traversal top to bottom, left to right. Insert uses bst for main key, then assigns random priority to the node based on heap property: delete heap property.