构建二叉搜索树时，日期字符串词法对比是否优于直接日期对比？

核心结论 #

直接用词法对比无法解决新日期持续晚于旧日期导致的BST退化问题，反而可能引发额外问题。

原因分析 #

• 词法对比的本质：若日期字符串采用YYYY-MM-DD或YYYYMMDD这类时间顺序对齐的格式，词法对比结果和直接日期时间的大小对比结果完全一致。新的晚日期字符串词法上同样会大于旧日期，插入时仍会持续作为右子节点，最终还是退化为退化树。
• 若使用非规范日期格式（如DD/MM/YYYY），词法对比会完全偏离时间顺序，导致BST结构混乱，丧失二叉搜索树的有序性，插入、查询操作都会出错。

解决退化问题的可行方案 #

如果你的场景是新插入的键始终递增，想要避免BST退化，应选择自平衡二叉搜索树（如AVL树、红黑树），或直接使用链表、跳表这类更适配顺序插入的结构。

内容的提问来源于stack exchange，提问作者dodekja