二元搜尋樹 二叉查找树英語Binary Search Tree也称为二叉搜索树有序二叉树ordered binary tree或排序二叉树sorted binary tree是指一棵空树或者具有下列性质的二叉树 若任意节点的左子树不空则左子树上所有节点的值均小于它的根节点的值 若任意节点的右子树不空则右子树上所有节点的值均大于它的根节点的值 任意节点的左右子树也分别为二叉查找树 二叉查找树相比于其他数据结构的优势在于查找插入的时间复杂度较低为 O  log  n  displaystyle Olog n 二叉查找树是基础性数据结构用于构建更为抽象的数据结构如集合多重集关联数组等 二叉查找树的查找过程和次优二叉树类似通常采取二叉链表作为二叉查找树的存储结构中序遍历二叉查找树可得到一个关键字的有序序列一个无序序列可以透過建構一棵二叉查找树变成一个有序序列建構树的过程即为对无序序列进行查找的过程每次插入的新的结点都是二叉查找树上新的叶子结点在进行插入操作时不必移动其它结点只需改动某个结点的指针由空变为非空即可搜索插入删除的复杂度等于树高期望 O  log  n  displaystyle Olog n 最坏退化為偏斜二元樹 O  n  displaystyle On 對於可能形成偏斜二元樹的問題可以經由樹高改良後的平衡樹將搜尋插入刪除的時間複雜度都維持在 O  log  n  displaystyle Olog n 如AVL树红黑树等