Skip to content
Hallway
0:00 / 0:00

#avltree#binarysearchtree#sorting

Lecture 6: AVL Trees, AVL Sort

MIT OpenCourseWare

6.5M subscribers • 37 videos on Hallway • University channel

YouTube
  • Recommended by 2 people: 1 in engineering communities and 1 curated list.
  • Presented by Erik Demaine, MIT

Intermediate. Assumes working knowledge.

705K views13 years ago2 recommendations

Computer scienceData structuresAlgorithms

Erik Demaine explains the mechanics of AVL trees, including rotations and balancing, and how they are used for sorting.

MIT 6.006 Introduction to Algorithms, Fall 2011 View the complete course: ocw.mit.edu/6-006F11 Instructor: Erik Demaine License: Creative Commons BY-NC-SA More information at ocw.mit.edu/terms More courses at ocw.mit.edu

Why it's here

2 people recommend this

What people say. Recommended as a standard resource for understanding AVL tree balancing and insertion procedures.

Moments people linked to

u/flebronin r/compsci • Recommends

On “[CS1] Understanding Rebalancing AVL Trees”

The balancing factor of a node is not something you chose. It is just the difference between the heights of your left and right subtree. For more information on AVL trees, you can look at Introduction to Algorithms, MIT Press. You can look at insertion procedures in https://www.cs.usfca.edu/~galles/visualization/AVLtree.html , and a video about AVL trees at link to this video
5View on Reddit

Coding Interview Universitycurated list on GitHubRecommends

Under “Additional Learning”

MIT AVL Trees / AVL Sort (video)
View the list

u/Seneferuin r/compsci • Mentions

On “Could anyone explain how this big-Theta solution is derived?”

N\_h > 2 N\_{h-2} > 2 2 N\_{h-4} > ... > 2\^{h /2} N\_0 You start with N\_h which is larger than 2 N\_{h-2}. Note that you have -2, not -1. Therefore, it takes only h/2 steps to get from h to 0. EDIT: Source: link to this video
3View on Reddit