文档章节

Redis研究-3.3数据结构之树与查找、排序等(后续)

会飞的杨先生
 会飞的杨先生
发布于 2015/08/27 19:21
字数 3351
阅读 1287
收藏 17

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讨论

© 著作权归作者所有

共有 人打赏支持
会飞的杨先生
粉丝 9
博文 14
码字总数 30689
作品 0
昆明
CTO(技术副总裁)
加载中

评论(1)

会飞的杨先生
会飞的杨先生
画图太麻烦了,如果有这么一个工具,在手画的时候记住你画图的过程,然后自动生成一个gif文件,打开的时候,可以播放你画图的所有过程,你愿意使用么?欢迎留言讨论
java collection 集合源码分析(三) map

TreeMap 首先看下TreeMap的头部声明的两个变量,TreeMap的排序利用红黑树进行 /** * The comparator used to maintain order in this tree map, or * null if it uses the natural ordering ......

nero_zy
2015/09/01
123
2
求Tree的Cache数据结构设计思路

背景: 数据示例:中国行政区树形结构,一直到街道(乡村) 使用MySQL作为存储,字段如下: 为减少对数据库的请求量,需要将这些数据存储在Cache中,比如Redis、Memcache等。 大家可以忽略l...

会员
2014/12/18
400
5
java集合框架(四):TreeMap

TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里...

chenzanjin
2017/11/07
0
1
nginx源码分析—队列结构ngx_queue_t

本博客(http://blog.csdn.net/livelylittlefish )贴出作者(阿波)相关研究、学习内容所做的笔记,欢迎广大朋友指正! Content 0. 序 1. 队列结构 2. 队列操作 2.1 在头节点之后插入 2.2 ...

晨曦之光
2012/03/09
216
2
skiplist(跳表)算法实现

跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。 下面来研究一下跳表的核...

golang_yh
2016/01/27
146
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring加载properties文件的两种方式

在项目中如果有些参数经常需要修改,或者后期可能需要修改,那我们最好把这些参数放到properties文件中,源代码中读取properties里面的配置,这样后期只需要改动properties文件即可,不需要修...

架构师springboot
11分钟前
0
0
分布式事务,原来可以这么玩?

多个数据要同时操作,如何保证数据的完整性,以及一致性? 答 : 事务 ,是常见的做法。 举个栗子: 用户下了一个订单,需要修改 余额表 , 订单 表 , 流水 表 ,于是会有类似的伪代码: st...

微笑向暖wx
14分钟前
0
0
IE6兼容PNG32图片显示PNG8图片

IE6并不是不支持PNG图片,只是不支持半透明通道。 是支持PNG8色表引索全透明的。 以往都是通过滤镜或统统使用PNG8实现兼容。 但是我发现twitter的png图标可以在chrome中显示png32,在IE6显示...

linsk1998
26分钟前
0
0
linux运维需要掌握的基础知识

踏入linux运维工程师这一职业,其实有很多工具技能需要掌握,下面我来给大家一一介绍。 1、shell脚本和另一个脚本语言,shell是运维人员必须具备的,不懂这个连入职都不行,至少也要写出一些...

linuxprobe16
27分钟前
0
0
《netty入门与实战》笔记-03:数据传输载体 ByteBuf 介绍

ByteBuf结构 首先,我们先来了解一下 ByteBuf 的结构 以上就是一个 ByteBuf 的结构图,从上面这幅图可以看到: ByteBuf 是一个字节容器,容器里面的的数据分为三个部分,第一个部分是已经丢弃...

Funcy1122
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部