Understanding AVL Trees in Data Structures

cse 373 data structures and algorithms n.w
1 / 34
Embed
Share

Learn about AVL trees in data structures and algorithms, including the four cases to consider for insertion and the various rotation solutions. Explore how AVL trees enable efficient dictionary operations like get(k) in constant time. Dive into the concepts taught in CSE 373 during the Autumn 2018 term by Shrirang Mare, with thanks to various contributors for sample slides and materials.

  • AVL Trees
  • Data Structures
  • Algorithms
  • Hash Tables
  • CSE 373
rayaanacharya
sebastyn Follow

Uploaded on | 0 Views

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.

Download 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.

E N D

Presentation Transcript

  1. CSE 373: Data Structures and Algorithms Hash Tables Autumn 2018 Shrirang (Shri) Mare shri@cs.washington.edu Thanks to Kasey Champion, Ben Jones, Adam Blank, Michael Lee, Evan McCarty, Robbie Weber, Whitaker Brand, Zora Fung, Stuart Reges, Justin Hsia, Ruth Anderson, and many others for sample slides and materials ...

  2. Today - Wrap up AVL Trees - Problem: Can we make get(k) operation on dictionaries fast: O(1) - Motivation - Hashing - Separate Chaining CSE 373 AU 18 SHRI MARE 2

  3. AVL Trees: Four cases to consider Insert location Left subtree of left child of y (A) Right subtree of left child of y (B) Left subtree of right child of y (C) Right subtree of right child of y (D) Case Left line case Left kink case Right kink case Right line case Solution Single right rotation Double (left-right) rotation Double (right-left) rotation Single left rotation y x z D A C B CSE 373 AU 18 SHRI MARE

  4. AVL Trees: Four cases to consider Insert location Left subtree of left child of y (A) Right subtree of left child of y (B) Left subtree of right child of y (C) Right subtree of right child of y (D) Case (also called as) Left line case (case 1) Left kink case (case 2) Right kink case (case 3) Right line case (case 4) Solution Single right rotation Double (left-right) rotation Double (right-left) rotation Single left rotation y x z D A C B CSE 373 AU 18 SHRI MARE

  5. AVL Tree: Practice. Insert(6) CSE 373 AU 18 SHRI MARE 5

  6. AVL Tree: Practice Unbalanced CSE 373 AU 18 SHRI MARE 6

  7. AVL Trees: Four cases to consider Insert location Left subtree of left child of y (A) Right subtree of left child of y (B) Left subtree of right child of y (C) Right subtree of right child of y (D) Case (also called as) Left line case (case 1) Left kink case (case 2) Right kink case (case 3) Right line case (case 4) Solution Single right rotation Double (left-right) rotation Double (right-left) rotation Single left rotation y x z D A C B CSE 373 AU 18 SHRI MARE

  8. y AVL Tree: Practice x z D A C B Unbalanced CSE 373 AU 18 SHRI MARE 8

  9. y AVL Tree: Practice x z D A C B Unbalanced CSE 373 AU 18 SHRI MARE 9

  10. Worksheet Q1 insert(1) 6 4 8 2 5 Case: Line or Kink? CSE 373 AU 18 SHRI MARE 10

  11. Worksheet Q1 insert(1) 6 4 8 2 5 1 Case: Line or Kink? CSE 373 AU 18 SHRI MARE 11

  12. Worksheet Q1 insert(1) insert(3) 6 6 4 8 4 8 2 5 2 5 Case: Line or Kink? 1 Case: Line or Kink? CSE 373 AU 18 SHRI MARE 12

  13. Worksheet Q1 insert(1) insert(3) 6 6 6 4 8 4 4 8 8 2 5 2 2 5 5 Case: Line or Kink? 1 3 Case: Line or Kink? CSE 373 AU 18 SHRI MARE 13

  14. AVL Tree insertions 1. Do a BST insert insert a node as you would in a BST. 2. Check balance condition at each node in the path from the inserted node to the root. 3. If balance condition is not true at a node, identify the case 4. Do the corresponding rotation for the case CSE 373 AU 18 SHRI MARE 14

  15. Worksheet Q2 Draw the AVL tree that results from inserting the keys 1, 3, 7, 5, 6, 9 in that order into an initially empty AVL tree. (Hint: Drawing intermediate trees as you insert each key can help.) CSE 373 AU 18 SHRI MARE 15

  16. How long does AVL insert take? AVL insert time = BST insert time + time it takes to rebalance the tree = O(log n) + time it takes to rebalance the tree How long does rebalancing take? -Assume we store in each node the height of its subtree. -How long to find an unbalanced node: -Just go back up the tree from where we inserted. -How many rotations might we have to do? -Just a single or double rotation on the lowest unbalanced node. AVL insert time = O(log n)+ O(log n) + O(1) = O(log n)

  17. How long does AVL insert take? AVL insert time = BST insert time + time it takes to rebalance the tree = O(log n) + time it takes to rebalance the tree How long does rebalancing take? -Assume we store in each node the height of its subtree. -How long to find an unbalanced node: -Just go back up the tree from where we inserted. O(log n) -How many rotations might we have to do? -Just a single or double rotation on the lowest unbalanced node. O(1) AVL insert time = O(log n)+ O(log n) + O(1) = O(log n)

  18. AVL wrap up Pros: - O(log n) worst case for find, insert, and delete operations. - Reliable running times than regular BSTs (because trees are balanced) Cons: - Difficult to program & debug [but done once in a library!] - (Slightly) more space than BSTs to store node heights. CSE 373 AU 18 SHRI MARE 18

  19. Lots of cool Self-Balancing BSTs out there! Popular self-balancing BSTs include: AVL tree Splay tree 2-3 tree AA tree Red-black tree Scapegoat tree Treap (Not covered in this class, but several are in the textbook and all of them are online!) (From https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree#Implementations) CSE 373 SU 17 LILIAN DE GREEF

  20. Announcements - HW3 out. Due this Friday (10/26) at Noon - HW4 out later today (or latest by tomorrow morning). Due next Tuesday (10/30) Noon (not at the usual time 11:59pm) - Midterm coming up Nov 2, 2:30-3:20pm, here in the class - If you can t take the midterm on Nov 2, let me know ASAP. - Midterm practice material will be posted on the website tomorrow - Midterm review next Wednesday CSE 373 AU 18 SHRI MARE 20

  21. Hash tables CSE 373 AU 18 SHRI MARE 21

  22. Revisiting Dictionaries - data = (key, value) - operations: put(key, value); get(key); remove(key) - O(n) with Arrays and Linked List - O(log n) with BST and AVL trees. - Can we do better? Can we do this in O(1) ? CSE 373 AU 18 SHRI MARE 22

  23. Motivation Why we are so obsessed with making dictionaries fast? Dictionaries are extremely most common data structures. - Databases - Network router tables - Compilers and Interpreters - Faster than O(log n) search in certain cases - Data type in most high level programming languages CSE 373 AU 18 SHRI MARE 23

  24. Question How would you implement at dictionary such that dictionary operations are O(1)? (Assume all keys are non-zero integers) CSE 373 AU 18 SHRI MARE 24

  25. Question How would you implement at dictionary such that dictionary operations are O(1)? (Assume all keys are non-zero integers) Idea: Idea: Create a giant array and use keys as indices CSE 373 AU 18 SHRI MARE 25

  26. Question How would you implement at dictionary such that dictionary operations are O(1)? (Assume all keys are non-zero integers) Idea: Idea: Create a giant array and use keys as indices Problems? 1. ? 2. ? CSE 373 AU 18 SHRI MARE 26

  27. Question How would you implement at dictionary such that dictionary operations are O(1)? (Assume all keys are non-zero integers) Idea: Idea: Create a giant array and use keys as indices Problems? 1. Can only work with integer keys? 2. Too much wasted space Idea 2: Idea 2: Can we convert the key space into a smaller set that would take much less memory CSE 373 AU 18 SHRI MARE 27

  28. Solve problem: Too much wasted space CSE 373 AU 18 SHRI MARE 28

  29. Review: Integer remainder with % The % operator computes the remainder from integer division. 14 % 4 is 2 3 4 ) 14 5 ) 218 12 20 2 18 15 3 218 % 5 is 3 43 Applications of % operator: - Obtain last digit of a number:230857 % 10 is 7 - See whether a number is odd: 7 % 2 is 1, 42 % 2 is 0 - Limit integers to specific range: 8 % 12 is 8, 18 % 12 is 6 CSE 142 SP 18 BRETT WORTZMAN 29

  30. Implement Direct Access Map public V get(int key) { // input validation return this.array[key].value; } public void put(int key, V value) { this.array[key] = value; } public void remove(int key) { // input validation this.array[key] = null; } CSE 373 WI 18 MICHAEL LEE 30

  31. Implement First Hash Function public V get(int key) { // input validation int newKey = key % this.array.length; return this.array[newkey].value; } public void put(int key, V value) { this.array[key % this.array.length] = value; } public void remove(int key) { // input validation int newKey = key % this.array.length; this.array[newKey] = null; } CSE 373 SP 18 - KASEY CHAMPION 31

  32. First Hash Function: % table size 0 1 2 3 4 5 6 7 8 9 indices foo biz bar bop elements poo put(0, foo ); put(5, bar ); put(11, biz ) put(18, bop ); put(20, poo ); 0 % 10 = 0 5 % 10 = 5 11 % 10 = 1 18 % 10 = 8 20 % 10 = 0 Collision! CSE 373 SP 18 - KASEY CHAMPION 32

  33. Today Wrap up AVL Trees Problem: Can we make get(k) operation on dictionaries fast: O(1) Motivation Hashing - Separate Chaining CSE 373 AU 18 SHRI MARE 33

  34. Hashing: Separate Chaining CSE 373 AU 18 SHRI MARE 34

Related


No related presentations.

More Related Content