The Profile of Binary Search Trees

The Profile of Binary Search Trees
复制标题

二叉搜索树简介

DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Jean Jabbour
Jean Jabbour
中科院分区：
--
文献类型：
--
作者：
B. Chauvin;M. Drmota;Jean Jabbour

文献摘要

被引文献

相似文献

我们描述了中心区域 1 (cid:4) 2log n ≤ k ≤ 2 (cid:4) 8log n 的二叉搜索树 T n 的 k 级节点数量的限制行为。特别是，我们证明宽度 (cid:2) V n （同一级别的内部节点的最大数量）满足 (cid:2) V n ∼ (cid:4) n/ (cid:1) 4 π log n (cid:5)，因为 n → ∞ a.s.
We characterize the limiting behavior of the number of nodes in level k of binary search trees T n in the central region 1 (cid:4) 2log n ≤ k ≤ 2 (cid:4) 8log n . Especially we show that the width (cid:2) V n (the maximal number of internal nodes at the same level) satisfies (cid:2) V n ∼ (cid:4) n/ (cid:1) 4 π log n (cid:5) as n → ∞ a.s.