DOC PREVIEW
GSU CSC 2320 - CSCI2320 Chapter 19 part2

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

AVL TreesBinary Search TreeAVL Tree (Adelson-Velskii & Landis)Adding/deleteing node from AVL TreeSingle rotation (When the problem happens in “A”)Single rotation Single rotation (When the problem happens in “C”)Single RotationSingle rotationSlide 9Slide 10Slide 11Single Rotation Doesn’t Work in Some CasesSlide 13Slide 14Slide 15Double RotationTrySlide 181AVL Trees53 71 2 82Binary Search TreeBinary search tree, using simple insert and delete proceduresthe tree is nearly balance add - fast O(log n)delete a target - fast O(log n)search - fast O(log n)the tree is highly unbalance, it becomes a singly linked list (the worst case)add, delete and search - slow O(n) effectively using sequential search to find a location3AVL Tree (Adelson-Velskii & Landis)AVL Tree are BST with an additional balance condition to ensure the depth of the tree is O(log2N)Balance Condition: for any node in the tree, the height (the length of the path form the node to the deepest leaf) of the left and right subtrees can differ by at most 1.Must ensure that after insertion and deletion of a node, the balance condition is preserved4Adding/deleteing node from AVL Tree* Add a node connected to some node?* Delete some node?After an insertion, the nodes on the path from the insertionpoint to the root can have their balances altered.Rotation restores local balance5Single rotation (When the problem happens in “A”)k2k1ABCk1k2AB C6Single rotation Single rotation (When the problem happens in “C”)k2k1ABCk1k2A BC7Single Rotation354 76 92183547692188Single rotationPerform Single Rotation on K2Node *k1 = K2 -> left; //identify k1K2 -> left = K1 -> RightK1 -> right = K2K2 = K1k2k1ABCk1k2AB C9Single rotationExample: in BST, if we insert 1, 2, 3, 4, 5, 6 in order, we get a BST tree like:10Single rotationIn AVL tree, it would be:11Single rotationIn AVL tree, it would be:12Single Rotation Doesn’t Work in Some CasesHowever, when the problem happens in “B”…13Single Rotation Doesn’t Work in Some Cases k2k1ABCk2k1BAC14Single Rotation Doesn’t Work in Some Cases k2k1ABCk2k1ACB15Single Rotation Doesn’t Work in Some Cases354 86 921735486921716Double RotationyDxAzB CyDxAzB C354 86 921735468921717TryInsert 1, 2, 3, 4, 5, 3.518Double RotationPerform Double rotation on X=Perform Single Rotation on Y + Perform Single Rotation on X yDxAzB


View Full Document

GSU CSC 2320 - CSCI2320 Chapter 19 part2

Download CSCI2320 Chapter 19 part2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CSCI2320 Chapter 19 part2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CSCI2320 Chapter 19 part2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?