DOC PREVIEW
Duke CPS 100E - Balanced Binary Search Trees

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 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 10 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 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Balanced Binary Search TreesSlide 2AVL TreesSlide 4Slide 5Slide 6AVL TreeSlide 8Slide 9Slide 10CompSci 100E41.1Balanced Binary Search TreesPathological BSTInsert nodes from ordered list Search: O(___) ?The Balanced TreeBinary Tree is balanced if height of left and right subtree differ by no more than one, recursively for all nodes. (Height of empty tree is -1) ExamplesCompSci 100E41.2Balanced Binary Search TreesKeeping BSTrees Balanced Keeps find, insert, delete O(log(N)) worst case. Pay small extra amount at each insertion to keep it balanced Several Well-known Systems Exist for ThisAVL TreesRed-Black Trees. . .Will look at AVL TreesCompSci 100E41.3AVL TreesAVL TreesAdelson-Velskii and Landis Discovered ways to keep BSTrees BalancedInsertionsInsert into BST in normal wayIf tree no longer balanced, perform a “rotation”Rotations leave the tree balanced againCompSci 100E41.4AVL TreesSingle RotationAn insertion into the left subtree of the left child of tree Adapted from Weiss, pp 567-568// Used if it has caused loss of balance) // (Also used as part of double rotation operations) Tnode rotateWithLeftChild(TNode k2)//post: returns root of adjusted tree { TNode k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; }CompSci 100E41.5AVL Treesk2k1k1k2CAABB CSingle RotationAlso: mirror imagebeforeafterCompSci 100E41.6AVL TreesSingle RotationMirror image caseTNode rotateWithRightChild(TNode k2)//post: returns root of adjusted tree { TNode k1 = k2.right; k2.right = k1.left; k1.left = k2; return k1; }CompSci 100E41.7AVL TreeDouble RotationAn insertion into the right subtree of the left child of tree Adapted from Weiss, p 57// Used after insertion into right subtree, k2,// of left child, k1, of k3 (if it has caused// loss of balance) TNode doubleRotateWithLeftChild(TNode k3) //post: returns root of adjusted tree { k3.left = rotateWithRightChild(k3.left); return rotateWithLeftChild(k3); }CompSci 100E41.8AVL Treesk3k1k1k3DAABBCDouble RotationAlso: mirror imagebeforeafterk2k2CDCompSci 100E41.9AVL TreeDouble RotationAn insertion into the right subtree of the left child of tree Adapted from Weiss, p 571// Mirror ImageTNode doubleRotateWithRightChild(TNode k3) //post: returns root of adjusted tree { k3.right = rotateWithLeftChild(k3.right); return rotateWithRightChild(k3); }CompSci 100E41.10AVL TreesDeletions can also cause imbalanceUse similar rotations to restore balanceBig


View Full Document

Duke CPS 100E - Balanced Binary Search Trees

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Balanced Binary Search Trees
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 Balanced Binary Search Trees 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 Balanced Binary Search Trees 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?