Binary search trees · 二叉搜索树
Binary search trees
- A binary search tree (BST) stores values so they stay sorted and are fast to find.
- Each node holds a value and links to up to two children: a
leftand aright. - The top node is the root. A node with no children is a leaf.
二叉搜索树
- 二叉搜索树(binary search tree, BST)存储数据时让它们保持有序,并且查找很快。
- 每个节点(node)保存一个值,并链接到最多两个子节点:一个
left(左)和一个right(右)。 - 最顶端的节点是根(root)。没有子节点的节点是叶子(leaf)。
The BST rule
- For every node: everything in its left subtree is smaller, everything in its right is larger.
- This one rule is what lets you find a value by going left or right — never both.
BST 规则
- 对每个节点:它左子树里的所有值都更小,右子树里的所有值都更大。
- 正是这一条规则,让你查找一个值时只需向左或向右走 —— 绝不会两边都走。
5
/ \
3 8
/ \ \
1 4 9
left < node < right, at every node
A node
- We model a node as a small object with a
value, aleft, and aright. - A brand-new node has no children yet, so
leftandrightstart asNone.
一个节点
- 我们把节点建模成一个小对象,带有
value(值)、left和right。 - 一个全新的节点还没有子节点,所以
left和right一开始都是None。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
Inserting a value
- Start at the root. If the tree is empty, the new value becomes the root.
- If the value is smaller than the current node, go left; otherwise go right.
- Repeat until you reach an empty spot, and put the new node there.
插入一个值
- 从根开始。如果树是空的,这个新值就成为根。
- 如果这个值比当前节点更小,就向左走;否则向右走。
- 不断重复,直到到达一个空位,把新节点放在那里。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
In-order traversal gives sorted order
- In-order traversal visits: the left subtree, then the node, then the right subtree.
- Because of the BST rule, this visits the values in sorted order — for free.
- It is naturally recursive: traverse left, take the value, traverse right.
中序遍历给出有序顺序
- 中序遍历(in-order traversal)依次访问:左子树、然后节点、再然后右子树。
- 由于 BST 规则,这样会按有序顺序访问所有值 —— 不费额外力气。
- 它天然是递归的:遍历左边、取出值、遍历右边。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(in_order(root)) # [1, 3, 4, 5, 8]
Searching is fast
- To find a value, compare it with the node, then go left or right — skipping half the tree each step.
- In a balanced tree this takes about
O(log n)steps, much faster than scanning a list. - A badly-shaped tree (values inserted already sorted) can degrade to a line —
O(n).
查找很快
- 要查找一个值,把它与当前节点比较,然后向左或向右走 —— 每一步都跳过一半的树。
- 在一棵平衡的树里,这大约只要
O(log n)步,比扫描一个列表快得多。 - 形状糟糕的树(按已排好序的顺序插入)会退化成一条线 ——
O(n)。
Common mistakes
- In a binary search tree: left child < node < right child.
- An unbalanced tree loses the speed advantage.
常见错误
- 在二叉搜索树中:左子 < 节点 < 右子。
- 不平衡的树会失去速度优势。
Now you try
- Build the three core operations:
insert,in_order, andcontains. - The
Nodeclass (and a workinginsert, where you need it) is provided. - Press Check answer to test it on several trees.
现在轮到你
- 实现三个核心操作:
insert、in_order和contains。 Node类(以及在你需要时一个能用的insert)已为你提供。- 按检查答案,在多棵树上测试它。
Searching a BST · 在二叉搜索树中查找
Left is smaller, right is bigger — so each step skips half the tree. · 左小右大——所以每一步都能跳过一半的树。
The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it. · Node 类已提供。编写 insert(root, value),把 value 加入这棵 BST 并返回根。如果 root 是 None,返回一个新的 Node(value)。如果 value < root.value 就往左,否则往右 —— 并把那个子节点重新赋值为向它插入后的结果。
Click Run to see the output here. · 点击“运行”查看此处输出。
Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives []. · Node 和一个能用的 insert 已提供。编写 in_order(root),返回一次中序遍历得到的值列表:先左子树,再本节点的值,再右子树。多亏 BST 规则,这个列表会是有序的。空树(None)返回 []。
Click Run to see the output here. · 点击“运行”查看此处输出。
Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left · 左侧, otherwise search right · 精准的; an empty branch (None) means it is not there. · Node 和一个能用的 insert 已提供。编写 contains(root, value),如果 value 在树里返回 True,否则返回 False。利用 BST 规则:若等于本节点返回 True;若更小就到左边找,否则到右边找;空的分支(None)表示它不在。
Click Run to see the output here. · 点击“运行”查看此处输出。