Shenlvmeng's Blog

引子

ECMAScript的变量是松散类型的，所谓松散类型就是可以用来保存任何类型的数据。换句话说，每个变量仅仅是一个用于保存值的占位符而已。

由于JavaScript是一种松散类型的语言，即变量在使用时，并不需要事先知道它的类型。因此不同变量间的比较往往要作类型转换，这也是一些常见quiz的由来。
比如下面的一道面试题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//请写出下面语句的输出结果
if ([]) console.log(1);               // 1
if ({}) console.log(2);               // 2
if ([] == true) console.log(3);       // 无
if ({} == true) console.log(4)；      // 无
if (null == undefined) console.log(5) // 5
if (NaN == NaN) console.log(6)        // 无
if ("5" == 5) console.log(7)          // 7
//下面的结果你能写出来么
console.log([] + {}); // "[object Object]"
console.log({} + []); // "[object Object]"
console.log({} - []); // -0
console.log([] - {}); // NaN
console.log([] + []); // ""
console.log([] - []); // 0
console.log({} + {}); // "[object Object][object Object]"
console.log({} - {}); // NaN
//下面的呢
typeof null           // "object"
typeof function () {} // "function"
[] instanceof Array   // "true"
{} instanceof Object  // "true"

怎么样？是不是有点晕，下面我们一部分一部分地来解释JavaScript中一些类型和相等相关的“潜规则”。

数据类型

让我们先从JavaScript的数据类型开始。JavaScript中只有5种基本类型和引用类型。其中5种基本类型分别是：

• Undefined
• Null
• Number
• Boolean
• String

除此之外只有1种引用类型——Object，Object本质上是由一组无序的键值对组成。5种基本类型是按值访问的，引用类型Object是按引用访问的。

可以使用typeof操作符监测变量的基本类型。*它可以判断变量是否为除null的其他5种基本类型以及function类型。除此之外都会返回”object”*。之所以null的typeof结果也为”object”，是因为null实际上表示引用指向空对象。

使用instanceof可以判断引用类型的具体值。使用方法类似于A instanceof B的形式。当B为“Object”时，表达式永远返回true。因为根据规定，所有引用类型的值都是Object的实例。

下面是几个例子。通过instanceof操作符可以很方便地区分空数组和空对象（当然还有Object.prototype.toString.call()和[].concat()两种方法。）

1
2

console.log([] instanceof Array); // true
console.log(/w+/g instanceof RegExp); // true

类型转换

to Boolean类型

Boolean类型是ECMAScript中使用最多的类型之一。类型只有true和false两个字面量。true不一定等于1，false也不一定等于0.可以通过调用Boolean()函数将其他类型转型为Boolean类型。规则如下：

• String类型：非空字符串=>true，空字符串=>false
• Number类型：非零数字（包括Inifity）=>true, 0和NaN=>false
• Object类型：任何对象=>true, null=>false
• Undefined：false

在使用if()语句或三元操作符等情况要求Boolean类型时，括号内的表达式将会自动使用Boolean()函数转换为布尔类型。

to String类型

有两种方法可以将值转为字符串，一种是使用几乎所有值都有的toString方法，对于null和undefined使用另一种——String()函数。

前者适用于除null和undefined外的所有值，甚至String本身（返回一个自身的副本）。有些toString()方法接收一个基数作为参数（如Number）对Object使用toString方法时，会根据对象内toString的定义决定。

• Array返回逗号隔开的不包括外侧中括号的字符串
• Function返回Function定义的字符串
• 普通Object返回”[object Object]”
• null和undefined分别返回”null”和”undefined”

to Number类型

可以使用Number(), parseInt()和parseFloat()三个函数做强制转换。转换到Number类型的规则要更好理解些。

• 是Boolean类型时，true和false分别转换到1和0
• 数字类型时，返回本身
• null时返回0
• undefined时返回NaN
• 对字符串使用类似于parseInt和parseFloat类似的方法（可以识别0x这样的进制前缀甚至Infinity这样的字符串）
• 对象使用valueOf()方法，再使用之前的规则；如果结果是NaN，再使用toString()方法作转换

类型转换场景

一元加减

一元加减只需对操作数强制转换到Number类型。向下面这样的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var s1 = "01";
var s2 = "1.1";
var s3 = "z";
var b = false;
var f = 1.1;
var o = {
    valueOf: function() {
        return -1;
    }
}

s1 = +s1; // 1
s2 = +s2; // 1.1
s3 = -s3; // NaN
b = +b;   // 0
f = +f;	  // 1.1
o = -o;	  // 1

加性操作符

ECMAScript中规定的加减法这两个操作符有一些特殊行为，不仅处理数值的加减，还处理字符串的加减。因此转换规则还有些复杂。

加法

优先做数值加减，无法完成时做字符串拼接。两个操作数都是数值时，执行常规的加法计算。

• 一个操作数为NaN时，返回NaN
• Inifity + -Inifity，返回NaN
• +0 加 -0，返回+0

只要有一个操作数为字符串类型，应用下面规则：

• 两个都是字符串时，则将它们拼接起来。
• 一个是字符串时，先将另一个转换为字符串

布尔值和null以及undefined在另一个操作数是数值类型时转换为数值类型，反之转换为字符串类型。
一个操作数为对象时，转换为字符串类型。

减法

与加法类似，除了数值相减减法也需要做一些类型转换。但是和加法不一样的是，减法返回的一定是Number类型。

• 一个数值为NaN时，结果为NaN
• 同号的Infinity相减返回NaN（如Infinity - Infinity），异号的Infinity相减等于第一个操作数
• 除了-0减+0返回-0，其余0间相减均返回+0
• 操作数出现字符串、布尔值、null、undefined时，做Number转换再进行数值减法
• 对象先尝试用valueOf方法获得对象数值，若无此方法则调用toString方法，并转换得到的字符串。

关系操作符

关系操作符即大于（>）、小于（<）、大于等于（>=）和小于等于（<=）。在操作数并非纯数值时，ECMAScript也会进行数据转换或一些奇怪的操作。

• 两个操作数都是数值时，进行数值比较
• 两个操作数都是字符串时，按照对应字符编码顺序比较
• 一个操作数是数值时，转换另一个为数值再比较
• 一个操作数是对象时，优先使用valueOf方法比较数值，没有该方法时再使用toString方法
• 任何数和NaN比较都会返回false

相等和全等

相等和全等用于确认两个变量是否相等。对此ECMAScript提供两组操作符：-相等-和-全等-。相等先转换类型后比较，全等仅比较不转换类型。由于情况较多较复杂，这里单独列一节。

ECMAScript中相等操作符为==。不相等操作符为!=。它们都会先强制转型变量再相互比较。转换规则如下：

• 先将布尔值转换为数值，false转换为0，true转换为1
• 字符串和数值比较时，将字符串转换为数值
• 两个操作数都是对象时，判断它们是否指向同一个对象（只比较引用）
• 只有一个操作数是对象时，调用valueOf()或toString()方法获得基本类型值
• null和undefined是相等的
• null和undefined在比较时不会被转换
• NaN出现时，相等操作符返回false

全等操作符为===，对象的不全等操作符为!==。它们不会转换变量类型，相比较类型后比较值。因此行为更容易预测。

CSS3中提供了animation的特性，用来通过指定关键帧（@kenframe）来实现动画效果。这么做方便高效。但是浏览器的兼容效果则比较捉急，且不能实现高级的缓动函数，更别说暂停、回放、倒放等功能了。所以大部分炫酷的动画还是采用JS动画来完成。

传统的JS动画无非是通过setInterval或是setTimeout定时器函数实现。这在对动画实时性以及流畅性要求不高时没有什么问题。不过当消息队列较拥挤时，定时效果不能得到保障。同时不同浏览器的UI渲染频率各不相同，很可能与用户设置的时间间隔相冲突。如，相当一部分浏览器的显示频率是16.7ms，此时如果我们设置的时延是10ms就会出现丢帧的情况。为了解决这个问题，requestAnimationFrame千呼万唤始出来。

requestAnimationFrame是window对象在HTML5中的新API。它的使用方法与setTimeout类似，不同的是，requestAnimationFrame()方法将告诉浏览器您希望执行动画，并请求浏览器调用指定的函数在下一次重绘之前调用回调函数更新动画。从而，不同的动画有了一个统一的刷新机制，可以提升系统性能，节省了CPU、GPU和电池等（CSS中的will-change也发挥着类似功能）。

那么requestAnimationFrame的兼容性如何呢？

好像还不错。在老版本的浏览器上，也有shim方法来实现同样的效果，借助了setTimeout函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

(function () {
    "use strict";

    var lastTime = 0,
        vendors = ['ms', 'moz', 'webkit', 'o'],
        x;

    for (x = 0; x < vendors.length && !window.requestAnimationFrame; ++x) {
        window.requestAnimationFrame = window[vendors[x] + 'RequestAnimationFrame'];
        window.cancelAnimationFrame  = window[vendors[x] + 'CancelAnimationFrame']
                                   || window[vendors[x] + 'CancelRequestAnimationFrame'];
    }

    if (!window.requestAnimationFrame) {
        window.requestAnimationFrame = function (callback) {
            var currTime = new Date().getTime(),
                timeToCall = Math.max(0, 16 - (currTime - lastTime)),
                id = window.setTimeout(function () {
                    callback(currTime + timeToCall);
                }, timeToCall);
            lastTime = currTime + timeToCall;
            return id;
        };
    }

    if (!window.cancelAnimationFrame) {
        window.cancelAnimationFrame = function (id) {
            window.clearTimeout(id);
        };
    }
}());

那么requestAnimationFrame怎么用呢。语法像下面这样。

1
2
3

requestID = window.requestAnimationFrame(callback);               // Firefox 23 / IE10 / Chrome / Safari 7 (incl. iOS)
requestID = window.mozRequestAnimationFrame(callback);                // Firefox < 23
requestID = window.webkitRequestAnimationFrame(callback); // Older versions Chrome/Webkit

注意它只接受回调函数作为参数，不需要指定延时哦。同样的，相对应的还有一个cancelAnimationFrame(requestID)方法取消重绘。最常见的用法是在一个动画函数里通过requestAnimationFrame循环调用自身。就像下面这样。

1
2
3
4
5
6
7
8
9
10
11

funFall = function() {
    var start = 0, during = 100;
    var _run = function() {
        start++;
        var top = Tween.Bounce.easeOut(start, objBall.top, 500 - objBall.top, during);
        ball.css("top", top);
        shadowWithBall(top);    // 投影跟随小球的动
        if (start < during) requestAnimationFrame(_run);
    };
    _run();
};

引子

首先我们先来看下面一段代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

(function(){
    console.log(1);

    setTimeout(function () {
        console.log(5);
    }, 0);

    setTimeout(function () {
        setTimeout(function () {
            console.log(8);
        }, 0);
    }, 0);

    (function () {

        console.log(2);

        setTimeout(function () {
            console.log(6);
        }, 0);

        console.log(3);

        setTimeout(function () {
            console.log(7);
        }, 0);

        console.log(4);

    })();

    return 'result';
}());

尽管结构复杂，但是只要对JavaScript的异步和回调有点了解，就能知道它的输出结果是’1 2 3 4 “result” 5 6 7 8’。

并发模型

JavaScript中的异步和回调是语言本身的一种特色。包括上文中的setTimeout函数，Promise对象以及node.js的fs.readFile等。将耗时的操作非阻塞地完成，可以大大提高程序的执行效率。而这些都和JavaScript的并发模型密切相关。与C++, Java多线程处理方式不同，JavaScript中的并发是基于事件循环（Event Loop）的。

Event loop is a programming construct that waits for and dispatches events or messages in a program.

执行图

Stack

函数调用时所用的执行环境栈。当函数被调用时，会进入一个执行环境（execution context）。当在函数内部调用其他函数（或自身调用）时，会进入新的执行环境，并在函数返回时回到原来的执行环境，并将原先的执行环境销毁。根据ECMA定义的概念，代码在执行环境中，还会创建变量对象的作用域链，以确保当前执行环境的有序性。最外层执行环境是全局环境（如window）。具体作用域链和执行环境的介绍，将放在其他文章中进行。

函数执行过程中的执行环境栈即Stack。如下面的代码中，调用g时，形成第一个堆栈帧，包括参数21和局部变量m等。g调用f后，会创建第二个堆栈帧，置于其上，包含f的参数84和局部变量12等。f返回后，第二层栈帧出栈，g返回后，栈就空了。

1
2
3
4
5
6
7
8
9
10
11

function f(b){
    var a = 12;
    return a+b+35;
}

function g(x){
    var m = 4;
    return f(m*x);
}

g(21);

Heap

存放JS中引用类型的堆，JS的引用类型通过类似于图的形式存储，方便进行垃圾回收。具体介绍可以参考红宝书，这里从略。

Queue

JavaScript运行时的待处理消息队列，其中的每个消息都与对应的回调函数绑定（未绑定的消息不会进入队列）。当栈空时，会从栈中取出消息进行处理，这个过程包括调用回调函数，形成调用栈等。当栈在此为空时，代表这个消息处理完成。

首先我们要明确一点，JavaScript的并发是单线程的。在程序中（如浏览器）运行时，JS引擎跑着两个线程。一个负责运行本身的程序，叫做主线程。另一个负责主线程与其他线程的的通信，即Event Loop。当遇到异步的任务时，主线程将交由其他线程处理，并根据情况将对应的消息入队到信息队列（Message Queue）等待处理，如果消息未绑定回调函数，则不入队。

当调用栈清空后，队首消息依次出队，并调用绑定的回调函数，产生函数执行环境和调用栈等。直到消息队列清空为止。以上就是JavaScript中的事件循环。

不同的web worker或跨域的iframe都有各自的栈、堆以及消息队列。不同的环境通过postMessage方法进行通信（需要双方监听message事件）。

setTimeout和setInterval

在明白什么是时间循环后，setTimeout和setInterval这两个定时器函数就比较容易理解了。由于JavaScript运行在单线程的环境里，setTimeout和setInterval的定时时机实际上并不能得到保障。

定时器对队列的工作方式是，在在当前时间过去特定的时间后将代码插入，这并不意味着之后会立即执行，而只能保证尽早执行。。如下面的代码中，设定的250ms延时并不代表在onclick事件触发后的250ms立即执行。实际上，如果onclick的事件处理程序执行超过了250ms，定时器的设置将不再有意义（因为匿名函数的执行时机由onclick事件处理程序何时结束决定）。由此可见，setTimeout的时间间隔往往会比设计时长。

1
2
3
4
5
6

var btn = document.getElementById("my-btn");
btn.onclick = function () {
    setTimeout(function () {
        document.getElementById("message").style.visibility = "visible";
    }, 250)
}

setInterval道理类似，和setTimeout不同的是，setInterval函数会将回调函数定时地插入消息队列的末端。为了避免定时器代码在执行完成前就有新的相同代码插入，造成严重性能问题，聪明的JavaScript引擎仅在队列中没有其他定时器实例时才会插入新的定时器代码。

但是这么做却也带来了一个问题，那就是

1. 某些间隔会被跳过
2. 多个定时器间的间隔会比预期的要小。

后者可以通过循环调用setTimeout来避免。

另外，微软在IE 10中实现了setImmediate方法，来实现真正的回调函数“立即执行”，而在实际运行中似乎和setTimeout的时间类似。

Macrotask 和 Microtask

首先我们还是先来看一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

setImmediate(function(){
    console.log(1);
},0);
setTimeout(function(){
    console.log(2);
},0);
new Promise(function(resolve){
    console.log(3);
    resolve();
    console.log(4);
}).then(function(){
    console.log(5);
});
console.log(6);
process.nextTick(function(){
    console.log(7);
});
console.log(8);

它的结果是什么呢。这里我们就要知道setTimeout, setImmediate, Promise.then, process.nextTick这些异步操作的优先级了。回答这个问题之前，我们先了解一下Macrotask和Microtask两个概念。

Macrotask又叫task，是消息队列中一个个的message，一次event loop里面可能会有多个task，task有自己的task source，比如说setTimeout来自于timer task source，又或者和用户交互相关的来自user interaction task source。

Microtask和Macrotask类似，区别在于它更轻量级，并非每次都在task末尾才执行，只要函数栈为空掉，Microtask就会执行。由此可见它的优先级要更高些。

总结一下，它们的特点如下：

• 一个事件循环(event loop)会有一个或多个任务队列(task queue) task queue 就是 macrotask queue
• 每一个 event loop 都有一个 microtask queue
• task queue == macrotask queue != microtask queue
• 一个任务 task 可以放入 macrotask queue 也可以放入 microtask queue 中
• 当一个 task 被放入队列 queue(macro或micro) 那这个 task 就可以被立即执行了

简单点总结事件循环就是

1. 在 macrotask 队列中执行最早的那个 task ，执行浏览器渲染，然后移出
2. 执行 microtask 队列中所有可用的任务，然后移出
3. 下一个循环，执行下一个 macrotask 中的任务 (再跳到第2步，直到没有task和microtask)

在实现上，macrotask主要有setTimeout setInterval setImmediate I/O UI渲染；microtask主要有Promise process.nextTick Object.observe MutationObserver。由于microtask会耽误task的执行，尤其是在较多时甚至无法执行消息队列中的task，包括UI刷新。因此process.nextTick默认上限为1000，避免上述情况的出现。当调用次数过多时，会抛出栈溢出错误。

所以，上面的执行结果将是3 4 6 8 7 5 2 1

炎热的夏天，聒噪的蝉鸣，人与人间的热气的日光灯下蒸腾。黑板上寥寥数笔，是语文老师画的重点。周围略显浮躁的气氛，《过秦论》的声音此起彼伏。

她是我的一个老朋友，身材小巧，善手工，不乏男性追求。只是她的名字实在是太普通了。我一直都不知该怎么称呼。我和她认识在高一的期末。也许从最初起，我就错了。

眼前的设计展并没有太多游客，我又向她迈近一步。我们已经十多年没见面了。她还像以前那样活泼，浑身上下散发着灵感。

她高一送我的用指甲油涂成的艺术画，我一直都留着。她的点子总是很多，多得让我有些羡慕。我们一起聊过摄影、聊过梦想。雨过天晴，五月份的蓝天映在排球场的水洼里。广播站的屋顶，和风吹过，午后的太阳挂在天际线高楼边。她说她要攒钱买单反，最后拿奥斯卡奖。我说我要考个好大学。楼下，蝼蚁样的人来来去去，头也不回。

那天过后，她送了我第5版的《认识电影》。

这面墙上挂着剪纸和针织作品，角度位置、一分一毫恰到好处。她一动不动，背朝着我。我似乎被巨大的阻力拉扯着，吃力地走到她跟前。

高一结束的一场大雨冲散了太多人。我和她断了联系。小小的筒子楼里，杳无音信，只剩下朋友的称谓悬着，连着。于是在毕业时公车的巧遇后，就再没重逢过。彼时，她送我的那本《认识电影》，我已经看完了。最后，她去了武汉，我来了北京。

其实，之后我们也还有联系。她说武汉天气无常，说要好好学设计，说好久不见。我说北京气候干燥，说我写的信注意查收，说再约再约。那封信，却没听她提起过。

至少联系还在，那个称谓还在，没人碰。

靠近了，我来不及整理要说的只言片语，伸出手轻轻点了她的肩。

转眼四年过去，我们毕业了。她还在武汉，我还在北京。有许多传言，有人说她去学校东门外开了家奶茶店，有人说她和前男友又重归于好。之后发生的事，却是我没想到的。

她来北京了。只可惜我不用微博，否则能知道的更早些。

终于，我们约好在三里屯见面，1月22日。

那天是北京当年最冷的一天。凛冽的冷风肆虐，地面的积雪将整个广场吞没，周围茫茫一片白。水池里的水凝结着，高楼兀立着，指向苍莽的天空。我下了车，被一拥而上的寒意驱动得踏起小碎步。

“我到了”

七分钟后，

“我们下午看电影去吧。我团两张电影票。”

“我们先见面吧，外面真得很冷。”

路上的行人稀稀拉拉，四下只有汽车和寒风呼啸的声响。五分钟后。

“你到了吗？”

“电影票估计是买不到了，我马上到，你先去星巴克等我吧。”

“来这儿找我吧。”说着，我将定位发给了她。

话音刚落，手机因低温自动关机。这该死的自动关机。

这便成为了我和她说的最后一句话。

之后的事情似乎进行地很快了。我去了星巴克，没有人。我回到了定位地点，没有人。一小时后，我去了网吧恢复了手机，没有回复。我联系了我们的共同好友，没有消息。

“您拨打的号码是空号。”雪还在下着，天色已经不早了。

事后出于好奇，我翻了她最常用的微博。第一条状态已是半年前的毕业。看到这儿我就没再翻下去。好像毕业以后，她似乎就变成了另外一个人。疑问没得到解决，她就此消失在我的世界里。

多年后，我因工作原因开通了微博。不知怎地突然想起了她。好奇之下，又去了她的微博。向下翻看时才发现：世上哪有那么多戏剧性。她并没有变成另外一个人。那时看的微博只不过并不是按照时间排序而已。

……

2015/12/20，“You silly dog. I love you so much, plz be a handful forever.”

2016/1/2，“Bye&hi”

2016/1/8，“I get you!”

2016/1/25，“I love and enjoy it！ Skiing!”

2016/2/3，“那些不顺换来的——你，你们和在北京的日子。再见，我们回家。”

……

再之后，她出国留了学，学的设计。再之后和男友定居国外。

6/8，“I am back! The 2nd exhibition in China!”

这场展览是关于日常材料艺术的，其中也包括指甲油。尽管大落地窗外艳阳高挂，场馆却空旷而凉爽。

她近在眼前。我的手指碰到了她的肩，之后又穿了过去。她就像是空气，漂浮在我面前。只见她转过头，还是那副小巧的面孔。我失去了平衡，整个身体与她交错，重重砸在地上

……

炎热的夏天，听不到蝉鸣。我躺在出租屋的床上，一头汗水。午睡的时间，四周一片寂静。眼前没有黑板，也没有老师画的重点，心里像是一下子失去了些什么。

也许，真实的故事里，她和我根本没有这么多交集。也许，我们没聊过梦想。也许，她没送过我书，广播站也并没有屋顶。甚至，她从未在国内办过设计展。而我却是真的。

有时，失去一个朋友真是很容易，就像看一道流星，还没来得及许愿，就从你身边划过。如果她，名字普通的她，看到了这篇故事，也祝愿她一路顺风，拥有崭新的更好的生活。有些事情，本就无是非对错。

本文目的在日后再看到这些名词时能有扫盲的作用，所以未做深入探讨。

二叉搜索树的查询时间复杂度为O(h)，但是h的大小和数据密切相关，随机构建二叉搜索树可以保证期望高度h为O(lgn)，但是我们并不总能随机地构造二叉搜索树。所以就有二叉搜索树的变体来保证基本操作具有好的最坏情况性能，如AVL树，红黑树，treap树，splay树等。它们在二叉搜索树的基础上增加了额外的约束，操作更加复杂，但是保证最坏情况的动态集合操作时间复杂度为O(lgn)。下面按照时间介绍之。

AVL树

AVL树是最早发明的自平衡二叉搜索树，查找、插入、删除在平均和最坏情况下都是O(lgn)，自平衡是通过插入和删除时一次或多次树旋转来完成的。节点的平衡因子是左子树减去右子树的高度，1、0、-1被认为是平衡的，-2或2被认为是不平衡的，需要重新平衡树。平衡因子储存在节点中，或是通过计算算出。

根据不平衡的情况，AVL分成左左、右右、左右、右左四种情况，分别需要1、1、2、2次旋转调整。图略。

由于AVL是高度平衡树，所以节点插入、删除后，重新平衡需要的旋转次数较多，但是因此带来的搜索效率更高。

红黑树

最常见的平衡二叉树，统计性能最好的二叉搜索树。红黑树是满足下列性质的二叉搜索树：

• 每个节点都是黑色或是红色
• 根节点是黑色
• 每个叶节点都是黑色
• 如果一个节点是红色，那么它的两个子节点都是黑色
• 对于每个节点，从它到其所有子孙叶节点的路径包含的黑色节点数目相同

由于没有AVL树对平衡的高度要求，红黑树在节点插入、删除时，只需最多3次旋转操作即可完成。虽然牺牲了查找效率，但是在经常改动的动态数据集合中，红黑树的性能要更好。可以说红黑树在复杂度和旋转次数上有比较好的折中，因此常用作数据结构的设计。

Treap树

Treap树得名于搜索树trea和堆reap，是有一个附加域满足堆特征的二叉搜索树，结构相当于随机插入数据的二叉搜索树，相较其他平衡二叉树，特点是实现简单，且能基本实现随机平衡。

在构成Treap树时，还需要满足堆特征，在插入、删除维护堆性质时，只需要两种旋转，相比Splay，编程复杂度要更小。性能在平衡二叉树和二叉搜索树之间。

Splay树

Splay树又叫伸展树，发明于1985年。它是一种自调整形式的二叉搜索树，利用了频繁查找的数据集有限，在二叉搜索树的每次搜索后，将搜索条目通过一系列旋转搬移到离树根更近的地方。它的优势在于不需要记录平衡树的冗余信息，且编程复杂度小很多。

Splay的操作为旋转，分单旋转、一字型、之字形几种。

这些树的编码都较为复杂，这里略去。