二叉查找树原理理解
二叉查找树原理理解
1.问题的提出
查找数组中第k小的数，且要求m次动态更新。
很容易想到每插入一个数就排序一遍，时间效率O(mnlogn）
注意到每次只插入一个数，排序造成了极大的时间浪费。
为了解决问题，使用二叉查找树Binary Search Tree。
2.原理
二叉查找树要满足如下性质：
1.是二叉树
2.每个节点的左子节点（如有）都比其小，右子节点（如有）比其大
此外，我们要记录每个节点的lsize——左子树的结点数，也即是数组中比它小的数的数目。（拗口）
这时候有同学提问了：教练，你这方法不严谨啊，万一是下图的情况呢？
同学不要怕，且看下一段的插入部分，构造时会避免这种情况。
话会正题。查询到某节点时，若lsize>k（比如左边有5个数，lsize=5，有五个数比它小，而k=3，我们要找的是第三小的），那就跳到左子节点。反之，跳到右子节点。如果lsize==k…恭喜你，找到啦！
3.实现
非常简单。
将第一个插入的数设为根节点（图1中的8），之后再插入时，新数小于当前节点则向左跳到左子节点，大于则跳到右子节点，直到其为空。
但，现在有了一个深层次的问题：最坏情况是怎样？
详见下集分解（AVL树）。
后续：https://blog.****.net/angrypop/article/details/82026216