二叉搜索树

简单来说，就是维护一个左子树的节点值 < 根节点值 < 右子树的节点值的二叉树。所以中序遍历之后就是一个升序排列的结果。

搜索

每次判断当前node的指与当前需要查找的数值的大小关系 ——

1. 相等：查找成功
2. 目标数值更小：搜索左子树
3. 目标数值更大：搜索右子树

插入

每次判断当前node的数与需要插入的值的大小关系 ——

1. 目标数值更小：插入左子树
2. 目标数值更大：插入右子树

如果node为空，则直接设为当前节点的值

缺陷

对于理想情况，在每次插入/搜索的时候会排除一半的节点，那么时间复杂度应该是$O({\log }_2(n))$，但是假设在极端情况下——假设退化成了单枝树，就会退化成$O(n)$的时间复杂度，和直接查找并无二异，非常垃圾。

所以延伸出平衡二叉搜索树（简称平衡二叉树），作为优化手段，防止退化

代码参考

插入核心代码参考 ——

private BinaryTreeNode<T> InsertRec(BinaryTreeNode<T> node, T value)
{
	if (node == null) return new BinaryTreeNode<T>(value);
	int cmp = value.CompareTo(node.Value);
	if (cmp < 0) node.Left = InsertRec(node.Left, value);
	else if (cmp > 0) node.Right = InsertRec(node.Right, value);
	return node;

}

搜索核心代码参考 ——

private bool SearchRec(BinaryTreeNode<T> node, T value)
{
	if (node == null) return false;
	int cmp = value.CompareTo(node.Value);
	if (cmp == 0) return true;
	return cmp < 0
		? SearchRec(node.Left, value)
		: SearchRec(node.Right, value);
}