Self-Balancing Tree

noun

say it: “SELF BAL-un-sing TREE” /sɛlf ˈbælənsɪŋ triː/

A binary search tree that fixes its own shape after every change, with small rotations, so it stays short whatever order data arrives in.

What is a self-balancing tree?

A self-balancing tree is a binary search tree that checks its shape after every add and remove and fixes it with small swaps called rotations. AVL trees and red-black trees are the best-known kinds, and the sorted maps in C# and Java are built on them.

In a sentence

  • “C#'s SortedDictionary is a self-balancing tree, so sorted data can't turn it into a slow line.”

Level: Freelancer · More Data Structures terms at this level

Updated