左边更小，右边更大

图中内容

1. 1根节点：每次查找都先与它比较
2. 2左子节点：比根小，所以放在左边
3. 3右子节点：比根大，所以放在右边
4. 4右子树中的叶节点：比根大但比它的父节点小，所以挂在父节点的左边

示例

• 猜 1 到 100 之间的数，每次只回答“大了”或“小了”，每猜一次就排除剩下的一半
• 查纸质词典时先翻到中间，再往前或往后翻

测验：左边更小，右边更大（17岁）

1. 1

   在二叉搜索树中，键为 50 的节点的左子树里，任何位置可以出现哪些键？

   • 紧挨着该节点下方的键小于 50，更深处可以是任何键
   • 只能是小于 50 的键
   • 任何键都可以，只要该节点的直接左子节点小于 50
2. 2

   一棵二叉搜索树的根是 50，根的右子节点是 80。新键 60 应该放在哪里？

   • 放在右子树，在 80 的左边
   • 放在右子树，在 80 的右边
   • 放在左子树，因为 60 小于 80
3. 3

   在一棵平衡良好的二叉搜索树中查找一个键时，大约需要检查多少个节点？

   • 树中的每一个节点
   • 先检查一层的所有节点，再往下一层
   • 大约每层一个节点

答案和讲解都在应用里。这节课已离开免费的一周，它的测验包含在订阅中。