倾斜树与二叉搜索树的关系

Question

3

我知道什么是二叉搜索树，并且我知道它们如何工作。但是，让它成为倾斜树需要什么条件？我的意思是，所有节点是否都必须在一侧？还是有其他组合方式？

只有像下面这样的树形状才能形成倾斜树吗？如果不是，还有哪些可能的倾斜树形状？

倾斜树示例：

此外，我搜索了但找不到一个好的、实用的倾斜树的定义。有人有一个好的定义吗？

- user4339896

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James Beach · Answer 1

一个关于斜树的好定义是二叉树，除了一个节点外，所有节点都只有一个孩子。（剩下的节点没有孩子。）另一个好的定义是，它是一个由n个节点组成的二叉树，其深度为n-1。

- user4339896 · Answer 2

发现一棵倾斜的树是树的最坏情况。

`1，2，...n的排列数=n!`

二叉搜索树形状数：（1/n+1）（2n！/n！n！）

`1，2，....n的倾斜树数=2^(n-1)`

这里有一个我被展示的例子： http://i61.tinypic.com/4gji9u.png

- Suman · Answer 3

一个只由左子节点或右子节点主导的二叉树被称为倾斜二叉树，更具体地说是左倾斜二叉树或右倾斜二叉树。