【BST拓扑问题】高效查找产生相同二叉搜索树的给定整数序列的排列数

SOONG, CHINGTSING

January 21, 2024

160 views

No comments

1957 words

学习研究

最近刷数据结构题库时遇到一个有意思的问题，在中文互联网中查询无果，在外文论坛中获得结论，遂在此记录，以防遗忘。

## 问题描述
给定一个整数数组。如{5,2,4,1,8,7}，我们可以得到的BST结构为：
```cpp
    5
   / \
  2   8
 / \ / 
1  4 7  
```

现在，如果我们的输入更改为 [5 2 8 1 7 4]，我们的 BST 结构仍将相同。
以下输入顺序都可以得到相同BST结构。

```cpp
5 2 8 1 4 7
5 2 8 1 7 4
5 2 8 4 1 7
5 2 8 4 7 1
5 2 8 7 1 4
5 2 8 7 4 1
5 2 1 8 4 7
5 2 1 8 7 4
5 2 1 4 8 7
5 2 4 8 1 7
5 2 4 8 7 1
5 2 4 1 8 7
5 8 2 7 1 4
5 8 2 7 4 1
5 8 2 1 7 4
5 8 2 1 4 7
5 8 2 4 7 1
5 8 2 4 1 7
5 8 7 2 1 4
5 8 7 2 4 1
```

那么，给定一个整数数组，如何找到输入数组的不同排列数量，从而产生与原始数组顺序上形成的 BST 相同的 BST？

## 其他提示

在中文互联网中，针对如何找到所有得到相同BST的输入序列的算法是有参考的，但是其计算效率过于缓慢，此算法仅限于找出序列数量，而不输出具体的序列内容。

## 解决方案

采用递归方式进行计算。
1. 对于叶子节点，返回数字1.
2. 对于仅有1个子节点的非叶子节点，该节点返回子节点拓扑顺序数。
3. 对于具有两个子树大小的子节点的非叶节点 |L|以及 |R|，具有 l 和 r 顺序，或者，该数字等于 `l x r x INT(|L|, |R|)`
其中INT(|L|, |R|) = (|L|+|R|)! / (|L|！x |R|!）

## 计算案例

```cpp
Ord(1) = 1
Ord(4) = 1
Ord(2) = 1 x 1 x INT(1, 1) = 2
其中INT(1, 1) = 2! / 1! = 2
Ord(7) = 1
Ord(8) = Ord(7) = 1
Ord(5) = 1 x 2 x INT(3, 2) = 20
其中INT(2, 3) = 5! / (3! x 2!)
```

## 公式分析
l x r x INT（|L|， |R|）的来源如下：
1. “l” 对生成左子树的序列进行排序的不同方式。
2. “r” 对生成右子树的序列进行排序的不同方式，以及。
3. INT（|L|， |R|）混合这两个序列的不同方法，即将它们交错。INT（a，b） = (a + b)! / (a! x b!)
因为在 a+b 元素的所有交织中，我们只对元素序列 a 具有固定顺序的元素序列感兴趣，元素序列 b 也是如此，因此需要将 (a + b)! 除以 a！和 b！分别。

关于第三点，可以理解为我们在l x r时已经得到了保持BST不变的序列数量，但是我们需要考虑到l序列和r序列交错的情况。
比如目前l序列为1 2 3，r的序列为4 5 6，那么保持l为1 2 3顺序（即2在1后面，3在2后面，以此为规律穿插4 5 6）且r序列为4 5 6顺序的序列还有很多。

## 参考文献
[[1] 输出构成某一BST拓扑全部序列的算法代码 (效率慢)](https://gist.github.com/kean/40a1e592a608154b117a0dac48baf25f "[1] 输出构成某一BST拓扑全部序列的算法代码 (效率慢)")
[[2] 查找产生相同二叉搜索树的给定整数序列的排列数](https://itecnote.com/tecnote/r-find-number-of-permutations-of-a-given-sequence-of-integers-which-yield-the-same-binary-search-tree/ "[2] 查找产生相同二叉搜索树的给定整数序列的排列数")
[[3] 公式相关交流与讨论](https://stackoverflow.com/questions/1701612/find-number-of-permutations-of-a-given-sequence-of-integers-which-yield-the-same "[3] 公式相关交流与讨论")

【BST拓扑问题】高效查找产生相同二叉搜索树的给定整数序列的排列数

SOONG, CHINGTSING • 2024 年 01 月 21 日

【BST拓扑问题】高效查找产生相同二叉搜索树的给定整数序列的排列数

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【吉他谱】Aloha Heja He 指弹

【吉他谱】打上花火指弹版

【吉他谱】城南花已开指弹版

【吉他谱】Take Me Hand 指弹版

【吉他谱】溯指弹版

【吉他谱】奇迹的山指弹曲

【BST拓扑问题】高效查找产生相同二叉搜索树的给定整数序列的排列数

飞飞V19[Lansky Bubble.R]v0.300(DNA附魔系统)

【吉他谱】Hazy Moon 指弹中川砂仁

【吉他谱】穿越时空的思念指弹版

【BST拓扑问题】高效查找产生相同二叉搜索树的给定整数序列的排列数

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【BST拓扑问题】 高效查找产生相同二叉搜索树的给定整数序列的排列数

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【BST拓扑问题】高效查找产生相同二叉搜索树的给定整数序列的排列数