二叉查找树(Binary Search Tree)也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点（no duplicate nodes）。
支持的操作:
- 遍历
- 查询
- 查找
- 最大关键字元素和最小关键字元素
- 后继和前驱
- 插入和删除
伪代码:
x = T.root
遍历
//中序遍历 Inorder-Tree-Walk(x) if x ≠ NIL Inorder-Tree-Walk(x.left) print x.key Inorder-Tree-Walk(x.right)
查找
//递归版 Tree-Search(x,k) if x == NIL or k == x.key return x if k < x.key return Tree-Search(x.left,k) else return Tree-Search(x.right,k) //迭代版 Iterative-Tree-Search(x,k) while x ≠ NIL and k ≠ x.key if k < x.key x = x.left else x = x.right return x
最大关键字元素和最小关键字元素
//最小关键字元素 Tree-Min(x) while x.left ≠ NIL x = x.left return x //最大关键字元素 Tree-Max(x) while x.left ≠ NIL x = x.right return x
后继和前驱
//中序遍历后继 Tree-Successor(x) if x.right ≠ NIL//x有右孩子,则后继是其右孩子的最小关键字元素 return Tree-Min(x.right) //x无右孩子,若x是左孩子,则后继是其父结点,若x是右孩子,则后继是x的有左孩子的最底层祖先,可能不存在(NIL) y = x.p while y ≠ NIL and x == y.right x = y y = y.p return y //中序遍历前驱 Tree-Predeccessor(x) if x.left ≠ NIL//x有左孩子,则后继是其左孩子的最大关键字元素 return Tree-Max(x.left) //x无左孩子,如果当前结点是其父亲的右孩子，则该父亲是其前驱 y = x.p while y ≠ NIL and x==y.left x = y y = y.p return y
插入
//先找到插入位置,再确定插入结点是左孩子、右孩子还是树根,每次插入的新的结点都是二叉查找树上新的叶子结点 Tree-Insert(T,z) y = NIL//记录z父结点 x = T.root//记录z的插入位置 while x ≠ NIL y = x if z.key < x.key x = x.left else x = x.right z.p = y if y == NIL T.root = z else if z.key < y.key y.left = z else y.right = z
删除
//用子树v替换子树u,并建立v与u.p的父子关系 Transplant(T,u,v) if u.p == NIL T.root = v else if u == u.p.left u.p.left = v else u.p.right = v if v ≠ NIL v.p = u.p //删除,分三种情况 Tree-Delete(T,z) if z.left == NIL//左子树为空 Transplant(T,z,z.right) else if z.right == NIL//右子树为空 Transplant(T,z,z.left) else//又分两种情况 y = Tree-Min(z.right)//z的后继 if y.p ≠ z//y不是z的右孩子就将其转换成右孩子 Transplant(T,y,y,right) y.right = z.right y.right.p = y Transplant(T,z,y) y.left = z.left//建立y与z.left的父子关系 y.left.p = y
时间复杂度:二叉查找树search,minimum,maximum,predecessor,successor,insert,delete的时间复杂度T(n)=O(h),O(lg n)=<h<=O(n)为树的高度,最差性能为O(n),最好性能为O(lg n)。可以证明n个不同关键字随机构建的二叉搜索树的期望高度为O(lg n).故平均性能接近最好性能，即T(n)=O(lg n).
中序遍历二叉查找树可得到一个关键字的有序序列。
每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。