Redis研究-3.3数据结构之树与查找、排序等(后续)
Redis研究-3.3数据结构之树与查找、排序等(后续)
会飞的杨先生 发表于2年前
Redis研究-3.3数据结构之树与查找、排序等(后续)
  • 发表于 2年前
  • 阅读 1259
  • 收藏 17
  • 点赞 0
  • 评论 1

腾讯云 十分钟定制你的第一个小程序>>>   

摘要: 通过上一章节的学习,我们了解了一些关于hash的实现相关方面的东西,但是里面还涉及到几个方面的知识,我们是还不太清楚的,比如说是查找,搜索(查找是搜索的特例)以及排序。因此为了能了解更多的底层知识,我觉得这一章节有必要先说说有关树的概念、排序、查找等方面的内容,目的是为了总结一下上一章节里面的提到的开放式寻址(在解决键冲突时候用到的方法)的原因以及为下一章节来要说道的跳跃表做个知识铺垫。

3.树、二叉树、森林之间的转换

   前面我们又说到,二叉树中的节点我们可以表示成一个具有左孩子域、右孩子域、双亲域、自身数据域的一个数据结构,那么对于一般的树或者森林中的节点来说,能不能也这样子表示呢?答案是可以的,表示成二叉树节点的形式,我们就能很好的使用二叉树的一些特性和算法。

在二叉树中,left表示节点的左孩子、right表示节点的右孩子,那么,对于一般的树节点来看,如果存在孩子,第一个孩子就是对应的left区域,如果有第二个、第三个孩子等,就用right形成一个链表,那么,这种树就转换为二叉树啦,只是这里两个指针域的说法不太一样而已。实际上,我们对于节点来说,我们可以改进一下得到如下的表示:

//修改后的一般的树节点表示
typedef struct gTBiTreeNode{
    struct gTBiTreeNode *left;
    struct gTBiTreeNode *right;
    void *data;
    struct gTBiTreeNode *next;//兄弟节点
}gTBiTreeNode,*gTBiTreeNode;



3.1 树转换为二叉树

  上面已经改造了树节点的表示,那么一般的树怎么转换为我们常见的二叉树呢?只需要三个步骤即可:

  1).加线。在所有的兄弟节点之间加一条连接线;

  2).去线。对数中的每个节点,只保留他与第一个孩子节点的连接,删除他与其他孩子节点之间的连接线。

  3).层次调整。以树的根为轴心,将整棵树顺时针旋转一定的角度,使之层次分明。这里要注意的是,第一个孩子是二叉树节点的左孩子,兄弟转换过来的孩子是节点的右孩子。

我们用图来表示一下

 

 

 

我们重点来看看,怎么调整成最后的这个层次了,首先我们应该清楚第三个步骤调整的原则:

  第一个孩子是节点的左孩子,那么B当然是A的左孩子啦。根据第二条原则,兄弟转换过来的孩子是节点的右孩子,因为C是B的兄弟,所以,转换过来后,就变成了B的右孩子。同样的,因为E是B的做孩子,所以转换后当然是B的左孩子。同样的,根据第二个原则,F是E的兄弟,所以,转换后,F变成了E的右孩子,G先前是F的兄弟,现在变成了F的右孩子。同样的,我们的先前的树中C的第一个孩子就是H,所以,现在H当然是C的左孩子,同样的,因为D是C的兄弟,所以现在变成了C的右孩子。I在以前的树上就是D的第一个孩子,所以,现在是D的左孩子,又因为J先前是I的兄弟,所以,现在变成了I的右孩子。

通过上面的文字描述,我们要特别注意,第二个原则,就是"兄弟孩子变成了节点的右孩子这个说法".

3.2 森林转换为二叉树

什么是森林?森林当然是由很多的树组成的啦。那么,我们当然可以把其中的每一颗树看做是兄弟,因此,我们就可以得到下面的转换步骤了。

1).把每棵树转换成一颗二叉树;

2).第一颗二叉树保持不动,从第二棵二叉树开始,依次把后一棵树的根节点作为前一棵二叉树的根节点的右孩子,然后用线连接起来。

用图来演示一下:

 

OK,应该说清楚了,那么,二叉树又怎么转换成树呢?

3.3 二叉树转换成树

前面我们已经从树转换成二叉树了,他要经历过三个步骤,分别是加线,去线,调整层次,那么,二叉树转换为树,也就是这个过程的一个逆过程,怎么做呢?

任然是

1).加线。如果节点的左孩子存在,则将这个左孩子的右孩子节点、右孩子的右孩子节点、。。。都作为这个节点的孩子节点,将该节点与这些右孩子节点连线。

2).去线。删除原二叉树中所有节点与其右孩子节点的连线。

3).层次调整。

有图有真相。

 

 

so easy,不是么?

3.4 二叉树转换成森林?

   一棵树能否转换成森林,判断的标准很简单,就是看这个二叉树的根节点有没有右孩子节点,如果有,那就可以转换。转换步骤是:

1).从根节点开始,若右孩子存在,则把与右孩子及诶单的连接线删除,分离以后,继续迭代。

2).将每棵分离后的二叉树转换为树即可。

上图

估计是傻瓜也能看得懂了吧???O(∩_∩)O哈哈~

3.5 哈夫曼编码

  我不知道大家在大学时候有没有学过运筹学,运筹学里面很重要的一个分支就是讲动态规划的(哈哈,在下本科就是数学系的哈,当时的运筹学考了67分,低分飘过,不过最高分也就是72啦)。在某些求解最优化问题的算法中,每个步骤都面临着多种选择,动态规划是这种问题的杀手级算法,但是有时候又会显得有点笨重,所以,在这个时候,我们需要一种更简单、更高效的算法,贪心算法就是这样一种算法,贪心算法的核心就是在每一步都做出当时看起来最佳的选择,或者叫做局部最优的选择,通过这种选择来得到最后的一个全局最优解。当然,这只是一种希望,所以,贪心算法并不保证能得到一个最优解。我们这里就先学习一种贪心算法-哈夫曼编码。

在说这玩意儿之前,先看个我们现实生活中的例子(这个例子来自《大话数据结构》,请各位参考)。里面就是说,老师在给学生评“不及格”、“及格”、“中等”、“良好”、“优秀”的时候,是根据学生的分数段来进行的,通常情况下,我们使用下面的一个结构来判断:

int degree(int score){
  if(score<60){
    printf("%s","不及格");
  }else if(score<70){
    printf("%s","及格");
  }else if(score<80){
    printf("%s","中等");
  }else if(score<90){
    printf("%s","良好");
  }else{
    printf("%s","优秀");
  }
}



得到的图化结构是:

当我们看到在实际的学习生活中,学生的成绩阶段比例是如下所示的时候,我们就会感到这个算法是大有问题的了


分数 0-59 60-69 70-79 80-89 90-100
比例 5% 15% 40% 30% 10%
,要查看70分以上的学生数据,至少要通过3此比较才能做出判断,那么,怎样来改进呢?
int degree(int score){
  if(score<80){
    if(score<70){
        if(score<60){
           printf("%s","不及格");
        }else{
          printf("%s","及格");
        }
    }else {
        printf("%s","中等");
    }
  }else if(score<90){
      printf("%s","良好");
  }else {
    printf("%s","优秀");
  }
}



通过这次改进以后,70-79之间的分数最多需要两次就能判断了,是不是更优化了呢?二叉树的表示方法如下:

 

 

假如,现在有1000学生,那么没改进之前,需要的判断次数是3150次,而改进后,需要用到的次数是2200次,效果很明显,特别是数据量大的时候。

 为了说清楚接下来的内容,有几个概念需要明确一下:

 

1).从树中一个节点到另外一个节点之间的分支构成两个节点之间的路径,路径上的分支数据叫做路径长度(走得通的路径)。

2).树的路径长度是从根到每一个节点的路径长度之和。树A的路径是:1+1+2+2+3+3+4+4=20.

3).节点的带权的路径长度是从该节点到树根之间的路径长度与节点上权的乘积。树A中的及格的带权路径是15*2=30;

4).树的带权路径路径是树中所有叶子节点的带权路径长度之和。树A的带权路径是:5*1+15*2+40*3+30*4+10*4=315;

5).带权路径长度WPL最小的二叉树就是哈夫曼树。

 

那么,怎么来构建哈夫曼树呢?遵循以下步骤

1).先把带有全职的叶子节点按照从小到大的顺序来排列成一个有序序列。

2).从这个有序序列中选择较小的两个来构造一个新的二叉树,较小的权值的节点作为新二叉树的左孩子,较大的作为右孩子,新的二叉树的根节点的权值是两个孩子的权值之和。

3).从序列中删除已经选择的两个较小权值的节点,并把步骤2中构造的新二叉树的根节点带到这个序列中排序。

4).重复步骤2、3就可以得到最终的哈夫曼树。

 

我们从树B来看怎么构造一个哈夫曼树:

 

 

新排序:N=15,B,D,C

 

 

重新排序:N=30,D,C

重新排序:C,N=60

构造后的这颗树的带权路径=40*1+30*2+15*3+10*4+5*4=205;

而原来的这颗树的带权路径是:5*3+15*3+40*2+30*2+10*2=220;

我们算一下需要多少判断步骤3050次,反而比不是哈夫曼树的算法还低效?那这说明哈夫曼树没用么?不是的。

 

我们再看一下:

假设我要给你远程发送一段“BADCADFEED”的内容,网络传输中,一般都是用二进制来表示的,在这段文字中出现了A,B,C,D,E,F这6个字符,假设我们分别以三位二进制来代替一个字母,则可以得到下面的对应表:


A B C D E F
000 001 010 011 100 101

那么,这段内容的编码就是:001000011010000011101100100011,一共是30位。但是我们发现,在这段内容中,各个字母出现的频率是不一样的,他们出现的频率分别是:


A B C D E F
0.2 0.1 0.1 0.3 0.2 0.1

也就是说,我们可以用哈夫曼树来进行一个构建

 

我们将权值做分支改为0,右分支改为1:

所以,得到的对应的字母编码映射表是:


A B C D E F
110 11110 11111 0 10 1110

那么,使用这种编码以后,发送内容应该是:111101100111111100111010100,一共是27位。

也就是说,我们改进后,节约了10的存储或者传输成本。

实际上,我们从上面来看到,这其实就是一种变长的编码,核心思想就是将高频的字符用最短的码字来表示,低频的用长的码字来表示。

其实我们还可以得到,我们构造的这棵二叉树,是一颗满二叉树。

哈夫曼编码的正确性的证明请参考由殷建平、徐云等人翻译的《算法导论-原书第三版》第248页。

二叉搜索树:就是在二叉树的基础上满足一个特性的二叉树就叫做二叉搜索树,这个特性就是对于树上任何节点X,其左子树的关键字不能超过X的关键字,其右子树的的关键字不能小于X的关键字。

红黑树:就是在二叉搜索树的每个节点上增加了一个颜色属性,这个属性有两个黑色和红色取值。同时要满足下面的特性:

1).每个节点要么是红色的,要么是黑色的。

2).根节点是黑色的。

3).每个叶子节点是黑色的;

4).如果一个节点是红色的,则他的两个子节点都是黑色的;

5).对每个节点,从该节点到其所有的后代叶节点的简单路劲上,均包含相同数目的黑色节点。

 遇到其他的树,再来写,基本上都是在二叉树的基础上加了一些限制

下一节,将继续说排序、查找

欢迎拍砖,同时也可以加QQ:359311095讨论

共有 人打赏支持
粉丝 10
博文 14
码字总数 30689
评论 (1)
会飞的杨先生
画图太麻烦了,如果有这么一个工具,在手画的时候记住你画图的过程,然后自动生成一个gif文件,打开的时候,可以播放你画图的所有过程,你愿意使用么?欢迎留言讨论
×
会飞的杨先生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: