有没有建立平衡二叉搜索树的方法?
例子:
1 2 3 4 5 6 7 8 9
5
/ \
3 etc
/ \
2 4
/
1
我认为有一种方法可以做到这一点,而无需使用更复杂的自平衡树。否则我可以自己做,但有人可能已经这样做了:)
感谢您的回答!这是最终的 Python 代码:
def _buildTree(self, keys):
if not keys:
return None
middle = len(keys) // 2
return Node(
key=keys[middle],
left=self._buildTree(keys[:middle]),
right=self._buildTree(keys[middle + 1:])
)
最佳答案
对于每个子树:
- 找到子树的中间元素并将其放在树的顶部。
- 找到中间元素之前的所有元素,并递归地使用该算法得到左子树。
- 找到中间元素之后的所有元素,并递归地使用此算法来获得正确的子树。
如果您首先对元素进行排序(如您的示例所示),则可以在常数时间内找到子树的中间元素。
这是一种构造一次性平衡树的简单算法。它不是自平衡树的算法。
以下是一些 C# 源代码,您可以自己尝试:
public class Program
{
class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
}
TreeNode constructBalancedTree(List<int> values, int min, int max)
{
if (min == max)
return null;
int median = min + (max - min) / 2;
return new TreeNode
{
Value = values[median],
Left = constructBalancedTree(values, min, median),
Right = constructBalancedTree(values, median + 1, max)
};
}
TreeNode constructBalancedTree(IEnumerable<int> values)
{
return constructBalancedTree(
values.OrderBy(x => x).ToList(), 0, values.Count());
}
void Run()
{
TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9));
// displayTree(balancedTree); // TODO: implement this!
}
static void Main(string[] args)
{
new Program().Run();
}
}
关于c# - 构建平衡的二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2893318/