Data Structures
"Learn about cognition, executive functions, memory, and more from the perspective of a speech-language pathologist specializing in brain injuries. Understand the complexities of the brain and how cognitive impairments impact daily life."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Data Structures Lecture 3 Dynamic Sets / Dictionaries Binary Search Trees Haim Kaplan, Uri Zwick March 2018
Dictionaries/Dynamic sets Maintain a set of items. Each item has key and info fields. Keys belong to a totally ordered universe, and can be compared with each other Support the following operations: Insert, Delete, Search, Min, Max, Extremely useful data structure! 2
Abstract Data Type: Dictionaries Dic-Item(k,i) Create a dictionary item containing key k and info i, Key(I), Info(I) The key and info contained in Dic-Item I. Dictionary() Create an empty dictionary. Insert(D,I) Insert I into D. Delete(D,I) Delete I from D (assuming I is in D). Search(D,k) Find a Dic-Item with key k in D, if any. Min(D) Return the Dic-Item with the minimum key in D. Max(D) Return the Dic-Item with the maximum key in D. Successor(D,I) Return the successor of I in D. Predecessor(D,I) Return the predecessor of I in D. Assume that Dic-Items have distinct keys.
Implementing dictionaries using doubly linked lists (ver. 1) Store the Dic-Items in a list, in no particular order. Insert a new Dic-Item to an arbitrary position of the list, e.g., the first or last position. Delete a Dic-Item using a supplied pointer to it. Search, and other operations, are implemented by sequentially scanning the list. Insert, Delete O(1) time Other operations O(n) time 4
Implementing dictionaries using doubly linked lists (ver. 2) Store the Dic-Items in a list, in increasing order of keys. Insert a new Dic-Item to the appropriate position. Delete a Dic-Item by using a supplied pointer to it. Search is implemented by scanning the list, stopping when the key of the current item is larger than the key sought. Insert, Search O(n) time (or O(n/2) on average ) Delete O(1) time Min, Max, Successor, Predecessor O(1) time 5
Implementing dictionaries using (circular) arrays Store the Dic-Items in an array, in increasing order of keys. Insert a new Dic-Item to the appropriate position Delete a Dic-Item by using a supplied pointer to it. Search implemented using binary search. Insert, Delete O(n) time (or O(n/2) ) Min, Max, Successor, Predecessor O(1) time Search O(log n) 6
Binary search Successful search: Search(38) high mid low 10 25 38 47 56 67 73 84 95 0 1 2 3 4 5 6 7 8 7
Binary search Unsuccessful search: Search(39) high mid low 10 25 38 47 56 67 73 84 95 0 1 2 3 4 5 6 7 8 8
Binary search Key k was found in position mid Key k should be inserted in position mid or mid+1 9
Can we implement all operations in O(log n) time? Yes! Using Binary Search Trees 10
Binary search trees A binary tree in which each node contains a Dic-Item. Satisfies the binary-search-tree property: If y is in the left subtree of x, then y.key < x.key. If y is in the right subtree of x, then y.key > x.key. 7 x parent key info 2 8 right left 1 5 10 11
Binary search trees D.root 7 x parent key info 2 8 right left 1 5 10 Dic-Item Tree-Node left, right, parent are initially null 12
A set can be represented using several different binary trees 1 1 7 Linked List! 2 2 8 2 5 8 1 5 10 7 7 10 8 5 10 Which representation is better? We usually want trees that are not too deep. 13
Height 1 height=4 4 7 height=2 2 2 3 2 8 1 1 8 2 1 5 10 0 0 0 7 10 1 0 Height of a node length of a longest path down the tree to a leaf 5 0 ??? ? ? = 0 , if ? is a leaf. ??? ? ? = 1 + max ??? ? ?.???? , ??? ?(?.??? ?) , if ? is not a leaf. Height of a tree = height of root 14
Depth 1 depth=4 0 7 depth=2 0 2 1 2 8 1 1 8 2 1 5 10 2 2 2 7 10 3 3 Depth of a node length of the path up the tree to the root 5 4 ???? ? = 0 , if ? is the root. ???? ? = 1 + ???? ?.?????? , if ? is not the root. Depth of a tree = maximum depth = height of tree 15
Tree-Search(x,k) Look for k in the subtree of x x 7 x 2 8 x 1 10 5 Tree-Search(x,5) We usually start the search at the root of the tree: Search(D,k) Tree-Search(D.root,k) 16
Tree-Position(x,k) Look for k in the subtree of x Return the last node encountered y x 7 y x 2 8 y x 1 10 5 Tree-Position(x,6) Returns the node containing 5 Tree-Position(x,k) is used to find insertion points 17
Processing the items in sorted order (In-order walk) 7 3 2 1 8 4 1 5 10 2 5 0 Sorted-Order(?): if ? ???? then Sorted-Order(?.????) Process(?) Sorted-Order(?.??? ?) 18
Finding the minimum keep going left 7 2 8 1 5 10 19
Successor(x) The successor of ? is the item following ? according to the sorted order of keys. If x has a right child, the successor of x is the minimal element in x.right. x Go right once, and then left all the way . What if x.right=null ? 20
Successor(x) If x.right=null, the successor of x is the lowest ancestor y of x such that x is in its left subtree. y Go up from x until the first turn right . x 21
Successor(x) y If x has the largest key, then Successor(x)=null. x Predecessor is symmetric. 22
Insertions 7 2 8 1 5 10 6 9 Insert(6) Insert(9) 24
Deletion: easy cases 7 2 8 1 5 10 6 9 Delete(6) 6 is a leaf; simply remove it. Delete(8) 8 has only one child; bypass it. Delete(10) 10 has only one child; bypass it. Delete(2) more complicated 26
Deletion of a binary node If z has two children, let y be the successor of z y has no left child Remove y from the tree Replace z by y z y Binary-search-tree property preserved! Is it enough to let z.key y.key? And maybe also z.info y.info? 27
Analysis Each operation takes O(h+1) time, where h is the height of the tree In general h may be as large as n Want to keep the tree with small h 28
Balanced trees A full tree of height h contains n=2h+1 1 nodes h = log2(n+1) 1 How do we keep the tree more or less balanced? 29
Randomly built BSTs Maybe balancing will take care of itself? Not if we insert the elements in sorted order. We get a path of length n. Things are usually ok if we insert the elements in random order. Theorem: If n distinct keys are inserted into a BST in random order, then the expected height of the tree is O(log n). Proof identical to the analysis of quicksort, to be given at a later lecture. We want worst-case results 30
Rotations x y Right rotate y x C A Left rotate B B C A 31
