TUhjnbcbe - 2021/8/31 8:57:00
树是常用的数据结构，而日常使用中，二叉树的使用比较多，主要有二叉搜索树，二叉平衡树。二叉搜索树和二叉平衡树，他们的主要思想是二分法，所以时间复杂度一般是O(logN)。二叉搜索树：非叶子节点的值比左子节点值大，比右子节点小。二叉搜索树是比较简单的，但是问题也很突出，很容易退化成链表，比如插入的数据是有序的时候。链表操作时间复杂度就变成了O(N)了。二叉平衡树解决了二叉搜索树的问题，他在二叉搜索树的基础上，加多了一个限制，节点的左右子树的高度差不能大于1。但是这个条件也导致了维护树的平衡需要复杂的操作。B树，也是一种平衡树，但是一棵M叉树。以下摘自：