预热姿势: 什么是二叉查找树 (二叉排序树)
有一个根节点，每一个节点的左边的子节点都比根节点小。右边的自然是都比根节点大。
1.红黑树
规则:
1.节点只能是红色或者黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点。(nil 没有值)
4.每个红色节点的下面两个子节点都是黑色。(不能有两个连续的红色节点)
5.从任一个节点，到其每个叶子的路径包含相同数目的黑色节点。
插入删除节点时的方法:
1. 变色：尝试红色变成黑色，黑色变成红色。已满足规则即可。
2. 左旋转：逆时针旋转红黑树的两个节点，父节点被右孩子取代。从而变成左孩子。
3. 右旋转：顺时针旋转红黑树的两个节点，父节点被左孩子取代。从而变成右孩子。
2. B-树 (也叫B树 Balance Tree，不叫B减数)
减少查找次数，把树变成矮胖的样子。(根节点中的元素值，是所有子节点的分界值)
B树的插入和删除比较复杂，一个元素删除(插入到节点)，需要满足下面的所有特征。
特征:
1.每个节点包含最多M个孩子。M成为B树的阶。 (假设现在是一个M阶的B树)
2.根节点至少有两个字节点。
3.每一个中间的节点都包含K-1个元素 和 K个孩子。(m/2 <= K <= m)
4.每一个叶子节点都包含K-1个元素。(m/2 <= K <= m)
5.每个叶子节点，都在同一层。
6.每个节点中的元素，从小到大排列。节点中K-1个元素正好是K个孩子包含的元素的值域分划。
3. B+树
B-树的变体，查询性能更高。
1.单一节点存储更多元素，查询IO次数更少。
2.每次查询都得查找到叶子节点，性能稳定。
3.所有叶子节点形成有序链表，便于范围性的查询。
特征:
1.中间节点有K个子树，就包含K个元素。且每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有叶子节点中包含了全部元素的信息，和指向含这些元素记录的指针。
且所有叶子节点按关键字大小，自小到大顺序链接。
叶子节点相邻之间有指针链接。(一个有序链表)
3.所有中间节点元素都同时存在于子节点。在子节点中是最大(最小)元素
4. Bitmap (位图算法)
指内存中连续的二进制位 bit,用于对大量的整型数据 做去重和查询。
吧一个唯一的整型ID，存放到二进制的字段里面。
每一位代表一个ID，ID累加。 (即index表示ID) 达到充分利用内存空间的目的。
这样一个字段表示一个Bitmap，不同的字段，只需做并运算，就可以查出需要的ID。
缺点
因为不知道总共有多少数据，只知道一个Bitmap(标签)所包含的数据。
所以不能做非运算， 如查询不是20岁的所有用户。
可以增加一个全量的Bitmap，这样就可以做非运算了。
5. A*寻路算法
引入的概念：
OpenList：存储可到达的位置。
CloseList：存储已到达的位置。
公式：F=G+H (G表示从起点到当前位置的距离，H表示当前位置到目标位置的距离)
F表示综合评估，尽量选择值小的。
算法
从起始位置开始，每一步都计算出所有的可用位置 和 这些位置的F值。
取最小的值，作为下一个位置。然后依次，一步一步算到终点。即得出最优路径。
网友评论