二元搜尋樹

二叉查找树的遍历

中序遍历（in-order traversal）二叉查找树的Python代码：
def traverse_binary_tree(node, callback):
    if node is None:
        return
    traverse_binary_tree(node.leftChild, callback)
    callback(node.value)
    traverse_binary_tree(node.rightChild, callback)

排序（或称构造）一棵二叉查找树

用一组数值建造一棵二叉查找树的同时，也把这组数值进行了排序。其最差时间复杂度为。例如，若该组数值已经是有序的（从小到大），则建造出来的二叉查找树的所有节点，都没有左子树。自平衡二叉查找树可以克服上述缺点，其时间复杂度为O(nlog n)。一方面，树排序的问题使得CPU Cache性能较差，特别是当节点是动态内存分配时。而堆排序的CPU Cache性能较好。另一方面，树排序是最优的增量排序（incremental sorting）算法，保持一个数值序列的有序性。
def build_binary_tree(values):
    tree = None
    for v in values:
        tree = binary_tree_insert(tree, v)
    return treedef get_inorder_traversal(root):
    '''    Returns a list containing all the values in the tree, starting at *root*.    Traverses the tree in-order(leftChild, root, rightChild).    '''
    result = []
    traverse_binary_tree(root, lambda element: result.append(element))
    return result

二叉查找树性能分析

每个结点的为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度为，其平均查找长度为（和顺序查找相同），最好的情况是二叉查找树的形态和折半查找的判定树相同，其平均查找长度和成正比（）。

二叉查找树的优化

一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。请参见主条目平衡树。