计算机原理-IO(三)

CPU和存储器之间是如何相互之间通信的呢,IO性能的瓶颈又是在哪里,希望看了这节可以给你解答。

总线

目前软件架构都流行ESB企业总线来处理消息的相互流转,这个架构灵感就参考了计算机中的总线。所谓总线是各种功能部件之间传送信息的公共通信干线,它是由导线组成的传输线束。我们知道计算机有运算器,控制器,存储器,输入输出设备这五大组件,所以总线就是用来连接这些组件的导线。

按照计算机所传输的信息种类,计算机的总线可以划分为

  • 数据总线: 数据总线DB是双向三态形式的总线,即它既可以把CPU的数据传送到存储器或输入输出接口等其它部件,也可以将其它部件的数据传送到CPU。数据总线的位数是微型计算机的一个重要指标,通常与微处理的字长相一致。我们说的32位,64位计算机指的就是数据总线。
  • 地址总线: 地址总线AB是专门用来传送地址的,由于地址只能从CPU传向外部存储器或I/O端口,所以地址总线总是单向三态的,这与数据总线不同。地址总线的位数决定了CPU可直接寻址的内存空间大小
  • 控制总线:控制总线主要用来传送控制信号和时序信号。控制总线的传送方向由具体控制信号而定,一般是双向的,控制总线的位数要根据系统的实际控制需要而定。其实数据总线和控制总线可以共用。

总线也可以按照CPU内外来分类:

  • 内部总线:在CPU内部,寄存器之间和算术逻辑部件ALU与控制部件之间传输数据所用的总线称为片内部总线。
  • 外部总线:通常所说的总线指片外部总线,是CPU与内存RAM、ROM和输入/输出设备接口之间进行通讯的通路,也称系统总线。

控制芯片

主要控制CPU和存储器,I/O设备等进行交互。一般都集成在主板上,所以攒机也不能忽略主板的。

对于目前的计算机结构来说,控制芯片集成在主板上,典型的有南北桥结构和单芯片结构。与芯片相连接的总线可以分为前端总线(FSB)、存储总线、IQ总线,扩展总线等。

  • 南北桥芯片结构
    • 北桥芯片,它控制着CPU的类型,主板的总线频率,内存控制器,显示核心等。它直接与CPU、内存、显卡、南桥相连,所以它数据量非常大;
      • 前端总线:是将CPU连接到北桥芯片的总线。FSB的频率是指CPU和北桥之间的数据交换速度。速度越快,数据带宽越高,计算机性能越好;
      • 内存总线:是将内存连接到北桥芯片的总线。用于和北桥之间的通信;
      • 显卡总线:是将显卡连接到北桥芯片的总新。目前有AGP,PCI-E等接口。其实并没有显卡总线一说,一般认为属于I/O总线;
    • 南桥芯片,它主要负责外部接口和内部CPU的联系;
      • I/O总线:连接外部I/O设备连接到南桥的总线, 比如USB设备,ATA,SATA设备,以及一些扩展接口;
      • 扩展总线:主要是主板上提供的一些PCI,ISA等插槽;
  • 单芯片结构: 单芯片组主要是是取消了北桥,因为现在CPU中内置了内存控制器,不需要再通过北桥来控制,这样就能提高内存控制器的频率,减少延迟。而现在一些CPU还集成了显示单元。也使得显示芯片的频率更高,延迟更低。

频率=性能

数据带宽 = (总线频率*数据位宽)/ 8

(每秒传送次数*每次传送大小)/单位大小转换

外频:系统总线的工作频率,一般的电脑这个是连接其他部件工作的基础频率。

分频:外部IO频率比系统总线低,采用2/3或1/3分频的方式就能使得CPU和外设同步的工作了。

倍频:CPU比外频高,所以需要一个倍频来协调工作。

CPU工作频率=外频*倍频

内存总线频率:

因为内存总线频率不同,所以内存和CPU之间存在同步和异步两种工作方式。

  • 同步方式:内存总线频率和CPU外频相同。比如以前的PC133和P3处理器,他们以同步的方式工作在133MHZ下。而当你超频时就需要拥有更高总线频率的内存。当然也需要北桥芯片的支持。
  • 异步方式:内存总线频率和CPU外频不同。睡着CPU外频的提高,内存也必须更新,所以出现了异步的方式。比如P4 CPU外频为200MHz,而内存却可以使用DDR333来运行。同时异步方式也在超频时经常使用。一般来说会有一个内存异步比率。在BIOS中会有相应的选项。

从性能上来讲,同步方式的延迟要好于异步方式,这也是为什么以前会说P4 200外频的CPU要使用DDR400才能发挥最大功效。但这也不是绝对的。比如我的I5处理器CPU外频工作在100MHz,而我使用的DDR3-1600的总线频率在200MHz,虽然不同步,但是拥有更高的传输速率。所以不能一概而论。

外部IO:

前面主要介绍了系统总线和CPU与内存之间的通信,最后一部分简单介绍一下CPU和I/O设备是如何通信的。对于计算机来说输入输出设备也是五大组件。我们知道相对于CPU,I/O设备的工作频率要慢的很多。比如早期的PCI接口工作频率只有33MHz,硬盘的IDE-ATA6的传输速率也只有133MB/s。而现在的 SATA3接口速率能达到600MB/s。

I/O设备一般由机械部件和电子部件两部分组成。电子设备一般称为设备控制器,在计算机上一般以芯片的形式出现,比如我们前面介绍的南桥芯片。不同的控制器可以控制不同的设备。所以南桥芯片中包含了多种设备的控制器,比如硬盘控制器,USB控制器,网卡、声卡控制器等等。而通过总线以及卡槽提供和设备本身的连接。比如PCI,PCI-E,SATA,USB等。

每个控制器都有几个寄存器和CPU进行通信。通过写入这些寄存器,可以命令设备发送或接受数据,开启或关闭。而通过读这些寄存器就能知道设备的状态。因为寄存器数量和大小是有限的,所以设备一般会有一个RAM的缓冲区,来存放一些数据。比如硬盘的读写缓存,显卡的显存等。一方面提供数据存放,一方面也是提高I/O操作的速度。

现在的问题是CPU如何和这些设备的寄存器或数据缓冲区进行通信呢?存在两个可选方案:

  1. 为每个控制器分配一个I/O端口号,所有的控制器可以形成一个I/O端口空间。存放在内存中。一般程序不能访问,而OS通过特殊的指令和端口号来从设备读取或是写入数据。早期计算机基本都是这种方式。
  2. 将所有控制器的寄存器映射到内存空间,于是每个设备的寄存器都有一个唯一的地址。这种称为内存映射I/O。

    另一种方式是两种的结合,寄存器拥有I/O端口,而数据缓冲区则映射到内存空间。Pentinum就是使用这种方式,所以在IBM-PC兼容机中,内存的0-640K是I/O端口地址,640K-1M的地址是保留给设备数据缓冲区的。(关于内存分布后面文章会介绍)

    对于我们程序员来说这两种方案有所不同

    1. 对于第一种方式需要使用汇编语言来操作,而第2种方式则可以使用C语言来编程,因为他不需要特殊的指令控制,对待I/O设备和其他普通数据访问方式是相同的。
    2. 对于I/O映射方式,不需要特殊的保护机制来组织对I/O的访问,因为OS已经完成了这部分工作,不会把这一段内存地址分配给其他程序。
    3. 对于内存可用的指令,也能使用在设备的寄存器上。

    任何技术有有点就会有缺点,I/O内存映射也一样:

    1. 前面提到过Cache可以对内存进行缓存,但是如果对I/O映射的地址空间进行缓存就会有问题。所以必须有机制来禁用I/O映射空间缓存,这就增大了OS的复杂性。
    2. 另一个问题是,因为发送指令后需要判断是内存还是I/O操作,所以它们需要能够检查全部的内存空间。以前CPU,内存和I/O设备在同一个总线上,所以检查很方便。但是后来为了提高CPU和内存效率,CPU和内存之间有一条高速的总线(比如QPI)。这样I/O设备就无法查看内存地址,因为内存地址总线旁落到了内存和CPU的高速总线上,所以需要一个额外的芯片来处理(北桥芯片,内存控制器的作用),增大了系统的复杂度。

 

瓶颈:1.寄存器-》内存(倍频-外频-内存频率)(普通应用可以忽略)

            2.IO瓶颈    IO速度实在太低(高性能程序都使用预先加载到内存的方式或者内存映射的方式来处理IO瓶颈:以时间,空间,金钱换取速度)

计算机原理(二)

不知道大家是否有过攒机的经历,攒机的时候,我们经常说不能只管 CPU 频率多高,性能多好,也要兼顾其他设备的性能,经常听到的词汇就是内存要大,总线频率也要匹配,硬盘转数也要跟上,这些其实都是涉及到不同设备部件之间的IO,一个不匹配就会拖累其他的。前面我们已经看了些CPU的皮毛,那么接下来我们就看下这些可能拖后腿的部件吧!

存储器

存储系统除了内存,硬盘这些,大概分为:寄存器、Cache、内部存储器、外部存储。请看如下图:

金字塔顶端的性能最好,既然这样,为啥还要分层呢,直接用L0就好了!

性价比。没有性价比,这些东西就不可能飞入寻常百姓家!我们知道,CPU是很快的,所以我们需要通过分层来平衡IO瓶颈,越接近CPU用越快的存储介质:各种晶体管,磁盘!

寄存器

寄存器基本与CPU是同频的,说明其高性能,但同时也意味着高能耗,高成本!所以我们只能少量的把寄存器集成到CPU中!

CASHE

SRAM,静态RAM,通常用于高速缓存,一般CPU中就集成了2级缓存就是这个!

DRAM ,这个其实就是我们熟悉的内存,这个容量大,DDR表示双倍的速率,而现在又有了DDR2,DDR3,他们的带宽也是越来越大。

上面的介质在断电后数据是会消失的,所以不能用来永久 存储数据,而ROM ,FLASH以及磁盘设备就是用来永久存储数据的,当然ROM 比磁盘速度快!

上面讲了这么多的存储设备,那么下一回,我们就来讲讲他们之间的通信,借此也可以了解看看以后如果写代码可能的瓶颈在哪里。

计算机原理(一)

大学毕业作也快两年了,回顾下,其实大学很多课程都是非常基础,对IT工作者而言其实是非常有作用的,特别是当要学得更加深入的时候,再去回顾下基础的东西是非常有必要的,所以就记录下回顾下计算机原理 的心得体会!

计算机之父

计算机发展史也不必刻意去多写了,我们都说冯诺依曼是计算机之父,其实图灵大大才是教父!

计算机组成

我们的计算机核心就是 :存储程式,然后执行!

下图就是一个基本结构流程:输入,存储,执行,输出。

对我们写代码的来说,比较重要的是存储与执行,因为这涉及到程序的性能如IO,计算速度等,我们最关心的就是CPU与内存了!程序数据是存储在硬盘里面,而如果要执行,一般来说我们需要把程序启动,把执行指令加载到内存中(数据交互更快)缓存着,然后CPU执行内存中的指令运算得出结果输出!

指令集

我们都知道,计算机是只能识别0跟1的(不通电OR通电),但是如果只是使用 0跟1进行编程,OMG,我想我们都要晕了,所以就出现了指令,我们装机买CPU的时候,都会听到指令集这么个说法,指令集跟牛逼啥的,其实就对应了我们这里说的0和1的一些组合,每个指令集可以然CPU执行一个(或者一组【牛逼的指令集】)操作,越牛逼的指令集在相同硬件条件下,能够让计算机速度更快!

汇编语言

二进制指令集虽然可以让CPU识别并执行,但是作为人类,还是太难懂了,所以就出现汇编语言,他用符号来映射具体的指令集,可读性进一步提升!那么把汇编语言转化为指令集,就需要一个辅助工具,汇编器

高级语言

计算机技术要普及,汇编语言显然还是太晦涩难懂,并且跟具体的硬件还有太多耦合,不同CPU可能只能识别不同的指令集,这样就需要写不同的汇编程序去实现,为了生产力的发展,于是不断出现各种高级语言,如C,C++,JAVA,C#…,从前面我们知道,高级语言也是不能被计算机识别的,所以我们就要编译器将高级语言转换成汇编程序,不同CPU硬件,我们就用不同编译器进行转换成不同的汇编程序,而不需要写不同的程序,编译器帮我们把硬件的差异屏蔽!

高级语言之间的差异

C,C++这种语言,其实是可以跨平台的,但是所写的程序代码,在不同平台(硬件)就需要不同编译器从新编译过才能执行。那么是不是有语言是可以做到写一次代码,编译一次代码就可以到处运行了呢!答案是肯定的,根据前面的一些讲解,你应该猜到了,这中间肯定还要加一层东西吧?答案是肯定的,JVM 虚拟机就是这么个中间的东西,JAVA语言写的代码,是先编译成中间代码的,然后由JVM负责解释执行。因为是在运行的时候解释执行的,所以性能上会有所下降,当然这提高了生产力,所以性能下降算个P啊(当然这只是针对大多数普通程序来说)!当然还有更加牛逼的脚本语言,都不需要编译成中间代码,直接依靠解释器就执行起来了,这又叫脚本语言,JS,大蟒蛇…说实在,也不慢啊!

本来想说计算机原理来着,顺便扯了些语言的东西,我们还是回来看CPU的是如何工作的吧:

CPU

有前面的图我们看到,CPU主要是由运算器与控制器组成的,控制器负责指令的,运算器接收指令进行运算处理,如果就是看上去那么简单,那么就太小看CPU了,实际CPU的组成运算比这个复杂多了,我们来看看Intel奔腾处理器的详细组成:

好晕啊,我来来具体分析下组要部件运算器与控制器的组成:

 控制器由程序计数器、指令寄存器、指令译码器、时序产生器和操作控制器组成。它是计算机指挥系统,完成计算机的指挥工作。尽管不同计算机的控制器结构上有很大的区别,当就其基本功能而言,具有如下功能:

    • 取指令 从内存中取出当前指令,并生成下一条指令在内存中的地址。 
    • 分析指令 指令取出后,控制器还必须具有两种分析的功能。一是对指令进行译码或测试,并产生相应的操作控制信号,以便启动规定的动作。比如一次内存读/写操作,一个算术逻辑运算操作,或一个输入/输出操作。二是分析参与这次操作的各操作数所在的地址,即操作数的有效地址。 
    • 执行指令 控制器还必须具备执行指令的功能,指挥并控制CPU、内存和输入/输出设备之间数据流动的方向,完成指令的各种功能。 
    • 发出各种微操作命令 在指令执行过程中,要求控制器按照操作性质要求,发出各种相应的微操作命令,使相应的部件完成各种功能。 
    • 改变指令的执行顺序 在编程过程中,分支结构、循环结构等非顺序结构的引用可以大大提供编程的工作效率。控制器的这种功能可以根据指令执行后的结果,确定下一步是继续按原程序的顺序执行,还是改变原来的执行顺序,而转去执行其它的指令。 
    • 控制程序和数据的输入与结果输出 这实际也是一个人机对话的设计,通过编写程序,在适当的时候输入数据和输出程序的结果。 
    • 对异常情况和某些请求的处理 当计算机正在执行程序的过程中,发生了一些异常的情况,例如除法出错、溢出中断、键盘中断等。

运算器的组成和功能: 运算器由算术逻辑单元(ALU)、累加寄存器、数据缓冲寄存器和状态条件寄存器组成,它是数据加工处理部件,完成计算机的各种算术和逻辑运算。相对控制器而言,运算器接受控制器的命令而进行动作,即运算器所进行的全部操作都是由控制器发出的控制信号来指挥的,所以它是执行部件。运算器有两个主要功能:

  • 执行所有的算术运算,如加、减、乘、除等基本运算及附加运算;
  • 执行所有的逻辑运算,并进行逻辑测试,如与、或、非、零值测试或两个值的比较等。

总结起来就是如下的一个流程:

光看CPU貌似我们已经了解了基本原理,其实最需要了解的其实是各个模块之间的交互,因为外部之间的IO是最容易产生瓶颈与疑惑的,所以接下来我们得学习下 CPU与内存及其他设备的交互等!

编码与字符

字符(集):中

字节:对应的二进制流byte

字符串(编码):字符与字节的映射关系:ANSI(多字节)字符串,Unicode (宽字节)字符串,(ANSI:0.一个字符可能是多个字节存储,1.不通国家字符集不一样,会有相同的字节映射,2.同一字符,不通编码规范 也可能对应不同的字符。)(Unicode :0.不同国家的字符集,不会有冲突的字节映射,是唯一的1.不同编码规范,最终可能对应不同的字符(为了省字节会添加一些识别信息,但去掉这些识别信息最终的值是一样的))

编码规范:同一编码的不通实现方式:UTF-8:可变长,节省Unicode 编码字符的空间。

编码转换:

把 UNICODE 字符串通过 ANSI 编码转化为“字节串”时,根据各自编码的规定,一个 UNICODE 字符可能转化成一个字节或多个字节。
反之,将字节串转化成字符串时,也可能多个字节转化成一个字符。比如,[0xD6, 0xD0] 这两个字节,通过 GB2312 转化为字符串时,将得到 [0x4E2D] 一个字符,即 ‘中’ 字。
“ANSI 编码”的特点:
1. 这些“ANSI 编码标准”都只能处理各自语言范围之内的 UNICODE 字符。
2. “UNICODE 字符”与“转换出来的字节”之间的关系是人为规定的。

比较懒,转一篇文章吧。

今天中午,我突然想搞清楚Unicode和UTF-8之间的关系,于是就开始在网上查资料。

结果,这个问题比我想象的复杂,从午饭后一直看到晚上9点,才算初步搞清楚。

下面就是我的笔记,主要用来整理自己的思路。但是,我尽量试图写得通俗易懂,希望能对其他朋友有用。毕竟,字符编码是计算机技术的基石,想要熟练使用计算机,就必须懂得一点字符编码的知识。

1. ASCII码

我们知道,在计算机内部,所有的信息最终都表示为一个二进制的字符串。每一个二进制位(bit)有0和1两种状态,因此八个二进制位就可以组合出256种状态,这被称为一个字节(byte)。也就是说,一个字节一共可以用来表示256种不同的状态,每一个状态对应一个符号,就是256个符号,从0000000到11111111。

上个世纪60年代,美国制定了一套字符编码,对英语字符与二进制位之间的关系,做了统一规定。这被称为ASCII码,一直沿用至今。

ASCII码一共规定了128个字符的编码,比如空格”SPACE”是32(二进制00100000),大写的字母A是65(二进制01000001)。这128个符号(包括32个不能打印出来的控制符号),只占用了一个字节的后面7位,最前面的1位统一规定为0。

2、非ASCII编码

英语用128个符号编码就够了,但是用来表示其他语言,128个符号是不够的。比如,在法语中,字母上方有注音符号,它就无法用ASCII码表示。于是,一些欧洲国家就决定,利用字节中闲置的最高位编入新的符号。比如,法语中的é的编码为130(二进制10000010)。这样一来,这些欧洲国家使用的编码体系,可以表示最多256个符号。

但是,这里又出现了新的问题。不同的国家有不同的字母,因此,哪怕它们都使用256个符号的编码方式,代表的字母却不一样。比如,130在法语编码中代表了é,在希伯来语编码中却代表了字母Gimel (ג),在俄语编码中又会代表另一个符号。但是不管怎样,所有这些编码方式中,0–127表示的符号是一样的,不一样的只是128–255的这一段。

至于亚洲国家的文字,使用的符号就更多了,汉字就多达10万左右。一个字节只能表示256种符号,肯定是不够的,就必须使用多个字节表达一个符号。比如,简体中文常见的编码方式是GB2312,使用两个字节表示一个汉字,所以理论上最多可以表示256×256=65536个符号。

中文编码的问题需要专文讨论,这篇笔记不涉及。这里只指出,虽然都是用多个字节表示一个符号,但是GB类的汉字编码与后文的Unicode和UTF-8是毫无关系的。

3.Unicode

正如上一节所说,世界上存在着多种编码方式,同一个二进制数字可以被解释成不同的符号。因此,要想打开一个文本文件,就必须知道它的编码方式,否则用错误的编码方式解读,就会出现乱码。为什么电子邮件常常出现乱码?就是因为发信人和收信人使用的编码方式不一样。

可以想象,如果有一种编码,将世界上所有的符号都纳入其中。每一个符号都给予一个独一无二的编码,那么乱码问题就会消失。这就是Unicode,就像它的名字都表示的,这是一种所有符号的编码。

Unicode当然是一个很大的集合,现在的规模可以容纳100多万个符号。每个符号的编码都不一样,比如,U+0639表示阿拉伯字母Ain,U+0041表示英语的大写字母A,U+4E25表示汉字”严”。具体的符号对应表,可以查询unicode.org,或者专门的汉字对应表

4. Unicode的问题

需要注意的是,Unicode只是一个符号集,它只规定了符号的二进制代码,却没有规定这个二进制代码应该如何存储。

比如,汉字”严”的unicode是十六进制数4E25,转换成二进制数足足有15位(100111000100101),也就是说这个符号的表示至少需要2个字节。表示其他更大的符号,可能需要3个字节或者4个字节,甚至更多。

这里就有两个严重的问题,第一个问题是,如何才能区别Unicode和ASCII?计算机怎么知道三个字节表示一个符号,而不是分别表示三个符号呢?第二个问题是,我们已经知道,英文字母只用一个字节表示就够了,如果Unicode统一规定,每个符号用三个或四个字节表示,那么每个英文字母前都必然有二到三个字节是0,这对于存储来说是极大的浪费,文本文件的大小会因此大出二三倍,这是无法接受的。

它们造成的结果是:1)出现了Unicode的多种存储方式,也就是说有许多种不同的二进制格式,可以用来表示Unicode。2)Unicode在很长一段时间内无法推广,直到互联网的出现。

5.UTF-8

互联网的普及,强烈要求出现一种统一的编码方式。UTF-8就是在互联网上使用最广的一种Unicode的实现方式。其他实现方式还包括UTF-16(字符用两个字节或四个字节表示)和UTF-32(字符用四个字节表示),不过在互联网上基本不用。重复一遍,这里的关系是,UTF-8是Unicode的实现方式之一。

UTF-8最大的一个特点,就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号,根据不同的符号而变化字节长度。

UTF-8的编码规则很简单,只有二条:

1)对于单字节的符号,字节的第一位设为0,后面7位为这个符号的unicode码。因此对于英语字母,UTF-8编码和ASCII码是相同的。

2)对于n字节的符号(n>1),第一个字节的前n位都设为1,第n+1位设为0,后面字节的前两位一律设为10。剩下的没有提及的二进制位,全部为这个符号的unicode码。

下表总结了编码规则,字母x表示可用编码的位。

Unicode符号范围 | UTF-8编码方式
(十六进制) | (二进制)
——————–+———————————————
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

跟据上表,解读UTF-8编码非常简单。如果一个字节的第一位是0,则这个字节单独就是一个字符;如果第一位是1,则连续有多少个1,就表示当前字符占用多少个字节。

下面,还是以汉字”严”为例,演示如何实现UTF-8编码。

已知”严”的unicode是4E25(100111000100101),根据上表,可以发现4E25处在第三行的范围内(0000 0800-0000 FFFF),因此”严”的UTF-8编码需要三个字节,即格式是”1110xxxx 10xxxxxx 10xxxxxx”。然后,从”严”的最后一个二进制位开始,依次从后向前填入格式中的x,多出的位补0。这样就得到了,”严”的UTF-8编码是”11100100 10111000 10100101″,转换成十六进制就是E4B8A5。

6. Unicode与UTF-8之间的转换

通过上一节的例子,可以看到”严”的Unicode码是4E25,UTF-8编码是E4B8A5,两者是不一样的。它们之间的转换可以通过程序实现。

在Windows平台下,有一个最简单的转化方法,就是使用内置的记事本小程序Notepad.exe。打开文件后,点击”文件”菜单中的”另存为”命令,会跳出一个对话框,在最底部有一个”编码”的下拉条。

bg2007102801.jpg

里面有四个选项:ANSI,Unicode,Unicode big endian 和 UTF-8。

1)ANSI是默认的编码方式。对于英文文件是ASCII编码,对于简体中文文件是GB2312编码(只针对Windows简体中文版,如果是繁体中文版会采用Big5码)。

2)Unicode编码指的是UCS-2编码方式,即直接用两个字节存入字符的Unicode码。这个选项用的little endian格式。

3)Unicode big endian编码与上一个选项相对应。我在下一节会解释little endian和big endian的涵义。

4)UTF-8编码,也就是上一节谈到的编码方法。

选择完”编码方式”后,点击”保存”按钮,文件的编码方式就立刻转换好了。

7. Little endian和Big endian

上一节已经提到,Unicode码可以采用UCS-2格式直接存储。以汉字”严”为例,Unicode码是4E25,需要用两个字节存储,一个字节是4E,另一个字节是25。存储的时候,4E在前,25在后,就是Big endian方式;25在前,4E在后,就是Little endian方式。

这两个古怪的名称来自英国作家斯威夫特的《格列佛游记》。在该书中,小人国里爆发了内战,战争起因是人们争论,吃鸡蛋时究竟是从大头(Big-Endian)敲开还是从小头(Little-Endian)敲开。为了这件事情,前后爆发了六次战争,一个皇帝送了命,另一个皇帝丢了王位。

因此,第一个字节在前,就是”大头方式”(Big endian),第二个字节在前就是”小头方式”(Little endian)。

那么很自然的,就会出现一个问题:计算机怎么知道某一个文件到底采用哪一种方式编码?

Unicode规范中定义,每一个文件的最前面分别加入一个表示编码顺序的字符,这个字符的名字叫做”零宽度非换行空格”(ZERO WIDTH NO-BREAK SPACE),用FEFF表示。这正好是两个字节,而且FF比FE大1。

如果一个文本文件的头两个字节是FE FF,就表示该文件采用大头方式;如果头两个字节是FF FE,就表示该文件采用小头方式。

8. 实例

下面,举一个实例。

打开”记事本”程序Notepad.exe,新建一个文本文件,内容就是一个”严”字,依次采用ANSI,Unicode,Unicode big endian 和 UTF-8编码方式保存。

然后,用文本编辑软件UltraEdit中的”十六进制功能”,观察该文件的内部编码方式。

1)ANSI:文件的编码就是两个字节”D1 CF”,这正是”严”的GB2312编码,这也暗示GB2312是采用大头方式存储的。

2)Unicode:编码是四个字节”FF FE 25 4E”,其中”FF FE”表明是小头方式存储,真正的编码是4E25。

3)Unicode big endian:编码是四个字节”FE FF 4E 25″,其中”FE FF”表明是大头方式存储。

4)UTF-8:编码是六个字节”EF BB BF E4 B8 A5″,前三个字节”EF BB BF”表示这是UTF-8编码,后三个”E4B8A5″就是”严”的具体编码,它的存储顺序与编码顺序是一致的。

9. 延伸阅读

* The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets(关于字符集的最基本知识)

* 谈谈Unicode编码

* RFC3629:UTF-8, a transformation format of ISO 10646(如果实现UTF-8的规定)

(完)

计算机原理(七)-进程内存管理分段

我们知道,进程都有独立的虚拟内存空间,跟物理内存一样,因为物理内存大小有限定,存在被覆盖的风险,所以现代CPU一般通过虚拟内存通过MMU进行页表的映射管理。而进程内的空间也一样,因为编译程序的时候,进程内也需要生成各个虚拟地址表,而每个表的大小不固定,可能就会覆盖其他表的地址,而这时,采用的解决方案是早期A-16位内存采用的分段方式,防止被覆盖。

分段原因

在编译过程中会建立许多的表,来确定代码和变量的虚拟地址:

  • 被保存起来供打印清单的源程序正文;
  • 符号表,包含变量的名字和属性;
  • 包含所有用到的整形和浮点型数据的表;
  • 语法分析树,包括程序语法分析的结果;
  • 编译器内部过程调用的堆栈。

前面4张表会随着编译的进行不断增大,而堆栈的数据也会变化,现在的问题就是,每一张表的大小都不确定,那么如何指定每一张表在虚拟内存空间的地址呢?

 

分段作用

分页实际是一个纯粹逻辑上的概念,因为实际的程序和内存并没有被真正的分为了不同的页面。而分段则不同,他是一个逻辑实体。一个段中可以是变量,源代码或者堆栈。一般来说每个段中不会包含不同类型的内容。而分段主要有以下几个作用:

  1. 解决编译问题: 前面提到过在编译时地址覆盖的问题,可以通过分段来解决,从而简化编译程序。
  2. 重新编译: 因为不同类型的数据在不同的段中,但其中一个段进行修改后,就不需要所有的段都重新进行编译。
  3. 内存共享: 对内存分段,可以很容易把其中的代码段或数据段共享给其他程序,分页中因为数据代码混合在一个页面中,所以不便于共享。
  4. 安全性: 将内存分为不同的段之后,因为不同段的内容类型不同,所以他们能进行的操作也不同,比如代码段的内容被加载后就不应该允许写的操作,因为这样会改变程序的行为。而在分页系统中,因为一个页不是一个逻辑实体,代码和数据可能混合在一起,无法进行安全上的控制。
  5. 动态链接: 动态链接是指在作业运行之前,并不把几个目标程序段链接起来。要运行时,先将主程序所对应的目标程序装入内存并启动运行,当运行过程中又需要调用某段时,才将该段(目标程序)调入内存并进行链接。可见,动态链接也要求以段作为管理的单位。
  6. 保持兼容性

所以在现在的x86的体系结构中分段内存管理是必选的,而分页管理则是可选的。

计算机原理-X86 CPU和内存管理(六)

这里主要简单介绍下32位处理器的内存访问,内存管理以及应用程序的内存布局。而32位CPU主要就是从intel 的80386架构CUP开始的,这也是我们最开始熟悉的CPU。而CPU最直接的作用就是 取指令、指令译码、执行指令、访存取数和结果写回。说白了就是对指令进行操作。而前面的可执行程序在CPU看来就是编译好的指令集合及数据集合。

其总图可以抽象为如下:

image

我们分别看看CPU及内存的一些操作细节:

一.32CPU
CPU架构

从80386开始,地址线变为了32位,和CPU寄存器以及运算单元位数一样,最大寻址范围增加到4G。另外80386处理器都可以支持虚拟存储器,支持多任务。 而之后的CPU,主要的改进就在于:

  1. CPU内部集成DMA,计数器,定时器等;
  2. 制造工艺的提示,更多的晶体管,更快的速度
  3. 加入更多的指令集,如MMX,SSE,SSE2等
  4. 集成L1,L2,L3高速缓存,减少外部总线的访问
  5. 超线程,多核心提高CPU效率
CPU内存访问方式

80386引入多任务后,内存管理方式有如下方式:

  1. 地址空间:这个是对物理内存的一个抽象,就好像进程是对CPU的一个抽象。一个进程可用于寻址的一套地址的集合,每个进程都有自己的地址空间,相互独立,这就解决了安全问题。
  2. 交换:把程序全部加载到内存,当进程处于空闲时,把他移除内存,存放到硬盘上,然后载入其他程序。这样使得每个进程可以使用更多的内存。
  3. 虚拟内存:利用到计算机系统的局部性和存储分层,我们可以只加载一部分需要使用的代码和数据到内存,当访问的内容不在内存时,和已经使用完的部分进行交换,这样就能在小内存的机器上运行大的程序了。对于程序来说这是透明的,看起来自己好像使用了全部内存。而多个应用完全可以使用相同的虚拟地址。
  4.  

    由于上面内存管理方式,产生了如下的内存访问方式:

虚拟寻址

CPU在内部增加了一个MMU(Memory Management Unit)单元来管理内存地址的转换。除了可以转换地址,还能提供内存访问控制。如操作系统固定使用一段内存地址,当进程请求访问这一段地址时,MMU可以拒绝访问以保证系统的稳定性。而MMU的翻译过程则需要操作系统的支持。所以可见硬件和软件在计算机发展过程中是密不可分的。

CPU寄存器

通用寄存器 ,指令指针寄存器。。。

二.虚拟内存

他就是现在保护模式下的内存获得方式,它的基本思想是:

  • 每个进程都有自己的地址空间;
  • 每个地址空间被分为多个块,每个块称为页,每个页有连续的地址空间;
  • 这些页被映射到物理内存,但不是所有也都在内存中程序才能运行;
  • 当使用的页不在物理内存中时,由操作系统负责载入相应的页;//运行时映射

虚拟地址(线性地址),虚拟地址就是同上CPU的MMU将虚拟地址映射为物理地址,然后送到总线,进行内存访问。这里最关键的就是虚拟地址的映射。

内存分页

对于虚拟内存来说,是对物理内存的抽象,整个虚拟内存空间被划分成了多个大小固定的页(page),每个页连续的虚拟地址,组合成了一个完整的虚拟地址空间。同样,操作系统也会把物理内存划分为多个大小固定的块,我们称为页框(page frame),它只是操作系统为了方便管理在逻辑上的划分的一个数据结构,并不存放实际内存数据,但是我们可以简单的认为它就是内存。这样一个虚拟内存的page就可以和一个物理内存的page frame对应起来,产生映射关系。

关于一个虚拟页的大小,现在的操作系统中一般是512B-64K(准确的说是地址范围大小,而非容纳数据的大小)。但是内存页的大小会对系统性能产生影响,内存页设得太小,内存页会很多,管理内存页的数组会比较大,耗内存。内存页设大了,因为一个进程拥有的内存是内存页大小的整数倍,会导致碎片,即申请了很多内存,真正用到的只有一点。目前Windows和Linux上默认的内存页面大小都是4K。

从上图我们也可以看出,虚拟内存的页和物理内存的页框并不一定是一一对应的,虚拟内存的大小和系统的寻址能力相关,也就是地址线的位数,而物理内存的页框数取决于实际的内存大小。所以可能只有一部分页有对应的页框,而当访问的数据不在物理内存中时就会出现缺页,这个时候操作系统会负责调入新的页,也就是建立新的映射。这样就不需要一次把程序全部加载到内存。

存储分页

加载应用程序到内存时,因为和虚拟地址有关,我们需要把应用程序文件和虚拟内存关联起来,在Linux中称为存储器映射,同时提供了一个mmap的系统调用来实现次功能。文件被分成页面大小的片,每一片包含一个虚拟页面的内容,因为页面调度程序是按需求调度,所以在这些虚拟页面并没有实际的进入内存,而是在CPU发出访问请求时,会创建一个虚拟页并加载到内存。我们在启动一个进程时,加载器为我们完成了文件映射的功能,所以此时我们的执行文件又可以称为映像文件。实际上加载器并不真正负责从磁盘加载数据到内存,因为和虚拟内存建立了映射关系,所以这个操作是虚拟内存自动进行的。 正是有了存储器映射的存在,使得我们可以很方便的将程序和数据加载到内存中。

MMU映射方式

如何将虚拟页映射到物理页中,MMU通过页表映射,页表是实时在内存中的,而虚拟页是运行时通过页表映射到实际的物理内存页上的。

页表分级

为了解决页表占用内存过多的问题,引入了分级页表

页表缓冲区

虚拟地址转换时,一次内存访问查找页表的过程。我们知道内存速度比CPU慢很多,每次从内存取数据都要访问2次内存,会使得系统性能下降。为了解决这个问题,在MMU中包含了一个关于PTE的缓冲区TLB(Translation Lookaside Buffer ),TLB是一个寄存器,所以它运行的速度和CPU速度相同。每次在去页表中查找之前,可以先在TLB中进行查找,如果命中则直接拿到物理页地址,如果不命中则再次访问内存。

进程调度和虚拟内存

我们知道在系统中,每个进程都有自己独立的虚拟空间,于是每个进程都有一张属于自己的内页表。 而我们翻译地址时,从cr3中取出页表目录的首地址。对于不同的进程,他们都使用同一个寄存器。于是在CPU调度进程的时候,虚拟的地址空间也需要切换。于是对于普通用户程序需要做下面几件事情:

  1. 保存当前进程的页表目录地址,也就是保存cr3中存放的地址到进程上下文中
  2. 清空TLB中缓存的数据
  3. 调度新的进程到CPU,并设置cr3寄存器的值为页表目录的首地址

但是内存中除了用户程序之外还存在操作系统自身占用的内存。我们可以简单的把操作系统看成一个超大的进程,他和其他普通进程一样需要使用虚拟内存,需要使用到页表。当然作为内核程序,它必须是有一些特权的,下一篇我们将会介绍虚拟内存的布局。而对于内核而言不是存在进程调度的。因为所有的内核进程都是共享内核的虚拟地址空间,而我们一般都称之为内核线程,而非进程。 当然对于Linux而言,没有线程的概念,线程和进程唯一不同就是是否共享虚拟地址空间。一般来说内核代码是常驻在内存的,那么内核会不会缺页呢?

STL容器解析

C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树(红黑树)等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

一.使用原则

当对象很大时,建立指针的容器而不是对象的容器

1 STL基于拷贝的方式的来工作,任何需要放入STL中的元素,都会被复制。

2 只涉及到指针拷贝操作, 没有额外类的构造函数和赋值构造函数的调用;

3.对象是指针的话,容器销毁前需要自行销毁指针所指向的对象;否则就造成了内存泄漏;

4.对象是指针的话, 使用排序等算法时,需要构造基于对象的比较函数,如果使用默认的比较函数,其结果是基于指针大小的比较,而不是对象的比较;

二.使用场景

deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。
vector与deque的比较:
一:vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置却是不固定的。
二:如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
三:deque支持头部的快速插入与快速移除,这是deque的优点。
list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。
map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。

数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于顺序存储结构的序列,这样才能O(1)找到其中间值。但是这样一来,其插入,删除会变得比较低效,鱼熊不可兼得。

B树(二叉查找树)算法

其查找效率与树的深度有关。

HASH查找

算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

算法流程:

1)用给定的哈希函数构造哈希表;

2)根据选择的冲突处理方法解决地址冲突;

常见的解决冲突的方法:拉链法和线性探测法。 详细的介绍可以参见:  哈希表 。

3)在哈希表的基础上执行哈希查找。

这也是用空间换时间的例子之一。所以哈希表是查询效率的极致了。但是要解决好健冲突问题,比如拉链法,相当于将有共同哈希值的数据存储到一个链上,哈希值索引指向这个链,如果链COUNT>1,则再在链上顺序查找,这也有分治法的应用效果,基本上std::map 这种 kv存储结构就是哈希表的应用。这还可以衍生出进行大数据外排查找Top K问题。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

拉链法实现的哈希表应该也算是一个分块查找,索引查找的实现方式

分块查找(索引查找)

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

这种也适合使用并行进行查找。

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。

数据结构与算法(四)排序

根据待排序数据量能否被全部装载到内存中进行排序分为:内部排序外部排序。当然我们都希望直接在内存中进行排序,因为IO的延迟非常的大,但对于大数据集来说,内存是远远不够的,这时候就涉及到外排序,外排序通过读/写外存的次数来衡量其效率。基本上上学的时候学的都是内部排序,同时万不得已,都尽量使用内部排序,或者转化为内部排序。其实也就是说,我们要以空间换时间,以稳定性换时间,所以如何选择排序方法要综合场景来进行

一.基本排序

http://ibinguo.net/wp-content/uploads/2016/12/image_thumb8.png

image

冒泡排序->快速排序->归并排序

冒泡排序是最基本的排序算法,遍历所有数据,一次遍历查出最大值。所以如果要查询某个最大值也可以使用下冒泡。但是这个速度不敢恭维,所以有了变种快速排序,当然是以牺牲部分空间及稳定性为条件的。

快速排序快排是基础单线程排序中效率最好的了。以分治的思想进行排序,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

 

插入排序->希尔排序->并归排序

插入排序:遍历剩余所有数据,遍历待排序数据,将数据插入到一个已排序好的队列中,该已排序好的队列慢慢增大。

插入排序是每次将一个数据插入待排序序列,即步长为1希尔排序也可称为分组插入方法,则是步长>1,每个分组内使用插入排序或者二分插入排序。

并归排序:

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。直到得到长度为n的有序表,排序结束。
归并操作的工作原理如下:

  1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2、设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4、重复步骤3直到某一指针达到序列尾

堆排序

堆实际上是一棵完全二叉树,利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

二.适用场景

综合上述,得到的各种情况下的最优排序分别是:

(1)序列完全有序,或者序列只有尾部部分无序,且无序数据都是比较大的值时, 【直接插入排序】最佳(哪怕数据量巨大,这种情形下也比其他任何算法快)

(2)数据基本有序,只有少量的无序数据零散分布在序列中时,【希尔排序】最佳

(3)数据基本逆序,或者完全逆序时,  【希尔排序】最佳(哪怕是数据量巨大,希尔排序处理逆序数列,始终是最好的,当然三数取中优化的快速排序也工作良好)

(4)数据包含大量重复值,【希尔排序】最佳(来自实验测试,直接插入排序也表现得很好)

(5)数据量比较大或者巨大,单线程排序,且较小几率出现基本有序和基本逆序时,【快速排序】最佳

(6)数据量巨大,单线程排序,且需要保证最坏情形下也工作良好,【堆排序】最佳

(7)数据量巨大,可多线程排序,不在乎空间复杂度时,【归并排序】最佳

 

三.

数据结构与算法(三)树

这一节我们专门来看看树吧,因为这个的应用也是非常广泛。基本的就是二叉查找树,因为二叉查找树可能会出现跛脚的情况,一边长,一边短,所以就出现了平衡二叉树,根据其实现又有AVL树,红黑树。

1.二叉树查找树

定义

对于任何一个结点X

若它的左子树非空,则左子树上所有结点的值均小于等于X的值;             

若它的右子树非空,则右子树上所有结点的值均大于等于X的值;

遍历:

前序遍历:根节点->左子树->右子树

中序遍历:左子树->根节点->右子树

后序遍历:左子树->右子树->根节点

例如:求下面树的三种遍历


前序遍历:abdefgc

中序遍历:debgfac

后序遍历:edgfbca

按中序遍历二叉查找树,所得到的中序遍历序列是一个递增(或递减)的有序序列。

我们来说二叉查找树当然是和查找操作有关系,查找的时间复杂度是和高度H成正比的:log(h)。也可以这么说,二叉查找树基本操作的时间都是和树的高度H是成正比的。这些基本操作包括查找插入和删除,前驱后继等。遍历不在这里讲,以后会专门写有关遍历的文章,BFS,DFS,无栈非递归等。

查找

我们先来看一下查找:给定一个树的树根指针x和关键字k,返回指向关键字的指针,否则返回NIL。 TREE-SEARCH(x,k)伪代码

在递归查找的过程中遇到的结点即构成了一条由树根下降的路径,故TREE-SEARCH的时间复杂度是O(H)。

再来一个非递归版本的ITERATIVE-TREE-SEARCH,这个比递归的要快一些。


最大值和最小值

那么如何去找最大值和最小值呢?最大值肯定是二叉树的最右结点啦,从根结点开始沿着right指针一路走到right指针为空。而最小值肯定在最左结点,从根结点沿着left指针一路走到left指针为空。(此时说的二叉树是按中序遍历是从小到大)

	时间复杂度都是O(H),因为寻找的过程就是根结点一路下降的过程。

前驱和后继

找到最大值和最小值还不够,有时候我们需要寻找前驱和后继。如何寻找呢?我们这里来讲述一下中序遍历的的前驱和后继寻找。后序遍历和前序遍历的前驱后继的寻找和这是一样的道理。
后继
先说后继,对于一个结点X来说,后继无非是有3种情况: 1  X有右孩子,那么X的后继就是右孩子的最左结点。 2  X无右孩子,而且X是其父母的左孩子,那么X后继就是其父母结点(可能NIL)。 3  X无右孩子,而且X是其父母的右孩子,那么X的后继就是X的某个祖先(这个最低祖先的左孩子也是X的祖先),此时让父母成为新的X,寻找不断找X是其父母的左孩子的结点,如果此时出现一个X结点是其父母左孩子,那个父母就是X的后继。这个意思也就是说把第三种情况变成第二种情况。如果这个时候找不到则得到的是NIL结点。因为最大值是没有后继的,其他的肯定都有。 对于第一种情况很简单

对于第二种情况,更简单了,可能父母是NIL,即X结点是根结点。

对于第三种情况,找不到的话就是NIL。最大值没有后继。

伪代码

前驱
	再来看一下前驱,前驱和后继是对称的。如果你仔细看,你会发现刚才寻找后继2 、3 情况的过程是X一直向上查找X是否是其父母的左孩子,而此时X的前驱的分类是和他对称的,是一直向上寻找看X是否是其父母的右孩子,那么其父母就是其前驱。
	1  X有左孩子,那么X的前驱就是左孩子的最右结点。
	2  X无左孩子,而且X是其父母的右孩子,那么X前驱就是其父母结点(可能NIL)。
	3  X无左孩子,而且X是其父母的左孩子,那么X的前驱就是X的某个祖先(这个最低祖先的右孩子也是X的祖先),此时让父母成为新的X,寻找不断找X是其父母的右孩子的结点,如果此时出现一个X结点是其父母右孩子,那个父母就是X的前驱。这个意思也就是说把第三种情况变成第二种情况。如果这个时候找不到则得到的是NIL结点。最小值没有前驱。
对应第一种情况

对应于第二种情况,父母可能是NIL。

对应于第三种情况,找不到是NIL。最小值没有前驱。

伪代码
TREE-PREDECESSOR(x)
1 if left[x]≠NIL
2    then return TREE-MAXIMUM(left[x])
3 y←p[x]
4 while y≠NIL and x=left[y]
5      do  x←y
6          y←p[y]
7 return y
	时间复杂度都是O(H),就是一条自结点向上的路径罢了。
	综上所述 对于一颗高度为H的二叉查询树来说,静态操作SEARCH,MINIMUN,MAXIMUM,SUCCESSOR,PREDECESSOR等用时都是O(H)。
	对于一颗二叉树,要的不仅仅是静态操作,还需要动态操作。因为必然会有插入和删除操作,而且还要保持二叉排序树的性质。

插入

先来看如何插入结点Z,插入很简单的。先把结点Z的左右孩子left[z] 、right[z]和父母p[z]初始化,然后从根结点开始一直向下寻找Z的父母,找到之后就把孩子Z插入,如果是空树,直接把Z当成根结点。 在伪代码中,X初始化为根结点,Y始终是其父母,最后把Z插入。

TREE-INSERT的时间复杂度是O(H)。

删除

插入结点很简单,那么如何删除结点呢?删除结点之后还要保持中序遍历是一个相对位置不变的序列。对于删除一个结点Z,其实是要分类的。 1 如果Z没有孩子,直接删除,仅仅修改其父结点P[Z]的孩子为NIL即可。 2 如果Z仅仅只有一个孩子,那么删除Z之前要把Z的孩子赋值给其父母P[Z]的孩子(左|右)。这样一个拉链直接去删除Z了。 3 如果Z有两个孩子,这样就有点麻烦了。因为删除Z之后还有两个孩子,如果不好好处理会破坏二叉树的性质,我们删除Z一定要保持中序遍历的相对位置序列不变。这样有两种方法,因为只有保持性质即可,两种方法得来的二叉树不一定是一样的,但是都是正确的二叉树。 我们来看一下第三种情况的两种方法:假设删除的结点是P,而且中序遍历的序列是{....CL ,C....  QL,Q,SL,S,P,PR,F}删除P之后的中序遍历序列应该是{....CL ,C....  QL,Q,SL,S,PR,F}。S是P的前驱,PR是P的后继。

这就是未删除P之前的二叉树原型。
方法一
第一种方法是,先把P的前驱S的左孩子SL(S肯定无右孩子,左孩子可能是NIL)变成S父母Q的右孩子,删除S。然后把S的值全部给P,这就让P前驱S取代了P的位置,这样序列相对位置没有发生变化。

	可是真的是这样吗?这是老严数据结构书上的截图,算导上给的是找后继结点,然后和上边说的一样,就是把刚才的前驱换成后继。
	可是我想说的是这里忽略了一种情况,那就是如果前驱是其左孩子了怎么办?根据之前分析的前驱分类,在这里要删除的结点P肯定有两个孩子,那么对于前驱来说就只有两种情况,如果P前驱是左孩子的最右结点,刚才的分析没有一点问题,可是如果P前驱是其左孩子,也就是说左子树根结点没有右子树。那么按刚才的分析 就是说不通了。前驱S是P的左孩子,你还要把S的左孩子变成S的父母(P)的右孩子吗?那之前P的右孩子岂不是丢了??!!
	所以这个时候你要判断一点就是P前驱是否是P的左孩子,就是在找前驱的时候保留一个指针指向前驱的父母,最后判断是否和P相等,如果相等就把P左孩子的左孩子变成P的左孩子,然后P的左孩子(此时也是前驱)覆盖P。如果不相等,就按刚才说的做。
	算导给的,和这是一样的,只不过是对称找后继,如果后继是其右孩子也是尴尬。也可以和刚才一样,留个指针判断。
	我们要分类判断,如果判断得到P的前驱是其左孩子的话,那么直接将前驱取代P就好了,其他什么都不用做。或者像算导上说的找后继,后继是其右孩子的话就让后继取代他。也就是说如果一个结点的前驱或者后继是其孩子的话,直接让其孩子取代他就好了,很简单的,其他什么都不用做。
	不能想当然的以为前驱一定是左孩子的左右结点,后继一定是右孩子的最左结点。这样就算是前驱不是其左孩子,只要后继是其右孩子,就让右孩子取代他,两个孩子满足一个就可以减少很多的处理,优化算法,而且此时不必留指针再判断了。如何判断呢?如果P的左孩子没有右子树,那前驱就是左孩子。如果他的右孩子没有左子树,那后继就是其右孩子。
伪代码
TREE-DELETE(T,z)
1 if left[z]=NIL or right[z]=NIL
2    then if left[z]=NIL
3            then  p[right[z]]=p[z]
4                  left[p[z]]=right[z]
5         else if right[z]=NIL
6            then p[left[z]]=p[z]
7                 left[p[z]]=left[z]
8 else if  right[left[z]]=NIL
9  then key[z]=key[left[z]]
10              p[left[left[z]]]=z
11              left[z]=left[left[z]]
12 else if left[right[z]]=NIL
13         then p[right[right[z]]]=z
14              right[z]=right[right[z]]
15 else
16      then y=left[z]
17           while right[y]≠NIL
18                 y=right[y]
19           p[left[y]]=p[y]
20           right[p[y]]=left[y]
21           key[z]=key[y]
	这是一种分类的做法,老严给的版本是找后继判断,算导给的是找前驱判断,我这里给他综合了一下,更加的优化。不过算导版本虽然没有分类,但是有各种判断,代码很紧凑。虽然我感觉没我的好,不过还是在这里贴一下。

方法二
	接下来我们看第二种方法,这种方法的好处是不像刚才那么有BUG,不过好像大多数书上举的例子都是第一种,汗。难道第一种比第二种的简单?我们看一下吧
	先令P的右孩子PR成为其前驱S的右孩子,然后将P的左孩子C成为P父母F的左孩子,删除P。这样就不用管C是不是其前驱了。C就是其前驱也是把PR给C的右孩子,序列的相对位置是不会发生变化的。

来看一下伪代码
TREE-DELETE(T,z)
1 if  left[z]=NIL or right[z]=NIL
2     then if left[z]=NIL
3             then  p[right[z]]=p[z]
4                   left[p[z]]=right[z]
5          else if right[z]=NIL
6                  then p[left[z]]=p[z]
7                       left[p[z]]=left[z]
8  else  9       y=TREE-PREDECESSOR(z)
10      p[right[z]]=y
11      right[y]=right[z]
12      p[left[z]]=p[z]
13      left[p[z]]=left[z]	代码很简洁,我反倒觉得这个简单,还不麻烦。这两种方法都很简单的,一时想不起,就拿笔画一颗二叉树,很快就明白了。一定要动手画一下。时间复杂度很明显是O(H)。	上边所说的二叉树的大部分操作的时间复杂度都是O(H),H是树的高度。大家一听高度想当然以为就是lgN,其实非也。一个好的二叉树高度可能是O(lgN),即便是如此,可是经过了很多的插入和删除,高度就会发生变化。就像是一开始只有一个结点的二叉树,最后变成了一个高度为N-1的链。这虽然还是树,可是已经不是我们需要的了,时间复杂度太大了(O(N)).
	可是我们怎么才能保证一个树的高度是lg级的呢?随机。一个N个关键字随机的构造的二叉树的高度是lgN。可是经过删除和再次插入的洗礼,高度也不会一直是lgN。所以我们二叉树期望高度是O(lgN),平均时间复杂度是良好的,不过还是不可避免的是会出现最坏情况。这个时候我们就不能仅仅依靠随机了。

平衡二叉树

不过我们不会任由这种最坏情况的发生,我们可以对二叉树做一些平衡的处理,接下来就介绍一下平衡二叉树,这个在最坏情况的时间复杂度都是lg级。 平衡二叉树是为了避免刚才的最坏情况产生的,平衡是指所有的叶子的高度趋于平衡,更广义的是指在平衡二叉树上所有可能查找的均摊复杂度偏低。几乎所有平衡树的操作都基于树的旋转操作,通过旋转操作可以使得树趋于平衡。AVL树,红黑树,伸展树,Treap树等都是平衡二叉树。

AVL树

AVL树仅仅只是平衡二叉树的一种而已,具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵AVL树。若二叉树上结点的平衡因子定义为该结点的左子树的高度减去右子树的高度。那么AVL树的平衡因子就只能是0,-1,1。如果有一个结点的平衡因子的绝对值大于1 ,那么这个二叉树就不是AVL树。如果由于插入和删除结点导致AVL树不平衡,那么就从这个结点开始进行一次或多次的左右旋转和高度的调整,最后使二叉树变得平衡。 老严那本书上讲的平衡二叉树仅仅只是AVL算法的一种平衡二叉树而已,不代表全部的。注意平衡二叉树一种平衡树,而AVL算法只不过是调整树的高度保持平衡的算法而已,不是平衡二叉树的全部。平衡二叉树有很多种,这里我把一些以前的AVL笔记中中的旋转K过来看一下吧。

红黑树

这里我们主要是说一个特殊的平衡二叉树,那就是红黑树RB-TREE。RB-TREE的好处在于检索很快,主要用于关联式容器。Set map multiset  multimap的底层实现都是RB-TREE,这些关联容器存入的时候都是自动排序,查询的时候都是很快。不过代价就是RB-TREE树的插入和删除带来的麻烦很多,不过还好的是 它可以在O(log n)时间内做查找,插入和删除。 红黑树在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。每一个结点有5个域:color key  left  right  p。如果某个结点没有孩子或没有父结点,则把相应的结点设为NIL,颜色BLACK。 红黑树是每个结点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求(性质): 性质1. 每个结点只能是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子结点都是黑色(叶子是NIL结点)。 性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点) 性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

	在很多树数据结构的表示中,一个结点有可能只有一个子结点,而叶子结点包含数据。这种表示红黑树是可能的,但是这会改变一些属性并使算法复杂。为此,我们使用 NIL来表示叶子结点。如上图所示,它不包含数据而只充当树在此结束的指示。这些结点在绘图中经常被省略,导致了这些树好像同上述原则相矛盾,而实际上不是这样。与此有关的结论是所有结点都有两个子结点,尽管其中的一个或两个可能是空叶子NIL。有点时候为了节省内存把所有的NIL连在一起当成一个NIL[T]哨兵,代表所有的叶子NIL和父母结点是NIL的结点。
	结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
	要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个相连的红色结点就足够了。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。还有注意的是叶子节点都是NIL,它不包含数据而只充当树在此结束的指示。所以根据属性5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长。
	我们定义黑高度BH(X)为从结点X出发(不包括X)到叶子结点的任意一条路径上,黑色结点的个数。这样我们就会得到一个结论:一颗有N个结点(不包括NIL叶子)的红黑二叉树的高度至多是2lg(N+1)。
	简单证明一下:由于以X为根的RB-TREE至少包含2^BH(X)-1个结点。因为对于高度为0的RB树,结点数目是0,对于一个结点高度大于0的RB树,左右孩子的颜色可能是红,也可能是黑,所以孩子的黑高度BH有可能和父母一样,也有可能比父母少1。所以孩子的结点数目加上父母结点X就和X为根的RB树的结点数目是一样的,也就是说2^(BH(X)-1)-1+2^(BH(X)-1)-1+1=2^BH(X)-1,所以假设成功。此时呢,假设N个结点的RB树高度是H,则黑高度至少是H/2,所以呢,2^BH-1=2^(H/2)-1<=N,H<=2lg(N+1),得证。
	所以对于红黑树的所有动态和静态的操作都可以在O(lgN)时间内实现。
旋转
可是经过了删除和插入,红黑树的性质会发生变化,所以需要一些旋转操作和结点颜色的改变来维持性质。这里我们先来看一下旋转的知识。旋转分左旋和右旋。

	当在某个结点x上做左旋操作时,我们假设它的右孩子y不是NIL,x可以为RB树内任意右孩子而不是的结点。旋以x到y之间的链为“支轴”逆时针旋转,它使y成为该子树新的根,而y的左孩子b则成为x的右孩子。而右旋和左旋是对称的。Y的右孩子X也不是NIL,这时候以y到x之间的链为“支轴”逆顺时针旋转,使x成为新的子树的根,x的右孩子变成y的左孩子。因为左右对称,这里我们只给出左旋的伪代码。假设X的右孩子不等于NIL,而且根的父母结点是NIL。

	时间复杂度都是O(1),旋转的时候只有指针在变化,而其他的所有域都不会改变。至于RB树颜色的变化是和旋转无关的。还要明确一点的就是旋转不改变中序遍历的相对顺序
插入
现在就先说插入吧,因为插入毕竟比删除简单一些。在一个有N个RB树中插入一个结点可以在O(lgN)时间内完成。 插入一个结点肯定是要赋予颜色的,我们是给他红色,还是给他黑色呢? 5大性质: 性质1. 每个结点只能是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子结点都是黑色(叶子是NIL结点)。 性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点) 性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。 根据5大性质我们知道,如果把插入的结点赋予黑色,则会违反性质5,导致黑高度发生变化,这个是很麻烦的。待会删除的时候你就会明白。而如果赋予红色,则只会违反性质2和4,如果是性质2,说明插入的是根结点,直接把根结点变成黑色就好。如果违反性质4,说明插入结点的父节点是红色的,此时可以通过旋转和结点颜色的改变搞定,这个不是很麻烦。我们只讨论违反性质的情况,不违反的就不说了。我们来看一下。 RB-TREE的插入和之前的二叉查找树的插入代码有些不同,所有的NIL结点换成哨兵NIL[T],插入的结点初始化left和right都是哨兵NIL[T],颜色直接赋予红色。然后专门写一个调整算法RB-INSERT-FIXUP。这里我们只看调整算法,之前的插入我们已经讲过了,不明白看前面章节。 我们假设父节点是P,叔叔结点是U,祖父结点是G,插入结点是N。同时假设Z的父节点P是祖父G的左孩子,这和是右孩子是对称的,我们只讨论P是G左孩子的情况。 如何调整呢?我们要寻找一些辅助,父节点P肯定是要参与的,因为要看他是不是红色,红色的话就调整,不是红色的话直接给根结点变黑色(不判断都行),不管其他的。而且可以肯定是祖父节点G肯定是存在的,而且是黑色(NIL或者其他,因为插入之前肯定满足RB树的性质)。如果父结点P是红色,那么我们如何调整?因为除了根结点是黑色之外,其他的都不晓得,我们也不能随意的调整。
情况一
	我们不能贸然调整把插入结点N变成黑色,不过如果父结点的兄弟结点,也是插入结点N的叔叔结点U,他如果是红色的话。

	此时我们可以把U和P都变成黑色,但是此时以祖父的父节点G为根的子树的黑高度变化了,也即是+1了。这就违反了性质5,唉,千万不敢违反性质5,超级麻烦。所以我们做一个变通,可以把祖父结点G变成红色,此时的违反性质的可能性就落到了G身上,这时就把G当成插入结点N,继续进入调整算法开始调整。
	也就是说我们可以把这个插入结点N和父节点P的连续红色的违反情况向上移动,就是把违反性质的结点向上调整,这样直到最后变成根结点是红色的,根结点父节点是NIL[T]黑色,此时直接把根结点变成黑色即可,很nice。

	此时的G就变成了新的插入结点了,继续调整,最多到根结点。情况一:如果父节点P和叔父节点U二者都是红色,则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质5)。
	可是如果叔叔结点U是黑色呢?这就不能按刚才说的调整了,我们要换一个策略了。此时我们要分情况,插入结点N是父节点P的左孩子还是右孩子,这是不一样的。
情况三
如果N是P的左孩子

	此时我们直接把父节点P变成黑色,然后以G--P为轴顺时针旋转(右旋),P变成了根,但是G变成了P的右孩子,这个时候两边的黑高度就发生了变化,右边的+1了,此时我们可以把G变成红色,这样两边就均衡了啊。而且
此时算法直接就结束了,因为性质都保持住了。

情况二
可是如果N是P的右孩子呢?

	这样看起来很不好搞啊,旋转变色,都达不到要求,都是无用的。我们可以把这个N右孩子变成刚才说的左孩子吗?看起来是不可以。不过我们可以发现的是父母和孩子结点的变换是可以通过旋转来做的,也就是说通过一次旋转,孩子可以变成父母,父母也可以变成孩子,而新的孩子和之前的孩子的左右是相反的。而此时N和P都是红色,我们通过一次的左旋,可以把P变成N的左孩子,也就是相当于P变成插入结点是红色,N变成父节点是红色,叔叔结点U是黑色,则和刚才说的是一样的。

	也即是变成了刚才那种情况。所以我们把这种情况称为第二种,刚才说的是第三种。因为第二种到第三种是直接过度的,不是互斥的情况。虽然我们忘了一种情况,那就是叔叔不存在,但是这并不影响我们刚才分析的结果。
情况二:如果父节点P是红色而叔父节点U是黑色或不存在,并且插入节点N是其父节点P的右孩子。我们以P-N为轴进行一次左旋调换插入节点N和其父节点P的角色(不是颜色)

情况三::如果父节点P是红色而叔父节点U是黑色或不存在,并且插入节点N是其父节点P的左孩子。我们可以把P重绘为黑色,并重绘G为红色。然后以P-G为轴以进行一次左旋调换节点P和节点G的角色。
	情况一要进入继续调整,最坏的情况是向上调整到根。情况二直接进入情况三。情况三调整完了之后调整算法就结束了。
	上伪代码,这个伪代码和刚才分析的是一样的,如此同时还是只有半边代码,就是只有父节点P是祖父结点G的左孩子的情况。不过在伪代码里,插入结点是z,y是其叔叔。
INSERT伪代码

RB-INSERT-FIXUP伪代码

给一个例子看看,很好的例子,囊括了三种情况。
这是情况一的情况

情况一调整结果变成了情况二了。

情况二调整结果变成了情况三了。

情况三调整完了就结束了。

	很明显我们的RB-INSERT的1-16行的时间代价是(lgN),而对于RB-INSERT-FIXUP中,只有情况一才会发生循环,即便是循环到根,也不过用时O(lgN),所以总的时间花费就是O(lgN)。而且这个RB-INSERT-FIXUP过程的旋转不超过2次,也就是情况二和情况三各旋转一次O(1),旋转过后算法就结束了。
删除
接下来我们来看看如何删除RB-TREE的结点。
	对于一个有N个结点的RB-TREE来说,删除一个结点要花费的时间就是O(lgN)。与插入相比,只不过是更加的复杂罢了。我们来分析一下。删除一个二叉树的结点我们说过了,这里不再说,之说删除结点之后如何保持红黑树的5大性质。
5大性质:
	性质1. 每个结点只能是红色或黑色。
	性质2. 根结点是黑色。
	性质3. 所有叶子结点都是黑色(叶子是NIL结点)。
	性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
	性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。
	如果删除的结点的颜色是一个红色,我们压根就不需要调整,因为这并不违反任何一个性质。因为各结点黑高度没有变化,不存在相邻的红色结点,删除的也不是根结点。如果树的结点只有一个,那么删除了也不需要调整。如果树的结点不是一个而且删除的结点是黑色的,那么就有可能违反性质4,因为可能有两个相邻的红色结点。删除了根结点,造成新的根结点是红色可能违反了性质2。而且删除黑色的结点会违反性质5,导致黑高度不一致。
	我们如何调整呢?假设删除了结点Y,肯定有占用他位置的结点是X,X可能是他的前驱或后继,X也可能是Y的孩子,或者是哨兵NIL[T]结点。如果X结点本身是红色,也就是说有可能违反性质4和5,那我们直接赋予它黑色就解决了。如果红色结点X变成了根违反性质1,也直接赋予黑色就OK。现在的问题是如果X结点是黑色而且不是根结点,违反了性质5,黑高问题就不好解决了。这里我们主要说如何解决这一个情况,前两个情况很easy,不需细说了。
	之前说过如果违反了性质5,会很麻烦,这会你就知道了。违反了性质5,我就很拙计了。当然这也不是解决不了的。那如何保持性质5呢?我们总不能期望他不违反性质5吧。这里我们用一个技巧,就是假设删除的结点Y把它的黑色性质X结点了,也就是说X结点多了一重黑色,就是黑+黑,这样的话黑高度就一致了,性质5就满足了。
	当然这只是假设,我们假想的,不过这有助于我们解决问题。这个黑+黑结点是X结点,他的颜色属性还是黑色,只不过用一个指针指向他,他便多了一层黑色。不断调整的过程,会出现新的X结点,这时候指针指向的结点不一定会是原来的X了,不过还是会多一层黑色。而且在不断旋转的过程会出现旋转前后两边子树黑高发生变化的情况,此时如果N这边的子树黑高+1了,那N头上的多于黑色就没有了,舍弃。这就是我们的最终目的。
	这也就是调整的麻烦之处,接下来我们看看他如何麻烦。当然这还是要分类的。这里我们只考虑结点X是其父节点左孩子的情况,对称的情况不再讲。
	我们假设占用被删除结点的位置的结点是N,N的兄弟结点是S,N的父亲结点是P,S的左孩子是SL,S是右孩子是SR。要明确一点的是S不是NIL[T],因为如果是NIL[T],那两边的黑高现在就不一样,即便是没删除之前,RB-TREE也不会出现这种情况的。
情况一
如果兄弟结点S是红色,那么S的父亲结点P和S的孩子SL和SR都必然是黑色,此时N也是黑色的。

	此时如何调整?指针指向的是N,N是黑+黑。此时父亲结点P变红色,S变黑色,然后以P-S为轴左旋。此时指针指向的还是N,看起来好象是没什么变化,其实是变了,父亲结点P变成了红色,兄弟结点变成SL还是黑色。不要着急,这只是第一步而已嘛。

情况一:如果兄弟结点S是红色的(隐含的意思P,SL,SR都是黑色),那么我们就交换父节点P和兄弟结点S的颜色,即P变红色,S变黑色,然后以P-S为轴左旋。	如果兄弟结点是红色的话,只可能有这一种情况,因为父节点和孩子结点的颜色都是定好的黑色。接下来看兄弟结点是黑色的情况,这样他的孩子结点和父亲结点的颜色可就不唯一了,这可以分好几种情况的。
情况二
如果N的兄弟结点S是黑色的,而且两个孩子结点都是黑色的。N还是被指针指向,黑+黑。(P的颜色不晓得)

	如何调整?此时我们并不知道P的颜色,我们也不需要去判断。我们假设N和S都脱掉一层的黑色(两边路径上的黑色结点数还是相同),那N变成了正儿八经的黑色了,指针也不指向他了,而S脱掉黑色就只能变成了红色。而此时经过P的路径在这边少了一个黑色,黑高-1,所以我们要用指针指向他,给他多一层的黑色,这样经过P的路径在这边的黑色就不变了,这样多好。

	此时指针指向的是P(新的N)多了一层黑色,黑+黑或者是红+黑。有变化吗?当然了,看起来好像回到了情况一(兄弟S是红色),其实不是。因为新的N是P,这样指针指向的结点不断的向上移动,至多变成了根结点,那敢情好,直接赋予黑色,OK搞定。
情况二:如果兄弟结点S是黑色的,而且S的两个孩子也都是黑色的。直接把N变成黑色,S变成红色,用指针指向P,P多了一层黑色。
情况三
如果N的兄弟结点S是黑色,不过S的左孩子SL是红色的,右孩子SR是黑色的。

	那么如何调整?此时把SL和S的颜色交换,即SL变成黑色,S变成红色,然后以S-SL为轴右旋。此时N的兄弟变成了SL,而SL的右孩子变成了红色。

情况三:如果N的兄弟结点S是黑色,而且S的左孩子SL是红色的,右孩子SR是黑色的。此时把SL变成黑色,S变成红色,然后以S-SL为轴右旋。
情况四
此时N的兄弟S的右孩子就变成了红色,而左孩子不晓得。这种情况就是我们要说的情况四,情况三直接过渡到情况四,相互不排斥,其实是在一个分类里面。

	这样的话就是直接交换P和S的颜色,P变成黑色,而S变成P的颜色(不定),S的右孩子SR也变成黑色。然后以P-S为轴左旋。此时只有S的颜色不定,可是此时S的孩子都是黑色,S是什么色都无所谓了。此时算法就结束了,调整完毕。

算法为什么就结束了呢?因为调整的前后左边的子树的黑高+1了,所以此时N的多一层黑色就没用了,要舍弃。就是说我们解决了黑高的问题,性质5保持住了。
情况四:如果N的兄弟结点S是黑色,而且S的右孩子SR是红色的。那么交换P和S的结点颜色,即S变成P的颜色(不定),P变成黑色,SR变成黑色,然后以P-S为轴左旋。
	OK,大功告成一半,接下来上伪代码。伪代码中Y是要删除的结点,X是替代Y的结点,W是X的兄弟。调整算法是RB-DELETE-FIXUP。
RB-DELETE(T,x)
........
if color[y]=black
   then RB-DELETE-FIXUP(T,x)

     RB-DELETE-FIXUP的时间复杂度是O(lgN),因为只有情况二需要循环,循环次数最多是O(lgN)。情况 1 、3、 4最多需要旋转3次和一些颜色的改变而已。所以RB-DELETE-FIXUP过程要花费O(lgN)的时间,至多需要3次旋转。总的来说红黑树是很不错的,很快,所以很多容器的底层都用RB树。
	OK,这样红黑树就差不多说完了,以后有新的理解还会继续更新。