#学习笔记
第6周-第13课 | 字典树 和 并查集
1. Trie树的基本实现和特性
- 字典树 Trie
- 字典树的数据结构
- 字典树的核心思想
- 字典树的基本性质
- 如果它的每一个结点的儿子只有两个，最多只有两个称为二叉树，当然还有多叉树。
- 如果看到一个层级的形式就应该想到经常会说的，按层次来打印一棵二叉树，这个题目是非常高频的题目。
- DFS深度优先搜索如果在树里面进行深度优先搜索的话，那么A走B再走C再走再走H，走完了之后回来再走I，在回来走E和J，然后再回到自己的根节点走右子树。走CF在回来走到G，这样就叫做深度优先搜索。
- BFS广度优先搜索的话，就从根节点出发犹如水波纹一样泛起的涟漪在湖上面一波，第二层就走BC，第三层就走DEFG，第四层就走HIJ，就像水波纹一样向外一波一波地扩散出去。
- 二叉搜索树
- 一讲到二叉搜索树就要想到是子树的关系，并不是儿子和父亲的关系。那么它的定义就是，任何一个结点，它的左子树的所有的结点都要小于这个根结点，它的右子树的所有的结点都要大于根节点，且对于它的任何子树同样的以此类推，对于任何子树都满足这样的特性，这个就是所谓的二叉搜索树。
- 二叉搜索树如果在题目中出来的话还要想它的另外一个特性是，二叉搜索树是一个升序的序列。
- 如果是中序遍历的话，中序是左根右，先走左子树走到底。
- 前中后序遍历忘记的话多复习几次。
- 二叉搜索树主要解决的一个问题就是查找的时候效率会更高，比如说要查找10的话怎么查找？首先和根节点比，因为10是大于根结点9的，所以左子树可以不用查找了，因为左子树所有节点都是小于根节点9的，那就一分为二，这个时候只需要找右子树了，再比13结点，10是比13小的，所以只要去左子树。10再比11，同理只去左子树，最后就找到了10这个结点。
- 还有一种情况在显示中特别常见，但是在二叉搜索树来进行存储的话，并不是特别好解决这样的一个实际问题。就是在搜索的时候，很多时候当你打了一个字母的前缀或者你中文也类似，比如说你打了一个周杰，一般人可能会觉得你是想搜周杰伦。英文的话同理。
- 像这种所谓的词频的感应，或者是由前缀来推后面的可能的词语这种形式，在现实中其实是用得非常多的。那么它应该用怎么样的数据结构来表示，就是所谓的字典树或者Trie树了，它就是因为这样的一种情形来应运而生的。
- 字典树是怎么来进行设计的
- 首先要实现这样的一种所谓的前缀感应出整个单词，这里就要改变二叉树的结点里面的存储方式。
- 不管是二叉树还是二叉搜索树，这个结点里面存的就是全部的值。这每个结点存的就是整个一个数字、一个单词、一个字符串。但是字典树最关键的点，就是每一个结点不再是存这里的单词本身，而是把这个字符串拆成单个单个的字母，每个字母存在这个结点里面去。从这一点就首先要打破之前对树的认识，就是说它的存储是相对来说比较巧妙的。
- 基本结构
- 字典树，即Trie树，又称单词查找树或键树，是一种树形结构。
- 典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
- 它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
- 怎么存的？
- 首先，结点本身它不存任何的单词，它只存它要去到下一个路径上面，这个路径代表的字符。
- 接下来每一个结点就依次进行，可以理解为常用的这些字符它的第一个字符就放在根节点上面，根据你输入的不同的字符，它就开始进行分叉。注意，Trie树不是一棵二叉树，它是一个多叉树开始分叉，根据走到的不同的地方，就开始分在不同的地方进行所谓的分流。
- 基本性质
- 结点本身不存完整的单词。
- 就是说她这个结点自己和二叉树不一样，它这个结点本身不存你要最后查找到的完整的单词。它只存你下一个字符是什么，可以去到相应的路径，所以结点本身不存完整单词。
- 从根节点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串。
- 任何一个结点，最后它代表的单词就是走过的某一条边。
- 每个结点的所有子节点路径代表的字符都不相同。
- 从根结点分散出去的每个不同的边就代表不同的字符。
- 统计频次应该怎么做？结点存储额外信息
- 在结点加一个数字，数字可以表示相应到这个结点所代表的单词，它的统计的计数就放在结点上，当然它的结点上可以存其他的额外的信息。这里的数字表示的就是这个单词出现的统计频次，而按照统计的频次，后续就可以给用户做相应的推荐。
- 结点的内部实现
- 每个结点如果是英文的话，那么它就会存到下一个结点去，指向下一个节点的不同的指针。这里它存储不再是用left和right来表示左右结点了，它直接用相应的字符来指向下一个结点。
- 如果是简单单词，同时不分大小写，可以认为是26个分叉，就是从a一直分到z。如果包含大小写或者其他的可能是更多，同时如果是整个字符串的话，它的ASCII域的话是255，所以是255个分叉。一般可以认为是多少分叉的一棵多叉树。到了最后，如果它是叶子结点，相应这个字符就指向空，表示它这里就没有儿子结点了。
- 从这里可以看出这棵树至少是一个26叉树，当然这里可以动态来分配，一开始都是0叉的，出来一个单词就分叉出去一个，那么在最坏情况下，最大可能的情况下会标称一个26叉树，所以它的空间是相对来说比较大的消耗。
- 再看单词的长度，就是它的深度，在这种情况下。一般来说它查询是很快的，因为它要查的次数就是这个单词到底有多少个字符，它就查多少次。如果单词只有两个字符，它只要走两次最后就查到了这个单词它所代表的，比如它的频次是多少。
- 那么单词的长度一般来说都不长，最多是十几个字符这么长。所以再整个字典一般来说最多也就查十多次，碰到长度为十几的这样一个单词就一直查下来。这样比去整个字典里面去查，就算排好序用二分查找的话，它的查找时间也会比用排序在用二分搜索来的快以及快不少。
- 核心思想
- Trie树的核心思想就是空间换时间。
- 利用字符串的公共前缀来降低查询时间的开销已达到可以提高效率的目的。
- 正式因为它用了公共前缀来表示这样一个路径，就可以非常天然地来解决，值输了前缀的前几个字母，它就会把所有的以这个为前缀的候选词，都给你很方便的找出来。
- 比如说输入you就在这里表示you这个东西，那么它下面的所有子树就代表了它所有的单词，可候选的单词。每个单词的频次，只要取出比如说前十天的频次然后就可以放在搜索框的推荐栏上，那么这个业务功能其实相对来说可以比较好地解决。
- 实战题目
- 实现一个Trie
- 这个代码可以有很多种，可以看题解然后来李临摹一种写法，不用自己去发明创造。
第6周-第14课 | 高级搜索
1. 剪枝的实现和特性
- 其实是前面讲的搜索内容的一个进阶，进阶的内容要求对之前的内容较熟悉。
- 剪枝
- 双向BFS
- 启发式搜索
- 都是比较烧脑或者是高阶的一些内容，一定要记得要多看几遍，然后多想想把笔记都记下来。如果对一些知识点发现理解起来特别难的话，不用话很多的时间进行所谓的死磕，更加重要的是过遍数。有时候一个知识点反复看起来不容理解，后面发现一下子就理解了。
- 朴素搜索 初级搜索
- 所谓的初级搜索就是傻搜或者暴力搜索，它主要可以优化的方向或者是怎么把它变高级，主要是两个领域。
- 优化方式：不重复（Fibonacci）、剪枝（生成括号问题）
- 第一个领域就是不重复和所谓的剪枝，这两者是相辅相成的。
- 那么不重复的剪枝可以想到就是第一Fibonacci问题，想到那个状态树。如果只是简单写一个递归程序，没有进行任何判重的话，那么它有大量的重复的结点的计算，那么时间复杂度沦为指数级的。
- 那么可以用办法就是所谓的用数组来存它的中间值，或者是在这里可以看直接用顺推的办法，就是避免重复中间重复的状态，这就是把它的重复性给去掉。
- 另外还有其他的更高价的剪枝，在生成括号问题上。也可以认为在Fibonacci的问题处理上也进行了所谓的剪枝，这都是异曲同工的。
- 所谓的剪枝就是整个状态树，这个分支是没有必要的时候，那么就把它剪掉，不进行搜索，这种没有必要性是来自一个是重复，当然也有可能是每次要找最优解，那么有一个分支是次优的或者不够优秀的，那肯定是不行的，那就把它剪掉。
- 搜索方向：DFS、BFS
- 另外一个优化的方向就是它的搜索方向上还可以进行优化，它的搜索方向主要是深度优先搜索和广度优先搜索两个方向。
- 它所谓的深度优先和广度优先，只是因为计算机数据结构里面有个所谓的先入后出的栈和先入先出的队列，导致了整个搜的时候是这两方面。但是细想的话就说广度优先可能还好一点，广度优先一般扩散到的都是距离近的，但是深度优先其实就是傻搜，或者就是一路不回头，直到撞到南墙才回头继续。那么这种并没有所谓的按照优先级或者没有任何的智能性。
- 优化的高级搜索的另外两种，一种是双向搜索，双向搜索可以理解为它从起点和重点分别做一个广度优先，然后再中间相遇，这样的话它的时间更快。另外一个就是启发式搜索，启发式搜索就不再是，用栈或者用队列这种先入先出先入后出的形式，而是用一个优先队列放在这里面。而优先队列它是按照这个结点所谓它的优先级，也就是有些结点更可能会达到我们需要的结果的话，就先把它从队列里面拿出来进行搜索，这个就叫做启发式搜索，也叫做A*算法或者叫做优先级搜索。
- Coin change （零钱置换）的状态树这张图要记在脑子里面。
- 当在做一个搜索问题的时候，这个时候一定要一下子在脑子里面会想到大概有这么一个搜索树。
- 零钱置换问题说的是你有面值为125的零钱，去凑成一个总值为11的面值，问不同的凑发有多少种。
- 它的递归树就是先用面值为1的话，剩下还需要出10这么一个子问题。当然也可以用面值为2的，它剩下的就是9。或者用5，剩下的话就是6。那么接下来递归树就是不断地向下展开了。
- 所谓的搜索问题，其实就是在它的整个状态树里面，做深度优先也好，广度优先也好，或者是优先级优先也好，最后找到我们要的比如说最优解。或者是统计它的分支个数，也就是说所谓到叶子的路径的个数，这就是所谓它的总共有多少种不同的钱币的拼法。
- 一定要记得把这种数形结合的思想给利用起来，一想到搜索问题，在脑海里面就把这个图形画出来。看到这个图形就会想到这是一个所谓的状态树的问题。
- 人生也就是所谓的这个状态树，你站在人生的一个分叉点，你可以去追这个女孩子，或者追另外一个女孩子，或者你都不追，你认真地埋头工作读书或者考研或者出国，都是一个分支，每个分支最后导致不同的所谓的平行的宇宙，这就是所谓的弦理论。
- 关于DFS和BFS，DFS代码模板-递归写法这个模板一定要滚瓜烂熟。
- DFS深度优先搜索基于递归的形式，它的模板本至上也是递归的模板。
- 如果把它换成所谓的非递归的形式怎么换？就是在这里用stack来手动模拟。
- BFS广度优先搜索代码模板，就用了所谓的队列queue的形式，这个队列就是把点这么依次加进去，然后再进行。
- 这个要是不清楚一定要再复习一下。
- 高级搜索
- 剪枝
- 所谓剪枝就是状态树，在状态树进行搜索的时候，如果发现这个分支是已经处理过的，那么我们就把它暂存在缓存里面。这整个分支就可以剪掉，不需要再手动进行计算。当然有些时候是分支不够好，所谓的叫做比较差的分治或者次优的分治也可以把它剪掉，这就是所谓的剪枝。
- 之所以有这种枝条的形态，就是因为整个状态树是一种所谓的树和枝叶的形态。
- 那么现在计算速度这么快，哪些问题状态空间还需要剪呢？
- 第一Fibonacci问题它其实状态空间就比较繁复，另外就是很不幸在人类生活世界当中具体的问题他的状态树的空间大小一般来说都是比较恐怖的。
- 国际象棋
- 人类选手卡斯帕罗夫和计算机深蓝进行对决，这个对决在90年代初那个时候名噪一时，当时话就是用普通的笔记本，用最基本的搜索再加剪枝和一些优化算法，最后就战胜了卡斯帕罗夫，当然是险胜。
- 这个棋本身就是用最朴素的搜索办法，这一仗是1996年在费城2月10号深蓝对战卡斯帕罗夫。它最后赢的棋谱，棋谱1指的是每个人走了一步，第2每个人走了两步，最后是每个人走了37步之后决出了胜局。所谓的走37步就是这个状态树的深度是37。所以就算它每一层深度的分叉就是两个分叉，那就是2的37次方也是非常大的，当然这里不止两个分叉。它的状态树空间是非常大的，正是因为深蓝进行了大量的剪枝，走的不好的位置的这分治就直接被砍掉了。
- 三子棋、五子棋等
- 一个三乘三棋牌，两个人玩，一个走O，一个走X，最后看谁是连在一起的。
- 走出来的这个状态树会发现当X走了两步的时候，至少X是不败的了。也就是说把整个状态树之前都遍历过一次的话，这时候基本上是一个不败的状态。所以关键在于这个状态树的深度能不能搞定，以及有没有什么很好的办法去剪枝。
- 扩展：复杂度非常高的围棋。
- 国际象棋每人走37步，而围棋最后走的步数是276步，而且棋盘异常的大。所以它的状态树空间比国际象棋要大不少。
- 还有一个复杂度来源就是在于它每一层的分治的个数也非常的多，原因就是说每次在国际象棋上面动的步数是相对有限的，围棋的落子只要空地都可以落上去。当然有些特别傻的位置，那么就直接剪枝点剪掉了。但是它可以落子的位置其实是没有任何明显的限制的，而且可以落子的选择性非常多。
- 正是因为这个原因，它的状态树来自于AlphaGod的文章，它的状态树树是异常的复杂，以至于用朴素简单的这种索索没法有效地处理它所谓的状态树树找到最优的情况。
- 第一它cover不了这么深的深度，另外分支太多了之后，直接又把它搜索的空间给打爆掉了。因为这个原因，直到最近的几年才是由深度学习的一种方法把它最后解决。
- 用深度学习的办法也是同样的思路，在这个状态树里面进行更加有效地评估哪个分支更好以及更加及时地剪枝出去，所以这时候会发现虽然是用了深度学习，但是它的整个思想和之前是异曲同工的。
- 科普文章：AlphaGoZero Explained，AlphaGoZero也是Google出的一个改进版的人工智能程序。AlphaGoZero这部分就解释了这个棋当时他们是怎么想的和怎么设计的，以及本身怎么解决这个问题的。DFS如果用的怎么用、以及它的这个状态树叫做蒙特卡洛树、它的估价函数，就是分支到底是好还是坏怎么判断等。
- 回溯法
- 其实回溯本身没有和递归有太多本质上的区别，只不过它是采用一种是错的思想，尝试分步去解决一个问题，这里其实它就是所谓的分治。分治再加所谓的试错，在分步解决问题的过程中，当它尝试发现现有的分步答案不能得到有效的结果的时候，它就会取消上一步或者上几步的计算，在通过其他的可能的分步解答，再次去尝试寻找问题的答案。
- 这个人类其实经常用，就是在下象棋的时候就会想下这步是否可行，再算对方可能怎么下，可能多算三四步，最后发现我这步棋可能是个臭棋，然后在想那不能走这步了，要走其他步。
- 在做问题决策的时候也会是这样，假设今天想去玩会干嘛，然后不玩会干嘛，在其他地方会干嘛，就在脑子里面去不断地试，试完之后找一个最优解出来，其实和人类很像。
- 但是这里更加重要的是机器和人类的区别或者是擅长点是什么？
- 人脑的第一个问题，就是它回溯的深度不够，因为它的短期记忆的话比较模糊，或者是说短期记忆记不准，经常回溯了一两层之后就不太会记得。
- 第二人类比较懒，当多回溯了几步之后特别累就直接不再想了。
- 机器就擅长第一做重复的递归特别快，它的记忆能力肯定是无敌的。因为这个原因，所以机器在做回溯，特别是这种有重复性的回溯就很厉害。
- 正是因为这个原因才会搞出这种递归式的搜索以及所谓的这种回溯法。
- 回溯本身的定义，定义没有什么巧，关键是后面具体做题的时候可以再次理解整个回溯的思想。其实它本身的话就是一种递归和分治，只是它要不断地进行是错的环节。
第6周-第15课 | 红黑树和AVL树
1. AVL树和红黑树的实现和特性
- 树Tree
- 二叉树Binary Tree
- 二叉树遍历（前中后序）
- 前序（Pre-order）:根-左-右
- 中序（In-order）:左-根-右
- 后序（Post-order）:左-右-根
- 如果一棵树是二叉搜索树，那么它的中序就是有序的。
- 树和链表没有本质上的区别，当一个链表分出两个next的话就把它称为树，所以它的数据结构的一个本质就是从一维空间扩散到二维空间。这种扩散的好处就是引入了二叉搜索树。当它本身是有序的话，那么每一次就可以根据它和当前结点的大小的关系分区分它只走左分治还是只走右分支，这样查询、插入和搜索的效率就是从O(n)的变成了log2n的时间复杂度。
- 二叉搜索树怎么插入的、怎么查找的、还有怎么删除的，删除不要求完全掌握，但是面试之前一定要看一下。
- 二叉搜索树如何查找？首先将要查找的值和根结点进行比较，如果小于根结点，就只要去左子树查找就行。它的查找的时间复杂度就是这个树的深度。如果这个树有n层的话，那么它的时间复杂度就是n。但是一般定义为n为树的总的结点个数，这个时候它的时间复杂度平均来说就是log2n的，这里的n表示树链总的结点个数。
- 极端情况
- 在维护二叉搜索树的时候没有特殊处理，在极端情况下它会变成一根棍子，这根棍子的话就是在插入的时候始终插在左边，当这根根子出现的时候，二叉搜索树就退化成一个链表，似于链表的查询的时间复杂度。
- 保证性能的关键
- 保证二维的维度->左右子树结点高度尽量是平衡（recursively），且左右子树以此类推下去都尽量是平衡的。
- Balanced，所以引入了一个叫平衡二叉树的一个概念。
- 平衡二叉树有很多种，在面试时候一般喜欢给大家出AVL和红黑树，以及treap以及splay伸展树，还有B+树（主要在数据库的索引结构里面用的很多）、二三树。面试的时候喜欢出这些，但是它整个平衡二叉树有很多。
- 如何保证一棵树的平衡？
- 想象成整个棍子直接从中间开始把它打折了。
- 相应的每个左右子树也类似地这么做下去。
- 这样就是可以让最后的整个树变得平衡，但是一般来说不会等到在真正的自平衡二叉树里面。一般不会等到这个树已经变成很极端的这根棍子的时候再去平衡，而是在每一步进行插入或删除操作的时候都去判断它是否平衡，以及将它维护成平衡二叉树的状态。
- AVL树
- 发明者G.M.Adelson-Velsky 和 Evgenii Landis
- Balance Factor （平衡因子）：是它的左子树的高度减去它的右子树的高度（有时相反）
- balance factor = {-1, 0 ,1}，取值范围只有-1，0，1这三种。就是它左子树的高度减去它右子树的高度，注意这里是高度，并不是左子树的结点树或者是右子树的结点树，只是它的高度。为什么呢？因为查询二叉搜索树查询效率只与高度有关，和它结点的个数是没有关系的。
- 通过旋转操作来进行平衡（四种）
- 记录左右子树高度
- 平衡因子 = 右边这个高度树的高度 - 左边高度树的高度
- 所有叶子结点，因为它左右子树没有，所以它的高度就是0。
- 平衡因子值在-1，0，1之间的是一个严格意义上的平衡的AVL树。所以保持平衡因子不超过绝对值1，就变成了一棵二叉搜索树开始最直观也最自然的一种维护方式。这就是为什么最开始最经典的树AVL就是要这么去做，它始终保证任何一个结点它的平衡因子都只在-1，0，1 ，这样的话就可以维护它效率。
- 假设要插入一个结点要怎么插？当插进来之后平衡因子全部都要调整。
- 当有结点它的平衡因子不再是1的范围了，就幸会进行一种旋转的操作。
- 旋转操作总共分为四种基础的旋转操作。
- 左旋
- 右旋
- 左右旋
- 右左旋
- 后面这两种是前面这两个的搭配起来就变成后两个，其实本质上就是一个左旋和右旋，但是有些数字结构需要旋两次，就变成左右旋和右左旋。
- 子树形态：
- 右右子树->左旋
- 如果局部的子树形态是一个结点，单一的右子树且单一的右子树，叫做右右子树，叫做这边有一个仅有一个右结点，且仅有一个右结点右右子树的情况，那么它的平衡因子就是0，1，2。这种情况下就是一次简单的左旋转操作。怎么左旋？就是把这个数领起来往左旋一下。这种是最简单最基础的一种情形，所用的旋转操作也是比较简单的一次左旋即可完成问题。
- 左左子树->右旋
- 左左子树的情况同理可得，右旋一次就行了。
- 左右子树->左右旋
- 就是它是先左子树再右子树。基于这种先左子树右子树的情况就叫做左右子树型，就要左右旋。如何左右旋？首先这个结点左旋一次，首先C是大于B的，但是C又是小于A的，所以左旋的话，B就拉下来C就顶上去，这样的话它还是一个复合二叉树性质的，就变成了左左子树的情况，就再加上一次右旋就行了，所以它总共叫做左右旋。
- 右子树->右左旋
- 先是一次右旋，C小于B，所以把它右旋上去变成右右子树的情况，再接下来进行一次大型的左旋。
- 这四种情况一定要滚瓜烂熟，相对来说是比较对称的，也比较自然能够理解的。它整个因为树的查找性能就在乎它的深度，那么就记录他左右子树深度就行，同时保证任何时候任何一个结点，它的左右子树的深度差不超过绝对值1。然后基于当它不平衡的时候，其实它的基础的情况就是以上四种。
- 带有子树的旋转
- 结点本身有所谓的子树情况进行左右旋转和右左旋转该怎么办？
- 右旋操作：注意下面子树是大于结点的，但是又小于根节点的，所以当结点挪上来，根节点挪下去，进行一个右旋操作的时候，这个子树不能在贴在结点上面了，必须挂在根节点的左子树上面。左旋操作同理。如果带有子树的情况下，它的左旋和右旋相应的夹在中间的子树就要换一个父亲节点了。
- 它的整个旋转和观察树的形态本身相对来说是比较繁琐的，但恰是代码来说的话是相对来说比较对称的。本身的代码量的确是比起普通二叉搜索树要大，或者说是大一截。
- 但是它整个情况就是这四种，所以在面试的时候把它这四种情况都给面试官在列表列清楚，那么对AVL整个的思路是完成掌握的。
- 当然也要解释为什么会出来AVL以及这个平衡因子是怎么定的。平衡因子定的由来就是因为它的查询的时间复杂度是等于树的深度的，所以的话它就会记录深度差，就得到平衡因子。
- 平衡因子不平衡的时候要怎么办？去旋转操作就会变成四种基础的旋转，然后树的形态本身带有子树的情况下就按照四种图来，这样的话就会掌握整个AVL。
- 关于代码怎么写，其实不要求，面试的时候没有人写的出来，面试官他自己可能也写不出来的。正式这个原因的话，可以不用去看代码。
- 如果个人觉得好奇或者对自己要求比较高的话，可以去网上找到相关语言自己实现去看一下。但是对于学习算法和掌握面试本身的话，通过这个图而且自己完全理解就够了，这样比较轻松而且实用很多。
- AVL总结
- AVL它是一个平衡的二叉搜索树，而且是自平衡的。
- 每个结点会存一个平衡因子balance factor = {-1 , 0，1}。
- 同时有四种旋转操作。
- 不足：也就是为什么会引入其他的平衡二叉树。
- 结点需要存额外的信息，而且存储的信息回事一个int型的，也就是说至少会要三个值来表示，或者是因为它有时候会要加减乘除，所以会是一个int型
- 且调整次数频繁，也就是稍微动它一个结点或者两个结点，有时候就要出发一次平衡，正式因为这样，它调整的有点多，导致这个树的维护成本偏高。
- 调整的频繁次数高是一件好事吗？其实不是这样子的，有些时候的话其实并不要求它高度差-1或者是1，超过-1或者说2和-2的话就要调。因为有些时候可能会认为-1和-2还能够接受，那么就调的少一点，因为调那些结点本身也要费操作的。
- 正是这个原因就会引入其他的一些树，这些树就叫做近似平衡二叉树。所谓叫近似平衡二叉树就是不需要每次非常严格地来平衡。
- 这种情况下就叫做所谓的近似平衡二叉树，它整个都是一些取舍叫tradeoff。当觉得另外一种好的话，它可能在其他地方有这种conpronise，就是有所妥协的意思。
- 红黑树 Red-black Tree
- 红黑树本身和有一些树都是类似的性能，就是所谓的近似平衡二叉树。为什么近似？并不没是每天或者每分钟都收拾桌子那么就一定是最高效的，这样的一个过程趋势。
- 红黑树是一种近似平衡的二叉搜索树（Binary Search Tree）
- 它能够确保任何一个结点的左右子树的高度差小于两倍。小于两倍指的是它的左子树的高度差如果是1的话，右子树的话可以是2，那么左子树的高度是5的话，那么右子树其实可以是10或者是2.5。反正它的高度差就是大的最多是小的两倍。所以它一下就变得宽度更广了，这样导致的一个好处就是说维护的它旋转的频次降低，这样的话很多时候会觉得来维护二叉树话的时间更少，它的总体性能更好。
- 具体来说，红黑树是满足如下条件的二叉搜索树：
- 每个结点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶结点（NIL结点，空结点）是黑色的。
- *不能有相邻接的两个红色结点。
- *从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。（任何一个结点，到每一个叶子的所有的路径，都包含相同数目的黑色结点。）
- 通过最后这两点关系，最后就可以证明它的高度差是小于两倍的，所以最关键就是它高度差要小于两倍。
- 所谓红黑树，空节点在最下面，红色的结点不相邻，然后任何一个节点到每个叶子结点走过的路径都包含相同数目的黑色结点。这个性质就可以证明在这种近似平衡的状态下，它的时间复杂度还是平均来说很好的logn时间复杂度，它不会进行所谓的退化，而它所需要的调整时间也是折中了之后相对比较小的调整时间。
- 关键性质：从根结点到叶子结点最长的可能路径，不多于最短的可能路径的两倍长，正式因为它有这个关系，所以会发现通过这五个性质就可以保证这一点。所以就只需要掌握这里就可以了，只需要记住这五点就行了。这五点能记住相当于初级地掌握了红黑树。同时还要记住它是所谓的一个近似平衡的，关于它的插入操作和删除操作这个相对来说比较复杂些，而且有所谓的相应的旋转。记住关键性质即可。
- 在面试里面问的最多的概述和比较
- AVL树提供了更快的查询（faster lookups），而比红黑树来说的话AVL优秀的地方是更快的查询。因为它是更加严格平衡的，也就是说从读或者是查找性能来说AVL更好。
- 红黑树提供了更快的插入和删除的操作，因为AVL的旋转操作会更多，那么红黑树会更少一点，因为红黑树只是一个近似平衡树。所以添加和删除整个操作，我们认为红黑树更快。
- AVL要存的额外的信息，要存factor和height更多一点，它需要用更多的内存，附加在每个结点里面来存这些额外的信息。而红黑树要的信息非常的少，它只要一个bit就是来存0和1表示的黑或者是红，所以它对额外空间的消耗更小。
- 就是一个int怕什么？树有时候可能也会有上万个结点，或者是它本身性能要有差别的话，结点个数肯定是很多的情况下。如果是结点数很少的情况下，比如一万以内，随便怎么用树都可以，稍微不平衡或者不平衡多一点其实差异不大的。那真正要追的话而且这诶很多都是在数据库和数据仓库里面使用，所以就在于那个数据至少是百万和十万以上的时候，这个时候它每个结点都增加一个int的话，其实并不是一个最佳的选择。而且在这里的话你只要一个bit会更好。
- 比较设么时候用红黑树，根据前面三点的话应该可以看到。
- 如果在读操作非常多，写操作很少的时候就用AVL就好了。AVL的问题就是插入删除调整得比较频繁，但是好处是非常平衡，所以查询很快。
- 如果插入操作比较多的话，或者插入操作和查询操作一半一半的话，一般来说是用红黑树。因为红黑树比较简洁比较好实现。
- 那么一般来说红黑树是用在常常写的一些高级语言的库里面，比如写Java或者写C++的那些map，set的话全部用的是红黑树。
- 而在DB里面的话，一般来说DB读会比较多，写会比较少，比如天天刷微博，或者天天看朋友圈，那是读的多还是写的多，除非是超级几个大V，一般来说肯定是读的多，这样Database里面一般是用AVL。
- 以上这些记住的话，一般来说对面试就是问题不大了。