二叉搜索树

二叉搜索树

概率

一个二叉树，左子数小于根节点，子右数大与根节点。

二叉树的查找

1，从根进行查找，比根小左边大右边。

2，没有找到就为空

时间复杂度为O（n），不可以排除只有单边大数量的东西！

这个原因就是因为不平衡造成的这个条件！所以说后面衍申出了ALV树红黑树等。

代码等一下附上,插入

按照正常的二叉树的性质进行插入，通过对于数据大小的判断进行代码的读写。

删除

首先进行数的查找才能够进行删除！没有直接返回。

1，没有子节点：

直接进行内容的释放

2，有子节点，子节点没有子节点

只有左节点：交换位置，然后释放交换的位置东西。

``

只有右节点：同上

左右子节点都有（而且子节点没有子节点）：

与右节点进行交换，然后释放右节点。

3，子节点全部都有子节点。

需要使用替代方法进行判断，进行交换。不断的判断位置，进行内容的交换。交换到底了，进行内容的释放。