此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
二叉搜索树
- 二叉搜索树(binary search tree, BST)存储数据时让它们保持有序,并且查找很快。
- 每个节点(node)保存一个值,并链接到最多两个子节点:一个
left(左)和一个right(右)。 - 最顶端的节点是根(root)。没有子节点的节点是叶子(leaf)。
BST 规则
- 对于每个节点:其左子树中的所有元素都较小,其右子树中的所有元素都较大或相等(本课将相等的值放入右侧)。
- 正是这一条规则,让你查找一个值时只需向左或向右走 —— 绝不会两边都走。
English
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
一个节点
- 我们把节点建模成一个小对象,带有
value(值)、left和right。 - 一个全新的节点还没有子节点,所以
left和right一开始都是None。
English
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
插入一个值
- 从根开始。如果树是空的,这个新值就成为根。
- 如果这个值比当前节点更小,就向左走;否则向右走。
- 不断重复,直到到达一个空位,把新节点放在那里。
English
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)依次访问:左子树、然后节点、再然后右子树。
- 由于 BST 规则,这样会按有序顺序访问所有值 —— 不费额外力气。
- 它天然是递归的:遍历左边、取出值、遍历右边。
English
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]
查找很快
- 要查找一个值,把它与当前节点比较,然后向左或向右走 —— 每一步都跳过一半的树。
- 在一棵平衡的树里,这大约只要
O(log n)步,比扫描一个列表快得多。 - 形状糟糕的树(按已排好序的顺序插入)会退化成一条线 ——
O(n)。
常见错误
- 在二叉搜索树中:左子节点 < 当前节点 <= 右子节点(此处相等的值归入右侧)。
- 不平衡的树会失去速度优势。
现在轮到你
- 实现三个核心操作:
insert、in_order和contains。 Node类(以及在你需要时一个能用的insert)已为你提供。- 按检查答案,在多棵树上测试它。
探索
在二叉搜索树中查找
左小右大——所以每一步都能跳过一半的树。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
Node 类已提供。编写 insert(root, value),把 value 加入这棵 BST 并返回根。如果 root 是 None,返回一个新的 Node(value)。如果 value < root.value 就往左,否则往右 —— 并把那个子节点重新赋值为向它插入后的结果。
点击“运行”查看此处输出。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
Node 和一个能用的 insert 已提供。编写 in_order(root),返回一次中序遍历得到的值列表:先左子树,再本节点的值,再右子树。多亏 BST 规则,这个列表会是有序的。空树(None)返回 []。
点击“运行”查看此处输出。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
Node 和一个能用的 insert 已提供。编写 contains(root, value),如果 value 在树里返回 True,否则返回 False。利用 BST 规则:若等于本节点返回 True;若更小就到左边找,否则到右边找;空的分支(None)表示它不在。
点击“运行”查看此处输出。