2019-03-19
红黑树，搜索树，大树小树次优树，这些都是二叉树的一种。二叉树指的是每个节点最多只有两个节点的树结构，也就是说理论上说链表也是二叉树的一种。这种结构的优势从二叉树的左右节点不可以调换得以升华。需要注意的是，之后我们会说到二叉搜索树在节点数为 0 的时候也是二叉搜索树，虽然这么说显得很刻意，好像二叉树和这个有什么区别一样，但是二叉树的节点也可以为 0。
二叉搜索树满足以下的条件，或者说满足以下条件的二叉树，或者空的二叉树就是一棵二叉搜索树：
我们可以看出，任意一个节点的值与当前子树的值的关系都是可以预测的，所以插入，搜索，删除的复杂度都是 O(log n)。搜索好说，插入和删除能达到这个性能的原因是二叉树不在乎整体的排序。比如说插入只要沿着树寻找到插入之后也可以符合二叉树性质的位置然后链接子节点就可以了。
之前无意提到的链表也是二叉树的一种。也就是说如果只把节点插入到左节点，树高等于元素数量的时候，二叉树就和链表或者说，二叉搜索树就合线性表是一样的了。线性表的插入搜索和删除都是 O(n)。
之前的一篇里面写了面试之前哪些虽然会但是不确定会不会忘记的东西最好还是看一遍。这不仅仅说的是面试的情况，所谓面试，查漏补缺也，当你看到代码的时候可以大概联系出这个玩意的实现，希望树树表表的结构不是你理解他的阻碍。
提供一个面试的时候方便问的小游戏问题，中国人讲叫拉大车，两个选手每个人分半副扑克牌，轮番放到桌子上，如果现在这张牌与前面任何一张的数字相同就拿走这张到数字那张的所有牌，然后洗牌。谁手中没有牌了谁就输了。
还有一个系统设计的小问题
要做一个提交问题获得所有二手汽车汽车数据的工具，输入品牌型号等等获得符合特征的列表，没有表变换，只有拿数据不用更新数据。所有的汽车数据都存在一个举行数据库里面，需要 ETL 来把它们取出来。
仿佛一片青草在风中摇曳 我看到宁静在远处波动 ——余华