二叉搜索树
二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 左、右子树也分别为二叉排序树
好的二叉搜索树是平衡的，高度是 log(n)，如下图所示
binary tree 1.jpg
不好的二叉搜索树可能类似于链表，高度是 n。
binary tree_02.jpg
二叉搜索树左节点小于它，右节点大于它。
插入操作
假设有一个序列 3 1 8 2 6 7 5，下载进行插入操作，具体操作如下：
- 插入 3，二叉树为空，直接插入
binary tree_03.jpg
- 插入 1, 1 < 3，插入到左子树
binary tree_04.jpg
- 插入 8， 8 > 3 插入右子树
binary tree_05.jpg
- 插入 2，2 < 3 插入左子树，2 > 1 插入右子树
binary tree_06.jpg
- 插入 6， 6 > 3 插入右子树，6 < 8 插入左子树
binary tree_07.jpg
- 插入 5，5 > 3 插入右子树，5 < 8 插入左子树，5 < 6 插入左子树
binary tree_08.jpg
- 插入 7，7 > 3 插入右子树，7 < 8 插入左子树，7 > 6 插入右子树
binary tree_09.jpg
这样二叉排序树就创建完毕了。
中序遍历结果：1 2 3 5 6 7 8，时间复杂度为 T = O(n)
二叉排序树和快速排序使用相同的比较方式，只是比较的顺序不同。
随机化二叉排序树
在插入的时候随机选择节点，将很和快速排序的时间复杂度是相同的。
T = O(nlogn)
网友评论