二叉查找树

1，二叉查找树

1）二叉查找树(BST)：中序遍历得到有序序列。左子树节点值小于等于根节点、右子树节点值大于等于根节点。
2）插入节点

image.png
3）删除节点
image.png
image.png
image.png

2，BST树优劣

1）理想情况下增删改查O(logN)，最坏O(N)。插入节点本身有序，排序二叉树退化为链表。
2）不同的插入顺序导致树的高度不一样。数据插入会导致树的倾斜，树的高度直接影响了数据查找效率。