问给定n个不同的键，可以构造多少个不同的2-3/红黑树？
EN

Software Engineering用户

提问于 2014-02-11 20:48:59

回答 1查看 237关注 0票数 2

记忆刷新器/我的理解：

2-3树是一个平衡的搜索树，允许两种类型的节点.

2节点:有两个子节点的正常节点。
- LChild < Parent和RChild >父母
3节点:具有两个父节点和三个子节点。
- Parent1 < Parent2
- LChild < Parent1，Parent1 < MChild < Parent2，RChild >父母2

一棵2-3棵树总是平衡的，当根将树的高度提高一倍时，树就会长出来。

http://en.wikipedia.org/wiki/2%E2%80%933_树

那么，我的问题是，给定n个不同的键，一个树可以构造多少个不同的2-3棵树？

我的数学能力很差，所以如果有人知道我应该如何“数学”来接近答案，那就太棒了！:)

发布于 2014-02-11 21:07:36

设T[n]是有n键的2-3棵树的数目.我们有：

T[n] =和k (从1到n of T[k - 1] * T[n - k] )，因为我们可以用键k创建一个2节点，用带键1, ..., k - 1的左树创建一个2节点，用键k + 1, ..., n生成右树。对于左树的每一次排列，我们都有右树的排列，所以我们必须把这两棵树相乘。当我们处理两个节点时，这是很重要的；
T[n] +=和k从1到n和p从k + 1到n of T[k - 1] * T[p - k - 1] * T[n - p]。当我们处理三个节点时，这就算得上了；

基本情况是T[0] = 1。

票数 2

页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://softwareengineering.stackexchange.com/questions/233381

复制

相似问题