<jupyter_start><jupyter_text>SICP 习题 （2.66）解题总结：二叉树的查找 SICP 2.66 提到二叉树的查找，题目的上文提到我们在构建数据库的时候可以把记录的ID按某种方式保存，以便于查找，因为信息的索引和查找是信息系统的两个关键功能。数据库记录的ID可以保存为未排序的列表，也可以保存为排序的列表，还可以保存为二叉树。如果保存为二叉树，它的查找复杂度是O(ln(n))，因为一棵平衡的二叉树的平均高度就是ln(n)。我在做这道题的多年以后接触云计算里的分布式对象存储，发现里面的key的索引用的是同样的方法，突然感叹算法的强大。回到题目的要求，关于实现树的查找，主要就是利用排序的二叉树增强查找的效率。具体实现上就是按照当前分支的值进行判断，如果当前值等于查找值，就返回结果，如果当前值大于查找值，就去左树继续查找，如果当前值小于查找值，就去右树继续查找。 代码如下：<jupyter_code>(define (lookup-tree given-key tree)
  (if (null? tree)
      #f
      (let ((target-key (key (entry tree))))
	(cond ((eq? target-key given-key) (entry tree))
	      ((> target-key given-key) (lookup-tree given-key (left-branch tree)))
	      ((< target-key given-key) (lookup-tree given-key (right-branch tree)))
	      (else (error "impossible value!" (list target-key given-key)))))))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14131736526946106, 'fraction_numerical': 0.00718562874251497, 'mean_word_length': 7.2772277227722775, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '519358', 'license': 'MIT', 'n_tokens_mistral': 530, 'n_tokens_neox': 597, 'n_words': 44, 'path': 'cn/.ipynb_checkpoints/sicp-2-66-checkpoint.ipynb', 'repo_name': 'DamonDeng/sicp_exercise', 'size': '835'}