查找

3.1 符号表

字典的实现，内部数组保留key+value两个数组index一致，然后通过二分法找key，然后再根据key的index找到value。 但是为了查找方便，要有序插入，就导致插入特别费事，需要排序+异位。 所以需要使用更高效的办法：二叉查找树

3.2 二叉查找树

二叉查找树，每个节点存储key+value，左节点小于父节点，父节点小于右节点。 这样，既方便查询，也方便插入删除。空间换时间。

3.2.3 有序性相关的方法与删除操作

找最大值:一直找到最右节点即可 找最小值:一直找到最左节点即可 删除最大值/最小值:

1. 最大/最小节点没有子节点，则直接去掉链接它的链接即可
2. 如果最大值/最小值有子节点
   1. 如果只有单个子节点，则直接替换即可
   2. 如果有两个子节点，则需要找到该节点的右节点的最小子节点，然后将子节点与要删除的节点相互替换，并删除要删除的即可

查找: 因为二叉树是有序的，左子树小于节点，节点小于右字数，如此递归排序即可，然后按范围查找

3.3 平衡查找树

二叉查找树，再查找时，左右节点分配可能极度不均衡，导致查找费时。 所以，这里有了平衡查找树：主要区别是，平衡查找树一个节点可以有多个值，并且有多条子节点，然后也是按大小进行排列，然后确保最底部的子节点跟根节点的距离都应该是相同地。

3.3.1 2-3查找树

允许一个节点包含2个值，子节点可以有3个。最左边的子节点小于节点的值，中间的子节点在节点的两个值中间，右边子节点大于节点的值。 这里，插入的时候要保持整个树的左右平衡。 所以显示找到合适的位置插入，如果这个点已经是当前只有1个值，则直接插入到这个点即可，如果是2个值，则将这个点临时改为3个点，然后再将中间数上升到父级节点，然后将子节点拆为两个子节点

插入可参考：

3.3.2 红黑二叉查找树

红黑树，就是将2-3查找树进行拆分，拆成我们正常看到的二叉查找树 ，但是拆分过程中，我们需要将其左链接当成一条红线。

插入:插入总是用红链接来和它的父节点相连接。如果父节点的子节点为空且小于父节点，则直接连接左节点。如果大于父节点，则跟父节点置换，并将父节点作为该节点的红链接链接的点。如果发现左右都是红链接则同时变为黑链接并将其父节点转为黑节点，如果右连续红链接，则将父节点上升，将这三个点转为新的二叉树

根节点总是黑色

删除:主要包含两步，1.删除：如果没有子节点，删除即可，如果只有一个子节点，则删除后子节点上移。如果有左右两个子节点，则根据中序遍历的规则，取其左子节点的最小子孙节点。 2.平衡，因为红黑二叉树的特征(平衡，对每个节点, 从该节点到其子孙节点的所有路径上包含相同数目的黑节点)，如果我们删除的是红节点，则啥事没有，如果删除的是黑节点，则会破坏该平衡，需要进行平衡调整【1.如果删除节点的父节点是红色的，则将父节点节点变黑即可 2.如果父节点是黑有其他子节点单但子节点下面没用红的，则将兄弟节点变红 3.如果父节点是黑然后兄弟节的子节点有红色，则把红色节点向上提，并同时要保存二叉树特性(移动相应的其他节点以保存)】 红黑树原理介绍

3.4 散列表

将数据转化为数组，key转化为数组的index 重点：散列有个主要的问题就是处理碰撞，当两个key转化后的index是一样的时候，就要进行处理。 碰撞处理：

1. 拉链法：散列表里面存的每一项都是个链表，然后链表里面存了具体的key。再查找的时候，我们可以拿到链表，然后去遍历
2. 线性侦测：将散列保存在一个大数组中，然后发现数组中对应的index已经保存过其他key了，就在数组后面第一个nil处放入对应的key的值。然后还有一个数组来记录每个index处保存的具体key。

3.5 应用

--EOF--

若无特别说明，本站文章均为原创，转载请保留链接，谢谢