Balanced trees

AVL and red-black trees rotate nodes so the height stays about log n. A skewed tree is just a list drawn vertically.

A balanced tree keeps its height small, about log n for n nodes. AVL trees and red-black trees do this by rotating nodes after an insert or a delete would make one side too tall. JavaScript engines and databases use these shapes. You do not implement a rotation this month.

You do need to notice when a tree has degenerated into a list. If every insert went to the right, the drawing is a linked list stood on end, and every search is O(n). The left-and-right rule can still be true. It is just no longer saving work.

Rotation here means a tree move: a node and its child change places so a different node becomes the parent, and the search rule still holds. It is not the array rotation from the first week. Same English word, different operation. When someone says a structure is balanced, ask what it does on insert to keep the height honest.