vlambda博客
学习文章列表

在本号描述的世界里面，有许多的儿童，他们组成了本号情节背景的重要的一部分。本号的号主常常走在大湾区的街头巷尾，看到入学的儿童名册，看到儿童们在少年宫的表演，发现浩、宇、涵、晓、雨等等太多了（含同音字）。经常在一个片区里面出现一堆“子浩”、“雨涵”等等，这对于大量数据的录入很不理想。

鸡蛋花，凤凰木，都是二叉排序树的原型

一棵树从他的脑海中长出，它如同鸡蛋花或是凤凰木，数据沿着鹰爪似的树枝走下去，它的数据总是按着有序的方式插入，这就是二叉排序树。

在《在二叉树中成为主人》中曾经留下一个问题，是否可以把儿童们按照他们的姓名的汉语拼音排序分布在一棵二叉树中？答案是可行的。下面将体现如何把这么多的儿童的数据加载在一棵二叉排序树中。

本质就是分两边，也就是类聚

在开始的时候，第一个结点直接成为根结点。然后第二个结点开始，每次和前面的第一个结点比较，如果比它小就会插入到左子树，比它大就会插入右子树，当结点与之前的结点有重复时，新结点插入在其左子树的最右边。

在计算机中操作时，结点的比较方式为其对应编码方式的值的大小，英文为ASCII码，中文根据编译器的不同，可以是部首或汉语拼音排序。这样就能得到一个有序的二叉树。

花或果实可以看作权值，左边的值总比右边小

但问题在于，当插入的顺序近似于有序的时候，二叉树就会退化为单支树，无法发挥二叉排序树把搜索次数尽量压缩到log2(n)的作用。同样的，在删除的时候，虽然在删除的时候，叶子结点直接删除、度为1的结点用其左或右子树补上，度为2的结点用左子树的最右结点顶上，但当只删除一侧的结点时，还是会出现不平衡或退化为单支树的情况，也无法发挥二叉树的优势。

所以为了防止出现这样的问题，就涉及到旋转的问题。平衡二叉树也是从这里开始的。

单支树最大的劣势在于搜索里面的元素时近似于一个一个查找

平衡二叉树就是任何一个结点的左右子树的高度差的绝对值不大于1的二叉树。这样的二叉树可以大幅减小平均搜索长度，使得平均搜索长度与log2(n)成正比（平均搜索长度准确值为((n+1)/n)*log2(n+1)-1），同时使得二叉树形态更加美观。为了实现平衡二叉树，就需要涉及4种旋转方式。分别是LL、LR、RR、RL型旋转方式。

其中LL型的调整方式是把根结点和它的左子树向右旋转，把根的左孩子的右子树变成右孩子的左子树，根的左孩子变成新的根结点，原来的根结点变成新的根的右孩子。RR型的调整方式和LL型相反，但类似。LR型的调整方式是先把根结点的左子树左旋转，然后把根结点右旋转，RL型的调整方式与LR型相反。它们分别对应左子树的左子树高（高指出现不平衡）、右子树的右子树高、左子树的右子树高、右子树的左子树高的情形。

四种平衡二叉树旋转方式

通过在插入和删除的时候及时对二叉树进行适当的旋转，就可以保证任何时候任何一个结点的左右子树的高度差的绝对值不大于1，实现平衡二叉树的目的。

在这样的自平衡算法下，二叉排序树的效率得到更大化，于是就能把这些儿童们的信息以更高的效率存储在二叉树当中，体现在最多n次搜索和最多（log((1+√5)/2)(√5*(n+1))-2）次搜索的区别，大大节省了时间，也能让线性的空间得到扩展。

平衡二叉树使得每一层的空间可以被充分利用

例如100个数据在最坏的情况下，只需要搜索9次，这相比于顺序表中最大的100次搜索节省很多。而且把儿童们的信息存储在二叉排序树插入新结点或删除结点时，可以不断平衡优化，使得搜索次数总是趋向于一定值。当儿童们的数据变得很大的时候，平衡二叉树的优势会更加显著。

他很喜欢平衡二叉树的美观和高效性，所以在存储查找一堆的子轩、雨涵、子浩（含同音字）的时候，平衡二叉树就会显得特别有序。因为即使有很多同名的儿童，也可以根据姓名之外的其他字段（例如ID号码等）再次进行判断插入不同的位置，使得每个儿童在二叉树中都是唯一的。

平衡二叉树能够使得所有数据都是唯一确定的，还能方便分组

于是儿童们就可以根据这棵平衡二叉树找到自己的朋友了，无论是分层还是按照左右子树分区，这样就解决了《在二叉树中成为主人》中的问题。儿童们因此能在二叉树中找到自己的位置，建立起同龄人的树状协作网络。

他希望这样美观的二叉树，可以让儿童们利用他们的数学等知识，努力探究这棵树中的真谛，真正成为二叉树的主人。

鸡蛋花又开了，让他们懂得如鹰爪一样的思维网络，这是知识的力量

站在高处看大都会，数据结构和它的思想本来就存在于都会的筋络中

他的思绪如生长之树，写下了计算机实现儿童的数据存储的源代码，由于长度过长，请见本次群发第二篇推文。

本号所写的数据结构，看似是高深的问题，实际上，就是计算机与数学在现实世界的应用。这些文章的字里行间，是对世界思维网络的思考，期待后辈能够从小建设起兼具深度和广度的思维网络，让思维成为改变世界的动力。

点击文字回顾往篇：