What is a tree? And what is a red-black tree?什么是树？什么是红黑树？

01The idea先有一个画面

A tree is that guessing game. Each node can have two children: left (smaller) and right (bigger). Finding a thing is: go left or go right, again and again.树就是这个猜数游戏：每个节点最多两个孩子——左孩子更小、右孩子更大。查找就是反复地“往左还是往右”。

02Why a line is too slow为什么“链”太慢

A linked list of 8 items needs up to 8 steps to find one — O(n). A balanced tree of 8 items needs about 3 — O(log n). Each time the data doubles, the tree needs one more step; the list needs double.8 个元素的链表最多要走 8 步，O(n)；8 个元素的平衡树大约 3 步，O(log n)。数据翻一倍，树只多一步，链表要多一倍。

03Why “balanced”为什么要“平衡”

If the tree grows only on one side, it becomes a line again — and a line is O(n). A balanced tree keeps left and right about the same height, so the number of steps stays small.如果树只往一边长，它就又变成一条链，又回到 O(n)。平衡的意思是左右高度差不多，步数一直很小。

A red-black tree is a balanced tree with a cheap trick: each node is coloured red or black, and a few colour rules keep it short. When an insert makes it too deep, it repaints and rotates a little.红黑树是一种平衡树，用的是很省的技巧：每个节点涂红或涂黑，几条颜色规则保证它不会太高。插入后如果太深了，就重新涂色、再转一转（旋转）。

Say it like this可以这样说

A red-black tree is a binary tree that colours its nodes red or black and rotates itself after inserts, so the height stays about 2 × log n.红黑树是给节点涂红或黑的二叉树，插入后会自己旋转，保证高度大约是 2 × log n。

04Where you meet it你会在哪里遇到它

• HashMap: when one bucket holds 8 items, that bucket becomes a red-black tree — lookup stays O(log n).HashMap：一个桶里攒够 8 个，就把这个桶变成红黑树，查找仍是 O(log n)。
• TreeMap in Java is a red-black tree. It keeps keys in order.Java 的 TreeMap 就是红黑树，key 是有序的。

→New words新词

Click ▶ hear it for real people on YouGlish; 🔊 for the computer voice.点 ▶ hear it 听真人发音（YouGlish）；点 🔊 听电脑朗读。

✓Check yourself自测

1. Why is a balanced tree O(log n)?为什么平衡树是 O(log n)？
2. What happens if the tree grows only on one side?树只往一边长会怎样？
3. What do the colours in a red-black tree do for us?红黑树里的颜色有什么用？

Answer out loud first. Only then open the answers below.先自己出声答，再看下面的答案。