CS130A: Midterm 2 Cheat Sheet
CS130A: Midterm 2 Cheat Sheet
Popular in Course
verified elite notetaker
Popular in ComputerScienence
Ted Robel Sr.
verified elite notetaker
This 2 page Bundle was uploaded by logeybearrr on Friday June 6, 2014. The Bundle belongs to a course at University of California Santa Barbara taught by a professor in Fall. Since its upload, it has received 97 views.
Reviews for CS130A: Midterm 2 Cheat Sheet
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 06/06/14
BINARY SEARCH TREEs delete when both children are not NULL find min in right subtree successor swap location values and recursively delete the original location of successor delete with one child NULL and the other not simply shift the existing child to the deleted nodes location AVL TREEs each parent has two children with heights differing no more than one NULL height is equal to 1 when inserting check every parent node along shortest path to the root to ensure the heights of its children differ no more than one rightright imbalance rotate node in violation LEFT leftleft imbalance rotate node in violation RIGHT rightleft imbalance rotate right child of violate node RIGHT and rotate newly violate node LEFT leftright imbalance rotate left child of violated node LEFT and rotate newly violated node RIGHT SPLAY TREEs operations are handled like a BST but at the ned a splay operation occurs splaying ensures all operations run in Olog n splay operation moves x to the root of the tree to solve the issue of locality reaccess result a final binary tree more balanced than original unless operation near root is done search splay node where key was found successful or last visited internal node unsuccessful insert splay newly added node delete splay parent of removed node all splay operations runs in 0h ZigZig leftleft or rightright depth decreases by two x has a grandparent zig no grandparent depth decreases by one x has IQ grandparent so y is the root Note w could be NIL DISJOINT UNION SETS Arbitrary root nodes value 1 Union by Size root holds negate value of size including root unionxy Make root of larger tree the new root Union by Height root holds negative value of largest height including itself as one unionxy Link smaller tree to larger height tree findx returns value of root of set containing x uniongt01 findgt0n m unions of n elementsgt0mog n Path Compression after finding the root r of the tree containing x change the parent pointer of all nodes along the path to point directly to r GRAPHS Undirected Graph E VV1 2 Directed Graph called symmetric if for every edge the inverted edge exists equivalent to undirected graph Loop an edge directed or undirected which starts and ends on the same vertex Multigraph two vertices can be connected by more than one edge Quiver multidigraph Simple no loops and no more than one edge between any two different vertices Weighted each edge is a assigned a number of priority Regular each vertex has the same number of neighbors Complete every pair of distinct vertices is connected by a unique edge Connected there is a path from every node to every other node Strongly Connected there is a path from every node to every other node for a directed graph Weakly Connected treat the edges as undirected and there is a path from every node to every other node for a directed graph Path record of vertices and edges visited Minimum Spanning Tree Prim from a source vertex check all directly and indirectly connected edges and choose the smallest edge repeat until all vertices are connected without making a cycle Kruskal connect all edges in increasing size until all vertices are connected without creating a cycle Matrix 1 List Space 0Vquot2 0VE Add Vertex 0Vquot2 01 Add Edge 01 01 Remove Vertex 0Vquot2 0VE Remove Edge 01 0E Search 0V 01 Topological Sort next page BTREES Disk Block Size 2048 bytes Branches 4 bytes Keys 4 bytes Records 256 bytes 4 accessess and 4 mill insts 1 disk readwrite 025 s 4151 ll 62l72 87 iigi li 99l 4 I Find Time heightdisk RN time 0102 v 39i it v double for insertions and deletions 33 41 51 56 62 72 31 87 94 99 4v1 4M lt 2048 35 43 53 53 64 74 33 89 96 101 4244 am 3 2 55 6 22 3 85 2 98 is Leaf Nodes 49 70 no branches 2 no keys ceiL2L records vj414 Non Leaf Nodes ceilM2 M branches ceilM21M1 keys Z no records 3 V4 Root Node 2 to M branches 1 to M1 keys no records 39ltiulty39 Max Records MquotHL 1eaVeS N 1N L 21 Indegree Before Dequeue Non Leaves each non leaf node has ceilM21 M1 keys Vertex 1 2 3 4 5 6 7 each non leaf node will have that many leaves So there will be ceilNLM1 CeiNL2 ceilM21 non leaf nodes xi 0 0 0 0 0 0 0 Range of Height logM2 NL logM2 NL2 logMNL logMNL2 V2 1 0 0 0 0 0 0 insert when full V3 2 1 1 1 0 0 0 adoption give largest to right sibling or smallest to left 111 3 2 1 O 0 O 0 splitting choose a median key smaller records to left sibling and median and larger records to right sibling 395 1 1 0 O 0 0 O deletion and underflow borrow from right or left sibling if it has 116 3 3 3 3 2 1 0 enough otherwise merge with a sibling 1 deletion from internal lode borrow from left or right leaf Vquot 2 2 2 1 0 0 0 Enqueue V3 V V V4 v3 v1 V11 Dequeue vi 1 v V4 v v vb Data Structures Data Structure 1 Ime Complexity Space Complexity Average Worst Worst Indexing Search Insertion Deletion Indexing Search Insertion Deletion Array 4 4 4 4 Dvnamimrav I Z Z I I Z I I singlyLinked Skioust Z X j j Z Z I C j I 4 4 P Z 1 Z 1 Tree 4 1 1 1 4 BTree j j X j j j j j Z RedBiacktree X j X j j X j j I splay Tree 4 j j Z Z X j Avttree j j j Z j Z Z Z I
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'