Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
1.4.2 b pt 2
1.4.2
| Question | Answer |
|---|---|
| Trees | Consists of nodes connected by pointers/edges; each node can be reached from anywhere |
| Tree parts | - Node at the start is the root node - Nodes immediately down from any node are the children - Nodes at the very bottom of a tree are leaf nodes - A subtree is a set of nodes and edges from any node down all its descendents |
| Tree applications | - Storing and managing file and folder structures - Family tree |
| Binary tree | special type of graph Similar to a tree, with nodes/vertices and pointers/edges |
| Binary tree special rule | Each node can only have 0, 1 or 2 children, so that each have: - A left pointer (to its ‘left child’) - data/value - A right pointer (to its ‘right child') |
| Array: Implementing binary tree | in a table, with pointers set to null if there is no child node |
| Object-oriented: Implementing binary tree | objects with a left and right pointer that may be set to null Class Node Element = “” Left_pointer = Node Right_pointer = Node End class |
| Binary tree diagram | |
| Binary tree applications | - Wireless networking - OS scheduling methods |
| Binary tree operations | - Add - Delete - Binary search: returns data stored in a node - Pre order, in order and post order traversal: types of depth-first search - Breadth-first search |
| Add (binary tree) (object oriented) | |
| Delete (binary tree) | |
| Leaf node being deleted (delete, binary tree) | 3. if previous node is greater then current, previous nodes left pointer equals null 4. And vice versa |
| One child (delete, binary tree) | 3. If current is less then previous bode: a. Set the previous node’s left pointer to the current node’s left child 4. If it is greater then: a. Set the right pointer |
| Hibbard deletion (delete, binary tree) | |
| Pre-order (binary tree) | variation of depth-fist search (node-left-right) 1. Start at root node 2. Output node 3. Follow left pointer and repeat from step 2 recursively until there is no pointer to follow 4. Follow the right pointer and repeat from step 2 recursively, etc. |
| Pre-order diagram (binary tree) | |
| In-order (binary tree) | depth-first variation (left-node-right) Automatically sorts data as outputs 1. Start at root node 2. Follow left pointer and repeat from step 2 recursively until there is no pointer to follow 3. Output node 4. Follow the right pointer etc. |
| In-order diagram (binary tree) | |
| Post-order (binary tree) | depth-first variant (left-right-node) 1. Start at root node 2. Follow from left pointer and repeat from 2 recursively until there is no pointer to follow 3. Follow from the right pointer etc. 4. Output node |
| Post-order diagram (binary tree) | |
| Types of binary tree | Binary search tree: all values to the left are less than node’s value, vice versa |
| Hash tables | Aims to immediately find an item in a sorted or unsorted list without comparing with other items Must be large enough to store all data items, often is larger to minimise collision Hashing function determines a hash value |
| Hash value | position in a hash table |
| Good hashing function properties | - Be calculated quickly - Result in as few collisions as possible - Use as little memory as possible |
| Collisions (hash tables) | Where two items have the same hash value |
| Collisions solutions (hash tables) | - Open addressing - 2D hash tables - Overflow table/linked list |
| Open addressing (hash tables) | store the item in the next available space - To find the item use linear probing - This prevents other items other items from being stored in their correct locations, and lead to clustering |
| Linear probing | a linear search from the hash value |
| Clustering | where frequent collisions lead to long stretches of filled slots in the hash table |
| 2D hash tables | (like 2D arrays) prevent collisions by using chaining |
| Chaining | placing more than one item at the same position |
| Overflow table/linked list | allows chaining |
| Hash tables operations | - add - delete - retrieve |
| Add (hash tables) | |
| Delete (hash tables) | |
| Retrieve (hash tables) | |
| Hash tables applications | - Databases - Password hashing |
Created by:
FlashCardFun!