二叉搜索树
二叉搜索树的性质、操作复杂度、以及退化为链表的最坏情况。
发布 2019年3月19日 标签
#data-structures
#trees
~/posts/binary-search-tree $ cat post.md
大树，普通树，二叉树
红黑树、搜索树、各种次优树，这些都属于二叉树。二叉树指每个节点最多有两个子节点的树结构——按这个定义，链表也算二叉树的退化情况。这种结构的价值在于”左右子树不可互换”——这一点让它能承载顺序信息。需要注意的是，二叉搜索树即使在节点数为 0 时也是合法的（一棵空 BST 也是一棵 BST），二叉树本身也允许节点数为 0。
二叉搜索树
二叉搜索树需要满足以下条件中的一种：要么是空树，要么是满足以下所有条件的二叉树：
- 任意节点的左子树非空时，左子树上所有节点的值都小于该节点的值。
- 任意节点的右子树非空时，右子树上所有节点的值都大于该节点的值。
- 任意节点的左、右子树本身也是 BST。
- 没有键值相同的节点。
由此可见，任意节点的值与所在子树的范围关系是可预测的。搜索、插入、删除的平均复杂度都是 O(log n)。搜索好理解；插入和删除能达到这个复杂度，是因为 BST 不要求整棵树是排序的——插入只要沿着规则找到一个合法位置链上去就行。
最坏情况
链表是二叉树的退化情况。如果所有节点都被插到了某一侧（比如全是左子节点），树高等于节点数，二叉搜索树就退化成了线性表。线性表的查找、插入、删除都是 O(n)——这也是 BST 的最坏情况。