ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo
CS216                                                                                         Fall 2001




                                         AVL Trees Example



        Insert 3                    Insert 2                   Insert 1 (non-AVL)              AVL

            3                        3                              3                             2


                                2                              2         Single          1                3
                                                                         rotation
                                                   1


        Insert 4                    Insert 5 (non-AVL)                                         AVL

                                                                                               2
                2                              2


                                                                        Single          1                4
                    3                    1             3
    1                                                                   rotation

                                                                                              3                       5
                            4                                   4

                                                                        5


        Insert 6 (non-AVL)                                 AVL                               Insert 7 (non-AVL)

                                                                4                                  4
        2

                            Single                     2            5                    2                5
1               4           rotation

                                               1           3                6       1         3                   6
    3                   5

                                                                                                                          7
                                6




        9/27/01                                                                                    Page 1 of 4
CS216                                                                                                                       Fall 2001



                               AVL                                                Insert 16                                                     Insert 15 (non-AVL)

                                                                                                                                                  4
                               4                                                    4
Single
rotation                                                                                                                            2                       6
                       2                    6                             2                     6

                                                                                                                           1                3          5                7
           1               3           5                  7         1         3         5                7


                                                                                                                   16                                                            16


                                                                                                                                                                   15



           Step 1: Rotate child and grandchild                                     Step 2: Rotate node and new child (AVL)

                                       4                                                                      4


Double                     2                         6                                               2                         6
rotation

                   1           3                5               7                           1            3             5                    15


                                                                    15                                                         7                  16


                                                                         16

 Insert 14 (non-AVL)                                           Step 1: Rotate child and                           Step 2: Rotate node and
                                                                       grandchild                                        new child (AVL)

                                                                                                                                            4
                       4                                                      4
                                                    Double
                                                    rotation                                                                    2                       7
       2                           6                                 2                  6

                                                                                                                   1                3             6              15
1              3           5                    15             1         3         5                 7

                                                                                                                                                                            16
                               7                         16                                              15                             5                   14


                                           14                                                   14                16

                           9/27/01                                                                                                                    Page 2 of 4
CS216                                                                     Fall 2001


         AVL Tree                               No longer AVL, must rebalance




                                Insert a node




     h                  h +1                             h             h +2



         Two ways to expand subtree of height h+2:




 h                                                   h



                   h           h +1                             h +1          h
                       h +2
                                                                       h +2
Apply a Single Rotation                              Apply a Double Rotation




                        Note: the symmetrical case is handled
                        identically (i.e. mirror image)




         9/27/01                                                                  Page 3 of 4
CS216                                                                                       Fall 2001


    Single Rotation:

               B                                                    D

                                      Single
                                      rotation
                          D                                     B

A
                                                                            E

h                                                                           h +1
               C                E                           A       C

               h               h +1                         h       h

                       h +2
    Double Rotation:

                   B
                                                                                   D



                          F
                                                                        B                          F
    A                                            Double
                                                 rotation
                   D
    h

                                  G                             A            C           E                  G

                                 h                              h            h           h -1           h
        C                 E                                                            OR
                                                                            h-1            h
        h               h -1                                                           OR
                                                                            h              h
                OR
        h-1               h
                OR
        h                 h
              h +1


                   h +2
    9/27/01                                                                                  Page 4 of 4

More Related Content

Viewers also liked (12)

new leave behind card copy
new leave behind card copynew leave behind card copy
new leave behind card copy
Zerish Watson
?
White paper - Fattori di successo nella implementazione dei sistemi ERP
White paper - Fattori di successo nella implementazione dei sistemi ERPWhite paper - Fattori di successo nella implementazione dei sistemi ERP
White paper - Fattori di successo nella implementazione dei sistemi ERP
Sogesi
?
Brochure booklet.compressed
Brochure booklet.compressedBrochure booklet.compressed
Brochure booklet.compressed
SparkDigital
?
Psa 130431
Psa 130431Psa 130431
Psa 130431
Pintu Sheel
?
Viva questions ds th c++
Viva questions ds th c++Viva questions ds th c++
Viva questions ds th c++
mrecedu
?
Hilton Head massage Therapy
Hilton Head massage TherapyHilton Head massage Therapy
Hilton Head massage Therapy
jamhassan00
?
Its undergraduate-16685-4106100069-presentation
Its undergraduate-16685-4106100069-presentationIts undergraduate-16685-4106100069-presentation
Its undergraduate-16685-4106100069-presentation
Yayuk Setiyowati
?
Updt Resume October 2015
Updt Resume October 2015Updt Resume October 2015
Updt Resume October 2015
Evening Star Barron
?
Tarea 3 TICTarea 3 TIC
Tarea 3 TIC
legendario8896
?
Module 1 lecture_1_final
Module 1 lecture_1_finalModule 1 lecture_1_final
Module 1 lecture_1_final
amit sunduja
?
Creative Australia
Creative AustraliaCreative Australia
Creative Australia
Daniel Dufourt
?
new leave behind card copy
new leave behind card copynew leave behind card copy
new leave behind card copy
Zerish Watson
?
White paper - Fattori di successo nella implementazione dei sistemi ERP
White paper - Fattori di successo nella implementazione dei sistemi ERPWhite paper - Fattori di successo nella implementazione dei sistemi ERP
White paper - Fattori di successo nella implementazione dei sistemi ERP
Sogesi
?
Brochure booklet.compressed
Brochure booklet.compressedBrochure booklet.compressed
Brochure booklet.compressed
SparkDigital
?
Viva questions ds th c++
Viva questions ds th c++Viva questions ds th c++
Viva questions ds th c++
mrecedu
?
Hilton Head massage Therapy
Hilton Head massage TherapyHilton Head massage Therapy
Hilton Head massage Therapy
jamhassan00
?
Its undergraduate-16685-4106100069-presentation
Its undergraduate-16685-4106100069-presentationIts undergraduate-16685-4106100069-presentation
Its undergraduate-16685-4106100069-presentation
Yayuk Setiyowati
?
Tarea 3 TICTarea 3 TIC
Tarea 3 TIC
legendario8896
?
Module 1 lecture_1_final
Module 1 lecture_1_finalModule 1 lecture_1_final
Module 1 lecture_1_final
amit sunduja
?

More from mrecedu (20)

Brochure final
Brochure finalBrochure final
Brochure final
mrecedu
?
Unit i
Unit iUnit i
Unit i
mrecedu
?
Filters unit iii
Filters unit iiiFilters unit iii
Filters unit iii
mrecedu
?
Attenuator unit iv
Attenuator unit ivAttenuator unit iv
Attenuator unit iv
mrecedu
?
Two port networks unit ii
Two port networks unit iiTwo port networks unit ii
Two port networks unit ii
mrecedu
?
Unit 8
Unit 8Unit 8
Unit 8
mrecedu
?
Unit4 (2)
Unit4 (2)Unit4 (2)
Unit4 (2)
mrecedu
?
Unit5
Unit5Unit5
Unit5
mrecedu
?
Unit4
Unit4Unit4
Unit4
mrecedu
?
Unit5 (2)
Unit5 (2)Unit5 (2)
Unit5 (2)
mrecedu
?
Unit6 jwfiles
Unit6 jwfilesUnit6 jwfiles
Unit6 jwfiles
mrecedu
?
Unit3 jwfiles
Unit3 jwfilesUnit3 jwfiles
Unit3 jwfiles
mrecedu
?
Unit2 jwfiles
Unit2 jwfilesUnit2 jwfiles
Unit2 jwfiles
mrecedu
?
Unit1 jwfiles
Unit1 jwfilesUnit1 jwfiles
Unit1 jwfiles
mrecedu
?
Unit7 jwfiles
Unit7 jwfilesUnit7 jwfiles
Unit7 jwfiles
mrecedu
?
M1 unit vi-jntuworld
M1 unit vi-jntuworldM1 unit vi-jntuworld
M1 unit vi-jntuworld
mrecedu
?
M1 unit v-jntuworld
M1 unit v-jntuworldM1 unit v-jntuworld
M1 unit v-jntuworld
mrecedu
?
M1 unit iv-jntuworld
M1 unit iv-jntuworldM1 unit iv-jntuworld
M1 unit iv-jntuworld
mrecedu
?
M1 unit iii-jntuworld
M1 unit iii-jntuworldM1 unit iii-jntuworld
M1 unit iii-jntuworld
mrecedu
?
M1 unit ii-jntuworld
M1 unit ii-jntuworldM1 unit ii-jntuworld
M1 unit ii-jntuworld
mrecedu
?
Brochure final
Brochure finalBrochure final
Brochure final
mrecedu
?
Filters unit iii
Filters unit iiiFilters unit iii
Filters unit iii
mrecedu
?
Attenuator unit iv
Attenuator unit ivAttenuator unit iv
Attenuator unit iv
mrecedu
?
Two port networks unit ii
Two port networks unit iiTwo port networks unit ii
Two port networks unit ii
mrecedu
?
Unit6 jwfiles
Unit6 jwfilesUnit6 jwfiles
Unit6 jwfiles
mrecedu
?
Unit3 jwfiles
Unit3 jwfilesUnit3 jwfiles
Unit3 jwfiles
mrecedu
?
Unit2 jwfiles
Unit2 jwfilesUnit2 jwfiles
Unit2 jwfiles
mrecedu
?
Unit1 jwfiles
Unit1 jwfilesUnit1 jwfiles
Unit1 jwfiles
mrecedu
?
Unit7 jwfiles
Unit7 jwfilesUnit7 jwfiles
Unit7 jwfiles
mrecedu
?
M1 unit vi-jntuworld
M1 unit vi-jntuworldM1 unit vi-jntuworld
M1 unit vi-jntuworld
mrecedu
?
M1 unit v-jntuworld
M1 unit v-jntuworldM1 unit v-jntuworld
M1 unit v-jntuworld
mrecedu
?
M1 unit iv-jntuworld
M1 unit iv-jntuworldM1 unit iv-jntuworld
M1 unit iv-jntuworld
mrecedu
?
M1 unit iii-jntuworld
M1 unit iii-jntuworldM1 unit iii-jntuworld
M1 unit iii-jntuworld
mrecedu
?
M1 unit ii-jntuworld
M1 unit ii-jntuworldM1 unit ii-jntuworld
M1 unit ii-jntuworld
mrecedu
?

Recently uploaded (20)

What is Blockchain and How Can Blockchain Consulting Help Businesses.pdf
What is Blockchain and How Can Blockchain Consulting Help Businesses.pdfWhat is Blockchain and How Can Blockchain Consulting Help Businesses.pdf
What is Blockchain and How Can Blockchain Consulting Help Businesses.pdf
Yodaplus Technologies Private Limited
?
5 Must-Use AI Tools to Supercharge Your Productivity
5 Must-Use AI Tools to Supercharge Your Productivity5 Must-Use AI Tools to Supercharge Your Productivity
5 Must-Use AI Tools to Supercharge Your Productivity
cryptouniversityoffi
?
Combining Lexical and Semantic Search with Milvus 2.5
Combining Lexical and Semantic Search with Milvus 2.5Combining Lexical and Semantic Search with Milvus 2.5
Combining Lexical and Semantic Search with Milvus 2.5
Zilliz
?
DealBook of Ukraine: 2025 edition | AVentures Capital
DealBook of Ukraine: 2025 edition | AVentures CapitalDealBook of Ukraine: 2025 edition | AVentures Capital
DealBook of Ukraine: 2025 edition | AVentures Capital
Yevgen Sysoyev
?
SB7 Mobile Ltd: Simplified & Secure Services
SB7 Mobile Ltd: Simplified & Secure ServicesSB7 Mobile Ltd: Simplified & Secure Services
SB7 Mobile Ltd: Simplified & Secure Services
Reuben Jasper
?
Bedrock Data Automation (Preview): Simplifying Unstructured Data Processing
Bedrock Data Automation (Preview): Simplifying Unstructured Data ProcessingBedrock Data Automation (Preview): Simplifying Unstructured Data Processing
Bedrock Data Automation (Preview): Simplifying Unstructured Data Processing
Zilliz
?
The Constructor's Digital Transformation Playbook: Reducing Risk With Technology
The Constructor's Digital Transformation Playbook: Reducing Risk With TechnologyThe Constructor's Digital Transformation Playbook: Reducing Risk With Technology
The Constructor's Digital Transformation Playbook: Reducing Risk With Technology
Aggregage
?
Mastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use Cases
Mastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use CasesMastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use Cases
Mastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use Cases
Sanjay Willie
?
GDG Cloud Southlake #40: Brandon Stokes: How to Build a Great Product
GDG Cloud Southlake #40: Brandon Stokes: How to Build a Great ProductGDG Cloud Southlake #40: Brandon Stokes: How to Build a Great Product
GDG Cloud Southlake #40: Brandon Stokes: How to Build a Great Product
James Anderson
?
Not a Kubernetes fan? The state of PaaS in 2025
Not a Kubernetes fan? The state of PaaS in 2025Not a Kubernetes fan? The state of PaaS in 2025
Not a Kubernetes fan? The state of PaaS in 2025
Anthony Dahanne
?
What is FinTech A Complete Guide to Financial Technology.pdf
What is FinTech A Complete Guide to Financial Technology.pdfWhat is FinTech A Complete Guide to Financial Technology.pdf
What is FinTech A Complete Guide to Financial Technology.pdf
Yodaplus Technologies Private Limited
?
Caching for Performance Masterclass: Caching at Scale
Caching for Performance Masterclass: Caching at ScaleCaching for Performance Masterclass: Caching at Scale
Caching for Performance Masterclass: Caching at Scale
ScyllaDB
?
Webinar: LF Energy GEISA: Addressing edge interoperability at the meter
Webinar: LF Energy GEISA: Addressing edge interoperability at the meterWebinar: LF Energy GEISA: Addressing edge interoperability at the meter
Webinar: LF Energy GEISA: Addressing edge interoperability at the meter
DanBrown980551
?
Caching for Performance Masterclass: The In-Memory Datastore
Caching for Performance Masterclass: The In-Memory DatastoreCaching for Performance Masterclass: The In-Memory Datastore
Caching for Performance Masterclass: The In-Memory Datastore
ScyllaDB
?
Benchmark Testing Demystified: Your Roadmap to Peak Performance
Benchmark Testing Demystified: Your Roadmap to Peak PerformanceBenchmark Testing Demystified: Your Roadmap to Peak Performance
Benchmark Testing Demystified: Your Roadmap to Peak Performance
Shubham Joshi
?
THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIA
THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIATHE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIA
THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIA
Srivaanchi Nathan
?
SECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdf
SECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdfSECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdf
SECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdf
spub1985
?
Supercharge Your Career with UiPath Certifications
Supercharge Your Career with UiPath CertificationsSupercharge Your Career with UiPath Certifications
Supercharge Your Career with UiPath Certifications
DianaGray10
?
Artificial Intelligence Quick Research Guide by Arthur Morgan
Artificial Intelligence Quick Research Guide by Arthur MorganArtificial Intelligence Quick Research Guide by Arthur Morgan
Artificial Intelligence Quick Research Guide by Arthur Morgan
Arthur Morgan
?
ISOIEC 42001 AI Management System ºÝºÝߣs
ISOIEC 42001 AI Management System ºÝºÝߣsISOIEC 42001 AI Management System ºÝºÝߣs
ISOIEC 42001 AI Management System ºÝºÝߣs
GilangRamadhan884333
?
5 Must-Use AI Tools to Supercharge Your Productivity
5 Must-Use AI Tools to Supercharge Your Productivity5 Must-Use AI Tools to Supercharge Your Productivity
5 Must-Use AI Tools to Supercharge Your Productivity
cryptouniversityoffi
?
Combining Lexical and Semantic Search with Milvus 2.5
Combining Lexical and Semantic Search with Milvus 2.5Combining Lexical and Semantic Search with Milvus 2.5
Combining Lexical and Semantic Search with Milvus 2.5
Zilliz
?
DealBook of Ukraine: 2025 edition | AVentures Capital
DealBook of Ukraine: 2025 edition | AVentures CapitalDealBook of Ukraine: 2025 edition | AVentures Capital
DealBook of Ukraine: 2025 edition | AVentures Capital
Yevgen Sysoyev
?
SB7 Mobile Ltd: Simplified & Secure Services
SB7 Mobile Ltd: Simplified & Secure ServicesSB7 Mobile Ltd: Simplified & Secure Services
SB7 Mobile Ltd: Simplified & Secure Services
Reuben Jasper
?
Bedrock Data Automation (Preview): Simplifying Unstructured Data Processing
Bedrock Data Automation (Preview): Simplifying Unstructured Data ProcessingBedrock Data Automation (Preview): Simplifying Unstructured Data Processing
Bedrock Data Automation (Preview): Simplifying Unstructured Data Processing
Zilliz
?
The Constructor's Digital Transformation Playbook: Reducing Risk With Technology
The Constructor's Digital Transformation Playbook: Reducing Risk With TechnologyThe Constructor's Digital Transformation Playbook: Reducing Risk With Technology
The Constructor's Digital Transformation Playbook: Reducing Risk With Technology
Aggregage
?
Mastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use Cases
Mastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use CasesMastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use Cases
Mastering ChatGPT & LLMs for Practical Applications: Tips, Tricks, and Use Cases
Sanjay Willie
?
GDG Cloud Southlake #40: Brandon Stokes: How to Build a Great Product
GDG Cloud Southlake #40: Brandon Stokes: How to Build a Great ProductGDG Cloud Southlake #40: Brandon Stokes: How to Build a Great Product
GDG Cloud Southlake #40: Brandon Stokes: How to Build a Great Product
James Anderson
?
Not a Kubernetes fan? The state of PaaS in 2025
Not a Kubernetes fan? The state of PaaS in 2025Not a Kubernetes fan? The state of PaaS in 2025
Not a Kubernetes fan? The state of PaaS in 2025
Anthony Dahanne
?
Caching for Performance Masterclass: Caching at Scale
Caching for Performance Masterclass: Caching at ScaleCaching for Performance Masterclass: Caching at Scale
Caching for Performance Masterclass: Caching at Scale
ScyllaDB
?
Webinar: LF Energy GEISA: Addressing edge interoperability at the meter
Webinar: LF Energy GEISA: Addressing edge interoperability at the meterWebinar: LF Energy GEISA: Addressing edge interoperability at the meter
Webinar: LF Energy GEISA: Addressing edge interoperability at the meter
DanBrown980551
?
Caching for Performance Masterclass: The In-Memory Datastore
Caching for Performance Masterclass: The In-Memory DatastoreCaching for Performance Masterclass: The In-Memory Datastore
Caching for Performance Masterclass: The In-Memory Datastore
ScyllaDB
?
Benchmark Testing Demystified: Your Roadmap to Peak Performance
Benchmark Testing Demystified: Your Roadmap to Peak PerformanceBenchmark Testing Demystified: Your Roadmap to Peak Performance
Benchmark Testing Demystified: Your Roadmap to Peak Performance
Shubham Joshi
?
THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIA
THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIATHE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIA
THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIA
Srivaanchi Nathan
?
SECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdf
SECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdfSECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdf
SECURE BLOCKCHAIN FOR ADMISSION PROCESSING IN EDUCATIONAL INSTITUTIONS.pdf
spub1985
?
Supercharge Your Career with UiPath Certifications
Supercharge Your Career with UiPath CertificationsSupercharge Your Career with UiPath Certifications
Supercharge Your Career with UiPath Certifications
DianaGray10
?
Artificial Intelligence Quick Research Guide by Arthur Morgan
Artificial Intelligence Quick Research Guide by Arthur MorganArtificial Intelligence Quick Research Guide by Arthur Morgan
Artificial Intelligence Quick Research Guide by Arthur Morgan
Arthur Morgan
?
ISOIEC 42001 AI Management System ºÝºÝߣs
ISOIEC 42001 AI Management System ºÝºÝߣsISOIEC 42001 AI Management System ºÝºÝߣs
ISOIEC 42001 AI Management System ºÝºÝߣs
GilangRamadhan884333
?

Avl handout

  • 1. CS216 Fall 2001 AVL Trees Example Insert 3 Insert 2 Insert 1 (non-AVL) AVL 3 3 3 2 2 2 Single 1 3 rotation 1 Insert 4 Insert 5 (non-AVL) AVL 2 2 2 Single 1 4 3 1 3 1 rotation 3 5 4 4 5 Insert 6 (non-AVL) AVL Insert 7 (non-AVL) 4 4 2 Single 2 5 2 5 1 4 rotation 1 3 6 1 3 6 3 5 7 6 9/27/01 Page 1 of 4
  • 2. CS216 Fall 2001 AVL Insert 16 Insert 15 (non-AVL) 4 4 4 Single rotation 2 6 2 6 2 6 1 3 5 7 1 3 5 7 1 3 5 7 16 16 15 Step 1: Rotate child and grandchild Step 2: Rotate node and new child (AVL) 4 4 Double 2 6 2 6 rotation 1 3 5 7 1 3 5 15 15 7 16 16 Insert 14 (non-AVL) Step 1: Rotate child and Step 2: Rotate node and grandchild new child (AVL) 4 4 4 Double rotation 2 7 2 6 2 6 1 3 6 15 1 3 5 15 1 3 5 7 16 7 16 15 5 14 14 14 16 9/27/01 Page 2 of 4
  • 3. CS216 Fall 2001 AVL Tree No longer AVL, must rebalance Insert a node h h +1 h h +2 Two ways to expand subtree of height h+2: h h h h +1 h +1 h h +2 h +2 Apply a Single Rotation Apply a Double Rotation Note: the symmetrical case is handled identically (i.e. mirror image) 9/27/01 Page 3 of 4
  • 4. CS216 Fall 2001 Single Rotation: B D Single rotation D B A E h h +1 C E A C h h +1 h h h +2 Double Rotation: B D F B F A Double rotation D h G A C E G h h h h -1 h C E OR h-1 h h h -1 OR h h OR h-1 h OR h h h +1 h +2 9/27/01 Page 4 of 4