Basis Lab

Keeping Things in Order

Keeping It Balanced

Last timeWhen a Tree Degenerates Into a List

A tree can be kept shallow by one small move: when a node leans too far, lift its heavier side into its place. Checking and repairing on the way back up costs almost nothing.

The condition is that no node leans by more than one. This lesson is the move

that restores it, and the move is smaller than people expect.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the planThe contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

The rest of this course

  1. 01Halving the Search
  2. 02A Sorted List You Can Changeopening only
  3. 03When a Tree Degenerates Into a Listopening only
  4. 04Keeping It Balancedyou are here
  5. 05Asking for Everything Betweenopening only
  6. 06Wide Trees and the Diskopening only
  7. 07Always Knowing the Smallestopening only
  8. 08Putting It in Order in the First Placeopening only

Read alongside