Fichas
Week 10: Data Structures for Search & Retrieval
Fichas del conjunto (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
Información
- Descripción
- (FIT1045: Algorithms & Programming Fundamentals in Python) Computer Science Fichas sobre Week 10: Data Structures for Search & Retrieval, creado por Melina Mackey el 25/10/2019.
- Creado por
- Melina Mackey
- Visitas
- 0
- Historial
-
- Creado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 16 sep 2019
- Copiado por Melina Mackey · 18 sep 2019
- Copiado por Melina Mackey · 21 sep 2019
- Copiado por Melina Mackey · 24 oct 2019
- Copiado por Melina Mackey · 25 oct 2019
- Valoración