1.二叉排序树(BST)

发表于 分类于 ， 本文字数： 371

二叉排序树，又叫二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）。

1.BST树的特点

排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：

  • 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 它的左、右子树也分别为排序二叉树。
  • 没有键值相等的节点。

img

由排序二叉树的特点，我们很容易得出这样的结论：按中序遍历排序二叉树可以得到由小到大的有序序列。排序二叉树要求所有的元素都能够排序，也就是键要实现comparable接口。

2.BST树的缺点

排序二叉树虽然可以快速检索，但出现最坏的情况——如果插入的节点集本身就是有序的(从小到大排列或从大到小排列)，在这种情况下，排序二叉树就退化成了普通链表，其检索效率就会很差。

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏