前言：
本文内容均来自b站up主【蓝不过海】数据结构讲解视频中总结整理的文字版，用于自己复习使用，大家有不理解的可以看原视频，讲的非常清楚。
数据结构——查找系列
二叉搜索树BST
引言：
当我们用有序数组保存数据的时候，采用折半查找能以O(logn)效率高效查找数据，但是当想要插入/删除元素时，需要将后面元素全部往后/前挪，使得插入和删除效率变为O(n)。故引出二叉搜索树BST，这种数据结构保存数据可以均已O(logn)的效率高效的维护查找，插入，删除三个操作。注意：如果数据本身有序，那么效率会退化成O(n)。
-
概念
对于任一子树，所有的左子树都小于根，所有右子树都大于根
-
查找
从根节点依次比较，待查找元素比当前节点元素小，向左子树继续找，比当前节点大，向右子树继续找
-
插入
插入其实就是查找的过程，依次向下搜寻，找到 要插入的元素刚好比树中的某一元素大/小，且这个元素下有空位置，直接放入
-
删除
没有孩子——>直接删除
只有左子树/右子树——>直接代替
左右子树都有——>直接后继（或前驱）代替值，然后删除（转换成前两种情况）
平衡二叉树AVL
引言：
如果数据本身有序，对于二叉搜索树效率会退化成O(n)，如何避免这种情况？——> 引出平衡二叉树AVL
-
概念
AVL树首先是一棵二叉搜索树(前提)。在此基础上，保证所有的节点的（左子树高度 — 右子树高度）的绝对值 <= 1，以保证树的均衡，不会出现一边倒的情况。其中左子树与右子树高度的差值又叫平衡因子，其取值只有为0 1 -1时才算做平衡。当发生失衡时，AVL可以通过一系列的旋转操作进行调整。
注意：AVL树在 查找、插入、构建、删除的过程和BST一致，只是在失衡的时候需要调整。
-
性质
任一节点左右子树的高度相差绝对值不超过1
-
调整策略
-
左旋
节点5直接转下去会和6冲突，则让冲突的6变为5的左孩子（简记：冲突的左孩变右孩） -
右旋
与左旋同理
-
四种失衡情况与对应调整策略
-
注意：如果插入节点后导致多个祖先节点失衡，只需调整距离插入节点最近的失衡节点，其他失衡节点会自然平衡 删除节点后则需要依次对每个祖先检查并调整
红黑树RBT
引言：与AVL树一样，都是对二叉搜索树的优化
-
概念
RBT首先是一棵二叉搜索树(前提，即所有左子树都小于根，所有右子树都大于根)。在此基础上，为每个节点引入红、黑两种颜色标记，其中根节点和叶子节（指的是NULL节点）点必须是黑色，同时所有红色节点左右孩子必须都是黑色（即从上到下不能出现两个连续的红色节点），最后还要满足从任一节点到它叶子接待你所有路径种黑节点数量相同。
-
性质
最长路径不超过最短路径的两倍（任一节点左右子树的高度相差不超过两倍）
注意：由于AVL树在平衡上比红黑树做的更好（左右高差不超过1，代价是更频繁地的旋转调整导致插入删除效率变低）所以红黑树的查询效率要略低于AVL树，但时间复杂度都是O(logn)，、。总而言之：AVL树查询更高效，红黑树插入和删除更高效！
-
插入操作
-
删除操作
红黑树的删除首先需按照二叉搜索树的方法将节点进行删除，如果删除的节点左右子树都有，那最终也会通过直接前驱或直接后继的替换转换为只有左子树或只有右子树的节点，或者是删除没有孩子的节点这两种大情况。
对于情况1：
如果删除的节点是只有左右一边子树的节点，对于红黑树来说只可能存在如下图左的两种情况（也可以看作只有左孩子/右孩子的情况），此情况可直接让删除节点的孩子代替删除点，然后变黑即可
对于情况2：
如果删除的节点是没有孩子的红节点——>删出后无需任何调整
如果删除的节点是没有孩子的黑节点，那么这个节点删出后就看作是一个双黑节点，然后通过调整，将该双黑变成单黑(NULL)。
具体调整要看双黑的兄弟节点：
如果双黑的兄弟是黑色：且黑兄至少有一个红孩，则需要判断符合哪个形态（LL,RR,LR,RL）然后再做相应的变色和旋转（变色方式如下图，旋转和之前AVL一样，不过要注意是对p旋转，也就是对父节点旋转）。如果是黑兄全黑孩，则兄变红，让双黑上移，如果遇到红节点或根节点，就直接边单黑，调整结束。否则需要继续修复上移后的双黑节点。
如果双黑的兄弟是红色：那么就先对兄父进行变色，然后让父节点朝向双黑节点旋转即可，旋转后继续保持双黑节点然后根据新的兄弟节点的情况去做进一步调整。
总之：只有黑兄至少有一个红孩这种情况，调整完双黑变成单黑，或双黑遇到了红节点或根节点直接变成了单黑，其他情况都需要继续对双黑进行修复调整！
嗯，就先整理到这吧 学不动了
查找系列后面还有B树、B+树、散列表什么的后续再继续整理。
