二叉查找树：
又称为二叉排序树或者二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。
- 若左子树不空，则左子树上所有节点的值均小于它的根节点的值。
- 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值。
- 左右子树也分别为二叉排序树。
- 没有键值相等的节点。
二叉查找树的性质：
对二叉查找树进行中序遍历，即可得到有序的数列。
二叉查找树的时间复杂度：
它和二分查找一样，插入和查找的时间复杂度均为O（logn），但是在最坏的情况下仍然会有O（n）的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。
二叉查找树的高度决定了二叉查找树的查询效率。
二叉查找树的插入过程如下：
- 若当前二叉查找树为空，则插入的元素为根节点。
- 若插入的元素值小于根节点值，则将元素插入到左子树中。
- 若插入的元素值不小于根节点值，则将元素插入到右子树中。
二叉查找树的删除，分三种情况进行处理：
- p为叶子节点，直接删除该节点，再修改其父节点的指针。
- p为单支节点。让p的子树与p的父节点相连，删除p节点。
网友评论