[科普中国]-最佳化二元搜寻树

计算器科学中， 一个最佳二叉搜索树（BST），有时也被叫做重量平衡二叉树， 是有可能在已知的一串序列中得到最短搜索时间的一棵二叉搜索树（或期望的搜索时间）。 最优化二叉搜索树可分为两种：静态的和动态的。

简介计算器科学中，一个最佳二叉搜索树（BST），有时也被叫做重量平衡二叉树，是有可能在已知的一串序列中得到最短搜索时间的一棵二叉搜索树（或期望的搜索时间）。最优化二叉搜索树可分为两种：静态的和动态的。

静态的最优化问题中，在完全被创建好之前，这棵树是不能被修改的。在这状况中，在这棵树中的每个节点都存在特定的设计，这些设计是依照每个节点被访问的机率去设计出会得到最短的搜索时间。不同的算法能依照每笔数据所给的访问机率去创建或逼近地做出一个静态的最优化树。

动态的最优化问题中，这棵树可以在任何时间被修改，是允许运行树旋转的。这棵树有一个从树的根开始的指针，他可以借着移动并使用他去修改一棵树。在这状况里，一定会有一连串序列是有着最小的花费，使得这个指针要去走访整棵树去找出这个序列。伸展树被推测和动态最优化树在任何的情况下都有一个常量比率存在，虽然这还没有被证明出来。1

树旋转在离散数学中，树旋转（英语：Tree rotation）是在二叉树中的一种子树调整操作, 每一次旋转并不影响对该二叉树进行中序遍历的结果. 树旋转通常应用于需要调整树的局部平衡性的场合。1

期望值在概率论和统计学中，一个离散性随机变量的期望值（或数学期望、或均值，亦简称期望，物理学中称为期待值）是试验中每次可能的结果乘以其结果概率的总和。换句话说，期望值像是随机试验在同样的机会下重复多次，所有那些可能状态平均的结果，便基本上等同“期望值”所期望的数。需要注意的是，期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。（换句话说，期望值是该变量输出值的平均数。期望值并不一定包含于变量的输出值集合里。）1

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学