Binary search trees
Python for A-Level CS Lesson 14 2:41 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A binary search tree keeps values sorted by where it puts them.
二叉搜索树靠"把值放在哪里"来保持有序。
Each node holds a value and links to up to two children, and one rule governs the lot.
每个结点持有一个值，并链接到最多两个孩子， 而一条规则管着这全部。
Take the five at the top: everything on its left is smaller.
看最上面那个 5：它左边的一切都更小。
And everything on its right is larger.
而它右边的一切都更大。
That holds at every node, not just the root, and it is what lets a search go left or right and never both.
这在每一个结点上都成立，不只是根， 而这正是让一次查找可以只往左或只往右、绝不两边都走的原因。
In code a node is a tiny object: a value, and two links called a left and a right.
在代码里，一个结点是一个很小的对象： 一个值，和两个叫 left 和 right 的链接。
That is the whole class.
整个类就这些。
And notice what a fresh node looks like — both links start as None, because it has no children yet.
再注意一个刚创建的结点长什么样—— 两个链接都从 None 开始，因为它还没有孩子。
Every insert you write is going to end by hanging a node like this one off something.
你写的每一次插入，最后都是把这样一个结点挂到某个东西下面。
Inserting is that rule, walked.
插入就是把那条规则走一遍。
Put four into this tree.
把 4 放进这棵树。
Start at the root: four is smaller than five, so go left.
从根开始：4 比 5 小，所以往左走。
Now we are at three, and four is bigger than three, so go right.
现在到了 3，而 4 比 3 大，所以往右走。
There is nothing there — so that is where it goes.
那里什么都没有——那就是它的位置。
The code says the same thing recursively, and each call hands back the subtree it just fixed.
代码用递归说的是同一件事， 而每一次调用都交回它刚刚修好的那棵子树。
Now the payoff.
现在是回报的时候。
Visit the tree in this order — left, then the node, then right — and follow along: one, three, four, five, eight.
按这个顺序访问这棵树——先左，再本结点，再右—— 跟着看：1、3、4、5、8。
The values come out already in order, and nothing sorted them.
这些值出来时已经是有序的，而没有任何东西排过序。
The rule put them where they had to be, and the traversal just reads them off.
是那条规则把它们放到了它们必须在的位置，遍历只是把它们读了出来。
Notice how naturally recursive it is: each subtree is traversed the same way.
注意它有多自然地递归：每一棵子树都用同样的方式遍历。
One warning, and it is a favourite exam question.
一个提醒，而且它是考试的常客。
A tree like the one on the left takes about log n steps to search, because each comparison throws away half of it.
像左边这样的树，查找大约要 log n 步， 因为每一次比较都丢掉它的一半。
But insert the same values in the order one, three, four, five, eight — that is, input that arrives already sorted — and every value goes right.
但如果按 1、3、4、5、8 的顺序插入同样的值—— 也就是输入本来就是有序的——那么每一个值都往右走。
You get a line, and searching it is n steps.
你得到的是一条链，而在链上查找要 n 步。
A search only skips half a tree while the tree still has two halves.
只有当树还有两半时，查找才能跳过其中一半。
Four things to take with you.
带走四点。
One: left is smaller, right is larger, at every node.
第一：左小右大，在每一个结点上都成立。
Two: inserting walks down until it finds an empty spot.
第二：插入一路往下走，直到找到一个空位。
Three: in-order traversal visits left, node, right.
第三：中序遍历按"左、本结点、右"访问。
Four: sorted input builds a line and loses the speed.
第四：有序的输入会造出一条链，速度也就没了。
Now write insert, in-order and contains.
现在把 insert、in_order 和 contains 写出来。