DOC PREVIEW
Duke CPS 100E - Balanced Binary Search Trees

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

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

Unformatted text preview:

Balanced Binary Search TreesSlide 2AVL TreesSlide 4Slide 5Slide 6Slide 7AVL TreeSlide 9Slide 10Slide 11Slide 12CompSci 100E41.1Balanced Binary Search TreesPathological BSTInsert nodes from ordered list : O(___) ?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.2Balanc ed 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 “rotation(s)”Rotations restore balance to the treeCompSci 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 insert has caused loss of balance at k2 * (Also used as part of double rotation operations) * @return root of adjusted tree */TNode rotateWithLeftChild(TNode k2){ TNode k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; }CompSci 100E41.5AVL TreesSingle RotationCompSci 100E41.6AVL Treesk2k1k1k2CAABB CSingle RotationAlso: mirror imagebeforeafterCompSci 100E41.7AVL TreesSingle RotationMirror image case/** Used if insert has caused loss of balance at k2 * (Also used as part of double rotation operations) * @return root of adjusted tree */TNode rotateWithRightChild(TNode k2){ TNode k1 = k2.right; k2.right = k1.left; k1.left = k2; return k1; }CompSci 100E41.8AVL 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) * @return root of adjusted tree */TNode doubleRotateWithLeftChild(TNode k3) { k3.left = rotateWithRightChild(k3.left); return rotateWithLeftChild(k3);}CompSci 100E41.9AVL TreeDouble RotationCompSci 100E41.10AVL Treesk3k1k1k3DAABBCDouble RotationAlso: mirror imagebeforeafterk2k2CDCompSci 100E41.11AVL TreeDouble RotationAn insertion into the right subtree of the left child of tree Adapted from Weiss, p 571/** Used after insertion into right subtree, k2, * of right child, k1, of k3 (if it has caused * loss of balance) * @return root of adjusted tree */TNode doubleRotateWithRightChild(TNode k3) { k3.right = rotateWithLeftChild(k3.right); return rotateWithRightChild(k3); }CompSci 100E41.12AVL TreesDeletions can also cause imbalanceUse similar rotations to restore balanceBig Oh?That was the “big picture”How can we insure performance?Think about some of the implementation


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?