Flashcards
Week 10: Data Structures for Search & Retrieval
Cards in this deck (10)
- 1Rooted tree terminology- Rooted tree is a tree T = (V, F) where we have chosen one vertex r as root
- Parent of a vertex v is the predecessor p of v on the unique path P = [r,…, p, v] to v from the root (where v is the child of p)
- Leaf is a vertex without children
- Inner vertex is a vertex with children
- Height of a tree is the length of the longest path from the root to a leaf - 2Binary tree- Rooted tree where every node has at most two ordered children, referred to as the left and right child
- Every subtree of a binary tree is a binary tree => recursive implementation
- Empty tree is also a binary tree - 3Binary tree representation- Pair-of-children list: at position i is a pair of indices corresponding to root of the left and right subtree of vertex i
- Root of full tree at position 0
- None indicates empty subtree - 4Binary search treeA vertex-labelled binary tree with the properties:
- Labels of each vertex in its left subtree is less than its label
- Labels of each vertex in its right subtree is greater than its label
- No duplicate values - 5Binary search tree operationsSearch - returns index of vertex with value (or -1 if no such vertex exists)
Insertion - adds new vertex to tree with label equal to value, preserving properties
- 6Perfect binary treeAll inner vertices have 2 children and all leaves have the same level
- 7Balanced and degenerate binary trees- Degenerate tree occurs when values are inserted in sorted order (very unlikely to happen when inserting in random order)
- Balanced binary tree - for all vertices, the absolute difference between the heights of the left subtree and right subtree <= 1 - 8Min heap- Use to repeatedly extract minimum element in a changing set of objects
- A vertex-labelled binary tree with:
1. Shape property: (essentially) complete => only some rightmost vertices on the last level are missing
2. Order property: no vertex has a larger label than either of its children - 9Min-heap relations
- 10Min-heap operationsExtract min - returns the minimum label, removes its vertex from the heap, and restructures the heap to restore properties
Insertion - adds new vertex with value to the heap, preserving properties
Information
- Description
- Computer Science (FIT1045: Algorithms & Programming Fundamentals in Python) Flashcards on Week 10: Data Structures for Search & Retrieval, created by Melina Mackey on 25/10/2019.
- Created by
- Melina Mackey
- Views
- 0
- History
-
- Created by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 16, 2019
- Copied by Melina Mackey · Sep 18, 2019
- Copied by Melina Mackey · Sep 21, 2019
- Copied by Melina Mackey · Oct 24, 2019
- Copied by Melina Mackey · Oct 25, 2019
- Rating