Содержание
- 2. 12/26/03 AVL Trees - Lecture 8 Readings Reading Section 4.4,
- 3. 12/26/03 AVL Trees - Lecture 8 Binary Search Tree - Best Time All BST operations are
- 4. 12/26/03 AVL Trees - Lecture 8 Binary Search Tree - Worst Time Worst case running time
- 5. 12/26/03 AVL Trees - Lecture 8 Balanced and unbalanced BST 4 2 5 1 3 1
- 6. 12/26/03 AVL Trees - Lecture 8 Approaches to balancing trees Don't balance May end up with
- 7. 12/26/03 AVL Trees - Lecture 8 Balancing Binary Search Trees Many algorithms exist for keeping binary
- 8. 12/26/03 AVL Trees - Lecture 8 Perfect Balance Want a complete tree after every operation tree
- 9. 12/26/03 AVL Trees - Lecture 8 AVL - Good but not Perfect Balance AVL trees are
- 10. 12/26/03 AVL Trees - Lecture 8 Height of an AVL Tree N(h) = minimum number of
- 11. 12/26/03 AVL Trees - Lecture 8 Height of an AVL Tree N(h) > φh (φ ≈
- 12. 12/26/03 AVL Trees - Lecture 8 Node Heights 1 0 0 2 0 6 4 9
- 13. 12/26/03 AVL Trees - Lecture 8 Node Heights after Insert 7 2 1 0 3 0
- 14. 12/26/03 AVL Trees - Lecture 8 Insert and Rotation in AVL Trees Insert operation may cause
- 15. 12/26/03 AVL Trees - Lecture 8 Single Rotation in an AVL Tree 2 1 0 2
- 16. 12/26/03 AVL Trees - Lecture 8 Let the node that needs rebalancing be α. There are
- 17. 12/26/03 AVL Trees - Lecture 8 j k X Y Z Consider a valid AVL subtree
- 18. 12/26/03 AVL Trees - Lecture 8 j k X Y Z Inserting into X destroys the
- 19. 12/26/03 AVL Trees - Lecture 8 j k X Y Z Do a “right rotation” AVL
- 20. 12/26/03 AVL Trees - Lecture 8 j k X Y Z Do a “right rotation” Single
- 21. 12/26/03 AVL Trees - Lecture 8 j k X Y Z “Right rotation” done! (“Left rotation”
- 22. 12/26/03 AVL Trees - Lecture 8 j k X Y Z AVL Insertion: Inside Case Consider
- 23. 12/26/03 AVL Trees - Lecture 8 Inserting into Y destroys the AVL property at node j
- 24. 12/26/03 AVL Trees - Lecture 8 j k X Y Z “Right rotation” does not restore
- 25. 12/26/03 AVL Trees - Lecture 8 Consider the structure of subtree Y… j k X Y
- 26. 12/26/03 AVL Trees - Lecture 8 j k X V Z W i Y = node
- 27. 12/26/03 AVL Trees - Lecture 8 j k X V Z W i AVL Insertion: Inside
- 28. 12/26/03 AVL Trees - Lecture 8 j k X V Z W i Double rotation :
- 29. 12/26/03 AVL Trees - Lecture 8 j k X V Z W i Double rotation :
- 30. 12/26/03 AVL Trees - Lecture 8 j k X V Z W i Double rotation :
- 31. 12/26/03 AVL Trees - Lecture 8 Implementation balance (1,0,-1) key right left No need to keep
- 32. 12/26/03 AVL Trees - Lecture 8 Single Rotation RotateFromRight(n : reference node pointer) { p :
- 33. 12/26/03 AVL Trees - Lecture 8 Double Rotation Implement Double Rotation in two lines. DoubleRotateFromRight(n :
- 34. 12/26/03 AVL Trees - Lecture 8 Insertion in AVL Trees Insert at the leaf (as for
- 35. 12/26/03 AVL Trees - Lecture 8 Insert in BST Insert(T : reference tree pointer, x :
- 36. 12/26/03 AVL Trees - Lecture 8 Insert in AVL trees Insert(T : reference tree pointer, x
- 37. 12/26/03 AVL Trees - Lecture 8 Example of Insertions in an AVL Tree 1 0 2
- 38. 12/26/03 AVL Trees - Lecture 8 Example of Insertions in an AVL Tree 1 0 2
- 39. 12/26/03 AVL Trees - Lecture 8 Single rotation (outside case) 2 0 3 20 10 30
- 40. 12/26/03 AVL Trees - Lecture 8 Double rotation (inside case) 3 0 3 20 10 30
- 41. 12/26/03 AVL Trees - Lecture 8 AVL Tree Deletion Similar but more complex than insertion Rotations
- 42. 12/26/03 AVL Trees - Lecture 8 Arguments for AVL trees: Search is O(log N) since AVL
- 44. Скачать презентацию