二叉查找树

二叉查找树：

又称为二叉排序树或者二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值。
• 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值。
• 左右子树也分别为二叉排序树。
• 没有键值相等的节点。

二叉查找树的性质：

对二叉查找树进行中序遍历，即可得到有序的数列。

二叉查找树的时间复杂度：

它和二分查找一样，插入和查找的时间复杂度均为O（logn），但是在最坏的情况下仍然会有O（n）的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。

二叉查找树的高度决定了二叉查找树的查询效率。

二叉查找树的插入过程如下：

• 若当前二叉查找树为空，则插入的元素为根节点。
• 若插入的元素值小于根节点值，则将元素插入到左子树中。
• 若插入的元素值不小于根节点值，则将元素插入到右子树中。

二叉查找树的删除，分三种情况进行处理：

• p为叶子节点，直接删除该节点，再修改其父节点的指针。
• p为单支节点。让p的子树与p的父节点相连，删除p节点。