本文目录一览：
python的字典怎么扩展成C呢？拿什么数据结构接收？100分 详细进来~
1、直接用PyObject。上策
2、转换成C++ STL的Map容器是直接对应的。中策
3、使用的是数据，而不是结构，只要能让中间的数据发挥作用，就没必要一样的结构，也就是转换成具体适合你那接下来C中应用的结构。比如只用到某几个键和某几个值。如果C中根本不应用，就回到1。中策
4、自己在C中实现这种字典。建立散列表或者红黑树表。或者最简单的两个一维数组，实现key[],value[]的一一对应。下策
红黑树(Red-black tree)
树 是一种 抽象数据类型 ，或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的 数据集合 。
红黑树 是一种自平衡二叉查找树，典型的用途是实现 关联数组 ，它是复杂的，但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的 O(log n ) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。
一个由n个节点随机构成的二叉查找树的高度为(log n ).证明如下：
而时间复杂度是以某个基础数据操作的重复次数作为量度。红黑树的是二叉搜索树，左子树上所有节点的值均小于他的根节点的值，右子树上所有节点均大于根节点的值，左右子节树相对根节点按大小分布。如果把每次节点值的比较看成基础数据操作，那么最差的查找情况是一直查找到高度最大的根节点，那么查找的时间复杂度即与高度成正比，可表示成 O(log n ) 。
简单了解了红黑树的字面定义，下面动手感受下红黑树的相关操作。当你插入或者删除一个节点时，可能会破坏红黑树的性质，所以需要对树节点进行重新着色或者旋转，来保持红黑树的结构。首先看下二叉树的旋转。
假设pivot节点不为空，其右子树不为空，那么左旋即是：使pivot的右孩子Y为子树的根，pivot节点为子树根节点的左孩子，pivot左孩子、Y节点的右孩子不改变，Y节点左孩子变为pivot节点右孩子。
假设pivot节点不为空，其左子树不为空，那么右旋：使pivot的左孩子Y为子树的根，pivot节点为子树根节点的右孩子，pivot的右孩子、Y节点的左孩子不变，Y节点的右孩子变为pivot节点的左孩子。
实战演练之增加、删除节点时，如何保证红黑树的性质不被破坏。
往一个空的红黑树中，依次插入数据：12 1 9 2 0 11 7 19 4
节点为根节点，所以为黑色，两个null节点为黑色节点。
按照二叉搜索树的逻辑，9小于12、大于1，应该是1节点的右孩子。但，新增的两个NIL节点已经使得12，1，9，NI这条路径的黑色节点至少为两个，而12，NIL这条路径的黑色节点只有两个。所以要对1节点进行左旋，9节点变为12节点的左孩子，发现问题还是存在。继续，对12节点进行右旋，9节点为根节点，1、12分别为9节点的左右孩子。尝试着色，9节点必须为黑色，而1，12节点可以为红色，也可以为黑色。
0节点直接作为1节点的左孩子，保持跟2节点相同的颜色即可。左右子树依旧保持平衡。
从二叉查找树的性质看，7节点作为2节点的右孩子即可。这时来分析着色问题，我们先看最短路径的黑色分布，9，12，NIL这条路径，有三个黑色节点，以此为参考，尝试改变9节点左子树的着色。目前最长的路径是9，1，2，7，NIL这条路径。保持三个黑色节点的话，9跟NIL已经为黑色节点，而红色节点又不能挨着，所以只能是1为红色节点，2为黑色节点，7为红色节点。那么9，1，0，NIIL这条路径，0就要为黑色节点。调整完毕。
19节点作为12节点的右孩子，与左孩子保持一样的红色即可。
4节点应该作为7节点的左子树，无论着什么颜色，以1节点为根节点的子树，都要破坏红黑性质。所以应该进行旋转。先以7为根节点进行一次右旋，再以2为根节点进行一次左旋。尝试着色即可。
类似插入节点的分析、总结，删除节点也可以针对每种场景找到固定的着色方法，就像玩一个游戏，有自己的推理跟玩法。我先做个PPT，这块稍后补充。
所有的插入、删除都是有限个情况，基于插入、删除的情况分析，即可编写算法生成红黑树，使其在固定的业务场景中发挥红黑树稳定操作效率的特色了。
在 计算机科学 中， AVL树 是最先发明的 自平衡二叉查找树 。在AVL树中任何节点的两个 子树 的高度最大差别为一，所以它也被称为 高度平衡树 。查找、插入和删除在平均和最坏情况下都是 O （log n ）。增加和删除可能需要通过一次或多次 树旋转 来重新平衡这个树。
节点的 平衡因子 是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
不提问题的码农不是好程序员。自己写完了红黑树的简单剖析，感觉还是只懂皮毛，没有从触碰到算法的核心内容。所以，不妨留几个小问题，担心自己脑子生锈或者没事想玩手机的时候，再提笔研究下红黑树。
教你初步了解红黑树
算法的时间复杂度和空间复杂度-总结
红黑树从头至尾插入和删除
AVL树
红黑树C源码实现与剖析
Echo
8 Nov，2016
红黑树详解
首先，我们来了解一下二叉查找树,二叉查找树具备以下几个特点：
1、左子树上所有节点的值均小于或等于它的根节点的值；
2、右子树上所有节点的值均大于或等于它的根节点的值；
3、左右子树也分别为二叉排序树。
下面我们以一棵典型的二叉查找树来查找值为10的节点：
以上图例正是典型的二分查找的思想，查找所需的最大次数等同于二叉查找树的高度。在往树中插入新节点的时候也要用类似的方法，通过一层一层地比较大小从而找到新节点适合插入的位置。但是即便如此，二叉查找树依旧存在它的缺陷，并且此缺陷恰恰体现在插入新节点的时候。请看下面图例展示：
这样的瘸腿形态虽然也符合二叉查找树的特性，但是查找的性能却大打折扣，几乎变成了线性数据结构。为了解决二叉查找树多次插入新节点而导致的不平衡问题，红黑树便应运而生了。
红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的特性外，还具有下列性质：
1、根节点是黑色，节点是红色或黑色；
2、每个叶子节点都是黑的空节点；（nil节点）
3、每个红色节点的两个子节点都是黑色；（也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点）
4、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些规则的限制，保证了红黑树的平衡，红黑树从根到叶子的最长路径不会超过最短路径的两倍。当红黑树插入或者删除节点的时候，红黑树的规则可能被打破，这时候就需要做出调整来维持它的平衡了。请看下面的例子（注意：新插入的节点必须是红色，否则就没有意义了）：
由于父节点22是也是红色节点，因此打破了红黑树的规则（每个红黑树的两个子节点都是黑色），所以必须进行调整，使之重新符合规则。那么我们需要作出怎样的调整才能保证一棵红黑树始终是符合规则的标准红黑树呢？调整有两种方法：“变色”和“旋转”，其中，旋转又分为两种形式：“左旋转”和“右旋转”。
为了重新符合红黑树的规则，尝试把红色节点变成黑色，或者把黑色节点变成红色。
下图是摘自上面红黑树的一部分，节点25并非根节点。正如上面所说因为新节点21和节点22连续出现了红色，不符合规则，所以把节点22从红色变成黑色。
但这样并不算完，节点22变成黑色后，凭空多出的黑色节点又打破了规则，发生连锁反应，需要继续把节点25从黑色变为红色。
此时仍未结束，节点25变为红色后，又和节点27形成了两个连续的红色，规则又被打破，需要继续把节点27从红色变为黑色。
如此一路走下来，完成变色调整。
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为左孩子。
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为右孩子。
这几种方法究竟怎么使用呢？红黑树的插入和删除包含很多种情况，每种情况都有不同的处理方式，下面举一个典型的例子，可以体会一下这个过程。
还以刚才插入节点21为例：
首先我们变色处理，把节点25及其下方的节点变色：
此时节点17和节点25是连续的两个红色节点，那么此时再把节点17变成黑色节点可以吗？显然是不可以的，这样依然不符合规则，更不可以把根节点13变成红色。
既然变色已经无法解决问题，我们此时就要使用旋转了，我们把节点13看作X，把节点17看作Y，进行左旋转：
旋转完成后，由于根节点必须是黑色，所以还需要进行变色：
至此并没有结束，因为其中两条路径（17-8-6-NIL）的黑色节点数是4，其他路径的黑色节点数是3，依旧不符合规则。这时我们需要把节点13看成X，节点8看成Y，做右旋转：
然后再进行变色：
经过上面一系列的调整，我们的红黑树终于变得重新符合规则，整个过程有点复杂，经历了：变色--左旋转--变色--右旋转--变色这样的一系列步骤。
经过上面细致的步骤演示，想必大家对二叉查找树和红黑树有所了解了吧，对红黑树结构插入新节点所触发的一系列的变化流程也有了大概印象。实际中红黑树的应用是很多的，比如JDK（Java开发工具包）的集合类TreeMap和TreeSet底层就是红黑树实现的，在Java8中，HashMap也用到了红黑树。其实关于红黑树自平衡的调整，插入和删除节点时涉及到的情形一一展开讲解还是很多很多的，但是万变不离其中，红黑树自平衡调整的主体思想都是上面所叙述的，大家有兴趣可以再进行深入的探究。
红黑树——一个自平衡的二叉搜索树
普通的二叉搜索树在最坏的情况下，可能退化成一个链表。而又因为二叉搜索树的所有操作的性能（添加，删除，查找等），与二叉搜索树的高度有关。在最坏的情况下，二叉搜索树的高度和元素个数相同，此时二叉搜索树的效率降为了O(n)级别。
所以为了防止我们的二叉搜索树退化成一个链表，就产生了 平衡二叉树 。 平衡二叉树 可以保证它的左右两个子树的高度差不会超过1。平衡二叉树有很多实现，一个经典实现就是 红黑树 。
在红黑树中将树中的节点划分为两种状态，分别用黑色和红色来表示。
红黑树为了保证自己能够平衡子树，所以制订以下五个规则：
1、每个节点必须有颜色，要么黑色，要么红色，没有别的颜色。
2、根节点必须是黑色
3、所有的空节点(nil节点)都认为是黑色节点。
4、红色的节点不能连续，即一个红色的节点，它的父节点和子节点不能也是红色的，
5、无论从哪一个节点起始，到它每个叶子节点的路径中，黑色节点数量必须相同。
在对红黑树进行添加、删除等操作之后，必须使红黑树符合这5个规则。
那么问题来了，在添加删除操作之后，树中节点的数量都变了，是怎么保证整个树满足上述这些规则呢？
这里涉及到3种操作， 变色 、 左旋 和 右旋 。通过这个三种操作，在增删节点之后调整树的形状结构，使它满足上述5个规则。这也是红黑树能保持平衡的原因。
变色操作 我们在下文的添加、删除节点的实际操作中，再进行在描述。
先来说一下左右旋。
文字描述一下就是，2的右孩子节点4，变为了2的父节点，2由父节点变为4的左孩子。同时，4原来的左孩子变为2的右孩子。
右旋与左旋相反，即以某节点为支点进行顺时针旋转。同样，我们看下图，是以5为支点进行的右旋:
文字描述同样反过来，5的左孩子节点3，变为5的父节点，5由父节点变为3的右孩子。3原来的右孩子变为5的左孩子。
首先是在树中找到新节点正确的位置，寻找位置的过程与普通的二叉搜索树相同，只是将新插入的节点默认为 红色节点 。为什么默认为红色？因为如果你将新节点默认为黑色，则插入后肯定会打破原本符合规则的红黑树（上述第5条规则）。但是，如果你将新节点定为红色，则有可能不用任何操作就符合红黑树规则，如下图，当新插入的红色节点，它的父亲节点为黑色时候，此时已经满足红黑树规则了。所以用红色比黑色好。
如果很不巧，新插入的节点的父亲节点也为红色，因为红色节点不能连续，所以我们需要调整红黑树的结构使其满足规则。在调整的过程中我们会遇到3种需要处理的情况，我们来一一进行说明。
情况1：
插入新节点40， 此时它的父节点为红色，并且它的叔叔节点（即51）也为红色 。此时我们需要进行 变色 操作。 将该节点的父亲节点、叔叔节点都变为黑色，祖父节点变为红色 。
此时上图已经满足红黑树的规则。但有的时候我们经过了变色操作后，仍不满足红黑树的规则，会遇到下面的情况。
情况2：
如图，我们插入新的节点53，在按情况1的操作变色后，变成了这样:
最后我们说一下情况3的情景，如下图：
我们向树中插入新节点37，在按情况1的操作变色后，变成了这样：
情况3：
3种情况我们说明完了，但是你可能还会有这样的疑问，什么时候进行左旋，什么时候进行右旋；什么时候以父节点为支点旋转，什么时候又以祖父节点为支点旋转？
那么我们可以总结一下，当遇到连续的红色节点应该怎么办： 当前节点我们叫它X，如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置相同，此时，就以祖父节点为支点，进行反向旋转。例如：X为父节点的左孩子，X的父节点同样也是其祖父节点的左孩子，此时以祖父节点为支点进行右旋；
如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置不同，则以X的父节点为支点，进行旋转，旋转方向与X相对于父节点左右位置相反。例如：X为其父节点的左孩子，X的父节点为祖父节点的右孩子，此时以X的父节点为支点进行一次右旋。
在红黑树中删除节点，肯定要涉及到要删的这个节点是红色的还是黑色的。删除红色比较简单，我们先说一下删除红色节点。
删除节点要考虑这个节点所处的位置，所以我们罗列一下红色的节点所有可能的位置情况。
你可能会发现为什么少了一种情况？它不能只有左子树或者只有右子树吗?我们可以看下图:
很明显，这四种情况都不符合红黑树的规则，所以根本不会出现这种情况。
而对于既有左子树也有右子树的情况。 我们可以先和普通的二叉搜索树的删除操作一样，将它与前驱或者后继交换一下 。它就又变成第一种情况——成为了一个叶子节点。所以我们只需考虑当它是叶子节点的情况。
接下来我们看一下当要删除的节点是黑色的时候应该怎么办。
同样我们列一下节点位置可能的情况：
第三种情况和删除红色节点时的处理方法一样，可以转换成第一种或第二种情况，所以我们只关心前两种情况。
当要删除的黑色节点只有一个子树时：
最后我们看一下最难处理的一种情况。
要删除的黑色节点是叶子节点时：
情况1：待删除黑色节点20，它的兄弟节点为红色。
操作方法为：将远侄子节点变黑，兄弟节点与父亲节点互换颜色，最后以父节点为支点进行 左旋 。(为什么是左旋？因为待删除的20是左孩子，我们要将左子树长度拉长，将它沉下来，使它变成多余的节点好删除它，如果它是右孩子，则进行右旋)
操作后如下图就完成了。
情况3：待删除黑色节点20，它的兄弟节点为黑色，但它没有红色的远侄子节点(即nil点，记住，nil点算黑色)，只有红色的近侄子节点。
操作后如下图:
此时有了红色的远侄子，就满足了情况2，再按情况2进行一次操作就完成了。
情况4：待删除黑色节点20，它的兄弟节点为黑色，远侄子、近侄子节点都没有。(即两个nil节点，nil节点算黑色)
我们将上图红黑树按流程演示一下:
第一步按情况4操作，将55变红。并将父节点50看做当前节点，继续操作。
此时有关红黑树的知识就说完了。
以上所有内容都为自己查阅资料学习理解之后手敲的。尽量得采用通俗易懂的描述和解释让读者更明白。27张图都是自己亲自画的，花费了四天才写完，如果觉得写的还可以，麻烦点亮喜欢支持一下，如果还是不懂，可以下方留言QQ等联系方式，我亲自告诉你。
