README.md

找BST第k小的节点

plan

任务目标

1. 找bst的第几个排序节点

任务分析

也可以理解为中序遍历(左根右)的第几个节点。 bst基于key的查找是不需要保持父节点和父节点的右子树的关系， 但是查找第几个，是有必要存的,所以使用迭代不太合适， 最合适的还是递归,有两种方式：

1. 中序遍历 + 计数，计数达到k时，退出
2. 多次左子树遍历来逼近k

递归1的特点是左右子树都遍历，每个节点做多遍历一次; 递归2的特点是只遍历节点的左子树，不关心右子树，一旦k节点在左子树， 可能会发生"左子树会遍历多次",针对这点，可以专门设计一个测试环节

课题

使用"中序遍历+计数"的方式来实现; 使用"多次左子树遍历"的方式来实现; 使用基准测试来比较两者的差别

课题的解决方案

• 实现上面的几种思路，并基于基准测试获取对比数据
• 可专门准备数据环境来测试递归2的多次遍历
• 使用go和tdd来实现(正好在熟悉这块)
• 可用图表的方式来展示最后的测试结果

Do

确定行动措施

1. 以tdd的方式完成几种实现方式
2. 完善基准测试
3. 可视化分析

# 用下面命令来生成性能分析文件
go test -bench="." -benchmem -cpuprofile profile.out

# 用下面的命令来在web生成可视化图
go tool pprof -http=172.17.0.2:8000 profile.out

Check

• 本次测试都是利用go原生结构实现，并未使用优化
• 基准测试的结果如下：
  • 完全退化的情况下(基本上退化成链表了)， "中序遍历+计数"和"多次左子树遍历"的效率相差不大
  • 普通bst，前者的效率比后者高非常多，性能相差甚至呈指数关系
• 分析：后者有额外的迭代，当最后寻找的节点分布在树的左下或右下时，效率最低

Adjust

• 本次的测试例子并未局限于之前学习的技能
• 将数据的准备和最后结果的比较都抽象出来了
• 甚至将对比的两个函数作为参数来测试最终结果的正确性
• 本次主要是两个算法的效率，而不是测试功能，才这样做的
• 后期可以将这种算法的正确测试和业务的功能测试结合起来
• 其次基准测试的样本多了之后，就容易看出结论了，以后一定要注意这点
• 测试例子写之间就考虑到了两种算法的边界问题，最后也都测试到了

总结

2019.10.21

虽说在极端情况(退化情况下)两者的效率相差不大, 但是非退化情况下，中序+计数的效率要高很多。

并不是说多次左子树遍历没有意义，相反，这个独特的角度看待问题，非常有启发。

附录

主要包含一些知识点信息

Binary Tree (BT), 也叫二叉树，最多有两个子树的树结构，左边的叫左子树， 右边的叫右子树。BT常用于实现二叉查找树BST,二叉堆BH(binary heap).

二叉树的详细部分，可查看yb-post

二叉树遍历的几个个术语：

• 前序遍历，根左右 pre-order
• 中序遍历，左根右 in-order
• 后序遍历，左右根 post-order

这几种遍历都属于深度优先，具体说明