---
title: Claude3.5 实现二叉搜索树的可视化
date: '2024-09-08 14:00:00'
tags: ['claude']
keywords: ['Claude3.5 辅助前端', '二叉搜索树', '算法可视化']
description: 二叉搜索树是一种特殊的二叉树，每个节点的左子树的值都小于该节点的值，右子树的值都大于该节点的值。本文用 Claude3.5 实现一个二叉搜索树的可视化，支持插入，删除和查找操作。
---

在看 [LevelDB 源码](https://selfboot.cn/tags/leveldb/) 的时候，里面有跳表实现，然后跳表的论文中有提到二叉搜索树，于是想着来实现一个二叉搜索树的可视化。于是开始压榨 Claude3.5，让它和我一起实现。

这里是最终效果，大家[可以来体验](https://gallery.selfboot.cn/zh/algorithms/binarysearchtree)：

![二叉搜索树可视化](https://slefboot-1251736664.file.myqcloud.com/20240908_ai_gallery_binarysearchtree.webp)

## 简单版本

Claude3.5 整体理解能力不错，按照之前的经验，开始的时候提示词可以很简单就行，Claude3.5 有不少先验的知识。我的提示词如下：

> 我想用 react 和 tailwind 实现一个搜索二叉树的可视化。给定 key，生成二叉树，支持插入，删除和查找操作。

另外，项目其他部分用了 headlessui，为了保持风格统一，同时不引入过多 UI 组件，所以这里告诉 Claude 继续用 headlessui。第一个版本很快就好了，但是页面什么都没有，只有一个空白的区域。于是继续提问：

> 我想要看到可视化的一个二叉树的，目前什么都没。

Claude 修复了一些问题，接着我再次刷新页面，就看到了一个二叉树的结构。不过这时候输入数字，然后点插入节点后，整个页面又没有内容了。继续提问：

> 现在输入数字点插入后，整个树不见了

Claude3.5 承认这个是一个严重的 bug，还真是敢于认错呢，哈哈。接着给出了修复方案，主要是确保在插入新节点后能更新树的可视化展示。

经过前面的几轮对话，已经有一个初步的版本了。目前在二叉搜索树中支持插入，删除和查找操作，并且能给出树节点的可视化展示。下面是这个版本的效果图：

![二叉搜索树可视化初始版本](https://slefboot-1251736664.file.myqcloud.com/20240826_ai_gallery_bst_first.png)

## 树布局优化

不过这个版本的树布局还是有点问题，插入多几个节点，**树的高度稍微深一些，就会变得特别宽，导致在屏幕上需要滚动才能看到整个树**。我想要的树布局，能够紧凑一些，在屏幕中显示更多的节点，这样体验会更好些。这里经过了好多轮的对话，不断调整一些细节，整体比较曲折。

其实开始的时候自己的思路也不太对，想着用之前[堆的可视化中](https://gallery.selfboot.cn/zh/algorithms/heap)节点的布局算法。提示词如下：

> 插入后树的宽度很宽，不适合阅读了。
> 这里提供你一个思路，来合适画树的结构。
> 
> 每次增加新的层之后，你要保证最底层节点很紧密，可以间隔一个节点的宽度。然后逐层往上面计算每层节点之间的间隔。之后根据这些间隔来绘制整个树。

Claude 照常拍马屁，然后就按照这个思路来实现，效果并不好，因为这里二叉搜索树每层可能比较稀疏，导致中间层节点之间的间隔太大。和最开始的版本有同样的问题，甚至更严重些，如下图：

![二叉搜索树可视化布局间距过大](https://slefboot-1251736664.file.myqcloud.com/20240826_ai_gallery_bst_heap.png)

那么直接提示它，让它每层间距不要太大，布局紧凑些，然后同一层的节点不要有重叠就好。得到了下面的结果：

![二叉搜索树可视化-错误的版本](https://slefboot-1251736664.file.myqcloud.com/20240827_ai_gallery_bst_error.png)

这里是紧凑了，不过节点分布都有问题，左右子树节点位置都不对。中间经过几轮尝试，自己的思路也慢慢清晰，我们想要树布局尽量紧凑，同时不能有节点的交叉和重叠，那么只需要满足：

1. 每个节点的所有子节点都必须在所有**左兄弟节点**的右侧。
2. 每个节点的所有子节点都必须在所有**右兄弟节点**的左侧。

也就是说在同一层中，所有小的节点肯定要在大的节点左边，不能有重叠交叉。**想好算法之后**，把上面算法简单描述了下，Claude3.5 很快就给出了实现思路，整体改动如下：

1. 新的布局算法：_updateLayout 方法现在使用一种新的算法来分配节点坐标。
2. 节点计数：引入了 getNodeCount 函数来计算每个子树的节点数量，这有助于更准确地分配空间。
3. 递归坐标分配：assignCoordinates 函数递归地为每个节点分配坐标，确保左子树总是在右子树的左边。
4. 动态空间分配：每个节点的位置是基于其左右子树的节点数量动态计算的，这确保了更均匀的分布。
5. 层次对齐：同一层的节点会有相同的y坐标，确保水平对齐。
6. 避免交叉：通过计算每个节点的相对位置，确保同一层的节点从左到右按大小排序，避免了交叉问题。

下面是布局的效果图，可以看到在有很多节点的情况下，整体布局比较紧凑，并且符合前面的要求。

![二叉搜索树可视化布局优化](https://slefboot-1251736664.file.myqcloud.com/20240826_ai_gallery_bst_layout.png)

## 优化界面

二叉搜索树的布局问题解决了，接着优化下界面部分。目前比较简单，只能输入数字，然后插入，删除和查找节点。但是一个个节点插入的话也比较麻烦，可以支持一种更方便的初始化节点方法。考虑到二叉搜索树在顺序插入和随机插入下的性能差异，这里可以支持两种初始化方式。同时为了让整个页面布局和其他可视化工具保持基本一致，这里也调整了下设置部分的布局。

由于之前的聊天上下文已经够长了，为了**避免更快消耗 Claude3.5 的额度**：

> Your limit gets used up faster with longer conversations, notably with large attachments. For example, if you upload a copy of The Great Gatsby, you may only be able to send 15 messages in that conversation within 5 hours, as each time you send a message, Claude “re-reads” the entire conversation, including any large attachments.
> Ref: https://support.anthropic.com/en/articles/8324991-about-claude-pro-usage

接着在 Claude 新开了一个对话，直接把之前的完整代码复制过去，然后提示如下：

> 这里是二叉搜索树的可视化实现。帮我优化下：
> 1. 分两个区域。大屏幕下分左右，左边是展示区域，占3/4，右边是设置区域，占1/4，每个按钮一行。小屏幕下分上下，上面是设置，下面是展示；
> 2. 支持设置初始的节点数量，最大可以50个。然后支持选择初始化方法，有随机初始化和顺序初始化。

于是 Claude 重构了界面部分，增加了初始化按钮。不过开始的版本 SVG 树部分不支持滚动，节点可能会超出屏幕，又重新提示一遍，加上了滚动条。最后效果如下，这里是按照顺序初始化 15 个节点：

![二叉搜索树可视化界面效果](https://slefboot-1251736664.file.myqcloud.com/20240827_ai_gallery_bst_improve.png)

## 添加动画

接着想为整个可视化增加些动画演示，比如插入节点的时候，想演示整个搜索路径，然后高亮显示。其实每次可视化动画算是 AI 比较难实现的部分了，可能和这里的需求本来就很难描述有关。这里我重开了一个对话，避免之前对话太长，导致 Claude效果变差。重开后把目前所有代码都传了上去，作为参考代码，然后用下面的提示词：

> 这个是二叉搜索树的可视化，目前支持树的布局和插入，删除，搜索操作。现在我想优化下可视化过程，支持显示插入，删除和搜索的过程。
> 1. 插入的时候，依次高亮查找路径上的每个节点。直到插入所有节点后，再取消高亮。
> 2. 搜索的时候，依次高亮查找路径上的每个节点。直到最后查找成功或者失败。
> 3. 删除的时候，依次高亮查找路径上的每个节点。然后删除节点，并调整树结构。
>要求改动尽量少，并且代码要灵活。

给出的代码有各种问题，开始的版本一下子就高亮整个路径，并且给出了新插入的节点。删除的时候，还报错。后来经过几轮对话，慢慢修复了各种小问题。然后刚好又看到 cursor 比较火，就尝试了下用 cursor 进行后续的开发。试着让 Cursor 来帮我修小的 bug，比如删除节点的时候，如果节点不存在，目前的版本还是会显示删除成功，于是直接让 AI 来改动，如下图：

![二叉搜索树增加动画](https://slefboot-1251736664.file.myqcloud.com/20240903_ai_gallery_bst_deletenode.png)

AI 给出了所有的改动，我这里先看了下，然后直接 Apply 了。在没用 cursor 的时候，还需要手动从 claude 中找到改动的差异部分，然后自己粘贴过来。相比之下，用 cursor 只需要看代码 diff，然后决定是否采纳。之后自己再测试一遍功能就行了，哈哈，感觉自己现在是一个测试人员了。

## 国际化支持

到这里基本功能算是差不多了，接着想支持下国际化，因为整个站点本来就是支持中英文的。打开 content.js 后，直接发起聊天，让 cursor 用 claude3.5 帮我支持翻译。

> 修改整个文件，在之前写死文案地方，支持翻译国际化。最后再修改翻译文件 zh.json 和 en.json

AI 生成部分和之前直接用 claude 区别不大，主要是修改代码中写死的文案，然后增加翻译文件。不过 cursor 强大之处在于可以点击 Apply，这样代码变更就直接 patch 到了文件中。我只用一路查看，然后确认即可。

![二叉搜索树增加国际化支持 by cursor](https://slefboot-1251736664.file.myqcloud.com/20240903_ai_gallery_bst_i18n.png)

不过后面的翻译 json 文件目前还不能按照我之前的风格自动添加到 en.json 和 zh.json ，还需要稍微手工编辑下，算一点美中不足吧。

## 测试

为了后续改动后，不每次手动测试，这里干脆试试让 AI 帮我写测试用例。之前没写过前端的测试用例，还真不知道要怎么测试 UI 组件。先来看看 AI 怎么回答吧，提示词也很简单：

> 怎么为这里的二叉搜索树可视化页面，提供完整严谨的测试呢

Claude3.4 立马提供了详细的思路和实现代码：

单元测试：测试 BinarySearchTree 类和 TreeNode 类的各个方法。
组件测试：测试组件的 UI 展示。
快照测试：创建组件的快照，以检测意外的UI更改。听起来有点高端这个。
端到端测试：使用 Cypress 或 Playwright 进行端到端测试，模拟用户交互和视觉检查。
性能测试：使用 React 性能工具或 Lighthouse 进行性能测试，特别是对于大型树的渲染。（这个其实没给出代码，不过可以继续追问，我这里懒得继续了）

相当不错的回复，当然我还没来得及细看他的测试用例，等后面专门来一篇文章，介绍怎么给这个站点的可视化工具添加测试用例。

## 总结

得益于 Claude3.5 强大的理解和编程能力，整个实现过程还是比较顺利的。不过中间也踩了不少坑，比如一开始的树布局，最开始的时候思路不对，导致效果不好。中间也有一些小的 bug，需要不断去修复，比如删除节点的时候，如果节点不存在，目前的版本还是会显示删除成功。

之前使用 Github copilot 的时候，编码过程只能往下补全，并没有很好利用大模型的优势。现在尝试了下 cursor，发现确实能提高不少开发效率，专注于代码提示，AI 改动后的代码会自动更新到编辑器中，真是舒服。
