# Cs 61b: Final Review Data Structures

Yüklə 0,6 Mb.
 tarix 28.06.2018 ölçüsü 0,6 Mb. #52047

• ## Data Structures

• Binary Search Trees
• B-Trees
• Heaps
• Hash Tables
• AVL Trees
• ## Graphs

• DFS, BFS
• Topological Sort
• Strongly Connected Components

• ## High-level idea – 2 components

• Big array called hash table of size M
• Function h which maps keys to integer values

• ## Given the following AVL Tree, performs these consecutive operations and draw out the tree in each step:

• Remove(7)
• Insert (11)
• Insert(12)

• ## AVL Trees are just Binary Search Trees that can rotate their nodes to try to maintain balance.

• Two kinds of rotations – single and double
• Can decide which to do based on structure of tree

• ## You have 3 nodes of importance, which we will call x, y, and z (z is the parent of y which is the parent of x)

• If x is the right child of y, and y is the right child of z, you do a single rotation (same goes for left child of left child)
• If x is the right child of y, and y is the left child of z, you do a double rotation (same goes for left child of right child)

• ## Motivations:

• Modeling of simultaneous actions
• Counteract I/O Latency
• ## Mechanism: Multiple threads of control

• Shared memory space, multiple program counters
• ## Dangers:

• Shared access to memory can result in conflicts
• Multiple threads per processor can result in unequal time sharing (see scheduling)
• ## Conflict types:

• WAR (write after read)
• WAW (write after write)
• RAW (read after write)

• ## Large values => GOOD:

• throughput
• cpu utilization
• ## Large values => BAD (maybe):

• wait time
• turnaround time
• response time

• ## Justification:

• In a zero-sum-game, the best move for an opponent is to minimize your score, just as your best move is to maximize your score. This will therefore return the best possible move under the assumption that one’s opponent plays perfectly.

• ## The threaded tree:

• Motivations:
• Inorder traversals are common
• Naive BST implementation can waste space (~half of all child pointers are null)
• Mechanism:
• Add boolean flag to pointers (or do fun polymorphism) so as to have leaf nodes point to the next node in an inorder traversal
• Results:
• For a minimal change in the space requirements and structure of a tree, inorder traversals can now be computed using a straightforward iterative algorithm

• ## The B+ tree:

• Motivations:
• Range queries are common
• size of Data >> size of Key, so treat differently
• Mechanism:
• Differentiate between Leaf and index nodes. Index nodes hold keys, leaf nodes hold data. Key values for all data are in leaf nodes.
• Insert and delete as before, except keys are copied up on split, not moved, and keys may remain on delete for data that no longer exists
• Add next and previous fields to all leaf nodes, forming a doubly linked list
• Results:
• Range query now straightforward to return result for - tree now optimized for contiguous storage on physical media

• ## Thanks to CS 61b staff of

• Fall 2001
• Spring 2002

• ## Thanks to

• CMU – MIT
• Cornell – Johns Hopkins U
• ## for slide and example ideas

Yüklə 0,6 Mb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2023
rəhbərliyinə müraciət

Ana səhifə