引言

真实的世界里，到底是具体的数值重要，还是数值之间相对的大小更重要？

在计算机科学中,相对的大小要比绝对的数量更重要。这一点，计算机科学和数、理、化都不相同,计算机只看重相对的输赢。

任何选择都比没有选择要好！在生活中也是如此，我们通常无法脚踩两只船。

工具的发明是针对问题来的:

1. 在数学上要计算数字，人类就发明了算盘。
2. 在物理学上，要测量绝对的数值，人类就发明了各种度量长度的尺子、计时的钟、称重量的天平和秤等等。
3. 在化学上，要测量化学反应的当量，人类就发明了各种有刻度的量器。
4. 在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作，而它们在计算机的世界里又如此重要，当然也就值得为这些事情专门设计一种数据结构，这种数据结构被称为二叉树。

I 二叉树

1、 我们在生活中，一些组织结构其实就是树状结构，比如一个公司的大老板是根结点， 2、这种怪怪的数据结构在计算机科学中有什么用处呢？

1）可以用于排序(从左到右是从小到大)、 2）快速查找到某一个数值。3）另外，网站的目录结构也是树状的（N个分叉）， 因此，针对二叉树的各种算法，稍加改变，就可以用于互联网。比如，下载一个网站里面所有的网页，就会用到二叉树中的一种遍历算法。

1.1 二叉树排序的过程遵循的两条规则

1. 先来的占据根部，以及靠近顶部层级比较高的位置，后来的放在相对靠下的位置。
2. 每当一个分支的根部被占据之后，接下来的数字，是和根部的数字进行比较，小的放到左边分叉中，大的放到右边分叉中。

它左右两个分叉可以和比较大小后的两种结果自然对应起来。

1.2 内容总结：

1. 工具是根据所遇到的问题而发明的

2. 在计算机科学中，数据的相对大小比绝对的数值重要，出于很多数据比大小的需求以及其他一些需求，就产生了一个抽象的数据结构——二叉树。

3. 和很多抽象的工具一样，二叉树其实能在现实生活中找到很多对应。除了比大小之外，我们的组织架构，我们的文件目录，网站的链接层次，以及锦标赛，都能对应到二叉树中。

4. 对应到二叉树的问题，都有一些共性，解决它们之间问题的方法是可以触类旁通的。这就是我们要学习理论的目的.

II  作为二叉树的变种，哈夫曼树和红黑树在查询或者写入效率上做了优化呢？

目的不同:

1. 哈夫曼树对应于哈夫曼编码，即信息论里的最短编码。这样可以保证平均的访问时间最短。哈夫曼编码的条件是必须事先知道每个码出现的频率。
2. 红黑树是为了防止二叉树一个枝子太长，另一个太短, 导致效率不高。

使用红黑树，可以保证各个枝子的长度基本相等。代价是需要不断维持平衡。二叉搜索树和平衡二叉树的时间复杂度 与树的高度h相关，所以需要尽可能的降低树的高度

原文链接：https://blog.csdn.net/z929118967/article/details/115913603

III 二叉搜索树和平衡二叉树的时间复杂度

与树的高度h相关，所以需要尽可能的降低树的高度。

【二叉搜索树 Binary search tree、平衡二叉树Balanced binary tree】