不同树数据结构的复杂性

到目前为止，我们已经了解了不同的树类型及其操作。我们不可能逐一介绍每一种树类型及其不同的操作，因为这超出了本书的范围。我们希望对其他树结构及其操作复杂性有一个最基本的了解。下面的图表列出了不同类型树的不同操作和空间的平均复杂度和最坏情况复杂度。我们可能需要根据自己的需求选择不同的树结构：

总结

在本章中，我们详细讨论了非线性数据结构。我们了解到树是分层数据结构，有不同的树类型、操作和复杂性。我们还看到了如何定义二叉搜索树。这对于实现不同的搜索技术和数据存储非常有用。在下一章中，我们将把重点从数据结构转向算法。我们将重点讨论第一类算法—排序算法。