C语言中的树和图有什么用

树和图是两种常见的数据结构，在计算机技术应用十分广泛，他们也是两种思考问题的方式，常用于结局实际问题。树最直观的用途就是如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。在数据库系统中，树型结构也是信息的重要组织形式之一，一切具有层次关系的问题都可用树来描述。数据结构的图就是实际情况的抽象，即逻辑模型，然后通过计算机编程来解决问题。比如一个很复杂的地图，有很多城市，有很多路，如何找出最短路径呢？当然是用计算机来算了，你就得用图来表示等等，很多用途，如果你学习数学建模，你会经常遇到他们的好好学吧

这样说呢，可能大家也猜到了是【二分查找法】，通过这个例子呢，主要想引出的是树，看下面的图片：

程序中的树呢，其实是我们日常看到的树的倒影，或者发挥一下想象，倒影也可以是树根

二叉查找树，Binary Search Tree 「BST」，要想了解二叉查找树呢，首先我们需要了解一下二叉查找树都有哪些特性呢？

看个图就轻松理解上面三句话的意思了:

上图，结合二叉查找树的三条约束来看，非常好，没有什么问题。再来看一个图，依旧符合上面三条约束，感觉有问题吗？

这是一个走路一米六，一米八的树

这是一个畸形的树，大风一挂很可能被折断的树

从程序的角度来说这个树不够平衡，查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长

理科生在高中学习生物时学过一个关键字「去除顶端优势」，通过去除植物顶端优势，侧芽会迅速生长，慢慢变得强壮和平衡， 红黑树其实就是去除二叉查找树顶端优势的解决方案，从而达到树的平衡

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

可能大家还是很懵逼，不过没事，多练习几次就熟悉了。

红黑树有两大 *** 作：

我们会先尝试recolor，如果recolor不能达到红黑树的四个要求，然后我们尝试rotation，其实红黑树的关键玩法就是弄清楚recolor和rotation的规则，接下来我们看一下详细的算法公式吧。

假设我们插入的新节点为X

接下来看下图：

跟着上面的公式走：

上面说的是X的uncle为红色的情况，接下来我们看一下X的uncle为黑色的情况

当uncle节点为黑色的时候，我们第一步考虑的是旋转，这里呢我们可以先不关注红黑树的4个规则，主要是演示如何旋转的。

这种情况很简单，想象这是一根绳子，手提起P节点，然后变色即可，如下图：

变色：X是当前节点，P是X的parent节点，U是X的uncle节点，G是grand parent节点。P节点是根节点变黑色，G变成和X一样的颜色，也就是红色。完成

先进行左旋：使X的父节点P被X取代，同时父节点P成为X的左孩子，然后在应用 左左情况 ，如下图：

像左左一样，看成一根绳子。手提起P节点，然后变色即可，如下图：

先右旋：使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用 右右情况 ，如下图：

通过上述过程，想必大家对红黑树有了一定的了解。以后在提到红黑树的时候，就不会那么头大了。本文参照 日拱一兵 公众号中的文章"红黑树，超强动静图详解，简单易懂".

参考文章

---