TUhjnbcbe - 2021/3/5 17:38:00
在前面的课程里，我们学习了树和二叉树，这一章我们来学习一种特殊的二叉树——二叉排序树（BinarySearchTree）。二叉排序树又称为二叉查找树，二叉搜索树。二叉排序树和普通的二叉树在结构上一样，它要么是一棵空树，要么是这样的一棵二叉树：对任意结点，如果左子树不为空，则左子树上所有结点的权值都小于该结点的权值；如果右子树不为空，则右子树上所有结点的权值都大于该结点的权值；任意结点的左子树和右子树都是一棵二叉排序树；一般而言，二叉排序树上结点的权值都是唯一的。说到这里，那么二叉排序树有什么性质呢？能应用在哪些问题上呢？在二叉排序树上，对于任意结点，如果有左子树和右子树，那么其左子树上结点的权值都小于右子树上结点的权值。如果中序遍历二叉排序树，会得到一个从小到大的序列。二叉排序树的插入和查找效率相对较高，最坏情况下时间复杂度为O(n)，期望的时间复杂度为O(logn)，其中n为树上结点总个数。刚才我们提到了二叉排序树最坏情况下时间复杂度为O(n)，这是为什么呢？最坏情况下，二叉排序树会退化成链表，从根结点往左依次递减，或者从根结点往右依次递增。那有什么方法可以解决这个问题呢？在二叉排序树的基础上可以加些优化，可以让其成为AVL树，红黑树，SBT，Splay等等，这些高级的树结构解决了上面的问题，插入和查找的效率均为O(logn)。在后面的章节里我们会介绍到这些高级的树结构，现在让我们来深入学习二叉排序树吧，加油哦！点击下方“阅读原文”一起学习二叉排序树吧预览时标签不可点收录于话题#个上一篇下一篇