Content #

正如马基雅维利几百年前就在他的经典著作《君主论》（The Prince）中指出的，虽然让人们既害怕你又喜欢你是种很理想的状况，但是当你必须两者选其一时，如果想获得和保持权力，那就应该选择让人们害怕你。

马基雅维利的忠告与我们如何看待别人的社会心理学研究结果一致，这项研究发现，人们普遍使用两个指标来评估他人，即友好和有能力。问题在于，你要表现得自己有能力，那就显得强硬一点，甚至是卑鄙一点，似乎很有帮助。哈佛商学院教授特雷莎·阿马比尔（Teresa Amabile）曾研究过人们对摘录的图书评论的反应。阿马比尔发现，与做出正面评论的人相比，做出负面评论的人往往被视为更聪明、更有能力，即使独立的专业人士认为这些负面评价的质量并不见得更高。她的论文名为《聪明但却残酷》（Brilliant but Cruel），这个题目就说明了一切。其他研究已经证实了她的发现：招人喜欢的人被认为是温暖人心的，但友好也往往被认为是软弱甚至是缺乏才智。

康多莉扎·赖斯（Condoleezza Rice）在布什政府中担任国家安全顾问。在进入政府部门之前，赖斯在斯坦福大学担任教务长，当时的校长是格哈德·卡斯珀（Gerhard Casper）。在斯坦福，人们认为她是绝不应当冒犯的人。正如雅各布·海尔布伦（Jacob Heilbrunn）所说：“赖斯削减预算，挑战反歧视行动的支持者……她的直率作风让很多学生和教员对她产生了敌意。正如赖斯对一个门徒所说的，她的信条就是：‘人们可能会反对你，但是当他们意识到你可以伤害他们时，他们就会加入你这一边。’”

招人喜欢的人被认为是温暖人心的，但友好也往往被认为是软弱甚至是缺乏才智。

“招人喜欢”可能会带来权力，但权力一定会让你招人喜欢

康多莉扎·赖斯说得很正确，如果你有权力，并且愿意使用权力，人们就会加入你这边，不仅因为他们害怕你伤害他们，也因为他们想接近你，想和你的权力与成功扯上关系。有大量的证据显示，人们希望和有实权的、成功的机构和人物沾亲带故，希望能沾一点光。

From #

权力：为什么中为某些人所拥有

Links #

Content #

在广告行业中，引人注目、令人难忘的概念就是所谓的“品牌记忆度”（brand recall），这是衡量广告效果的一个重要指标。对宣传产品有效的做法，宣传你也同样有效，所以你也需要显得很有趣，令人难忘，并且引人注目，让他人想了解你、想接近你。

这个建议，就像本书中的很多其他建议一样，是建立在扎实的研究成果基础上的，但它显得与传统智慧背道而驰，并且打破了你认为应该遵循的行为“规则”。当然它打破了规则！正如马尔科姆·格拉德威尔（Malcolm Gladwell）曾深刻指出的那样，这些规则倾向于对制定这些规则的人有益，而这些人往往是已经获得了成功，拥有了权力的人。格拉德威尔说，一项研究结果显示，按规则行事，即按常规智慧行事，在从体育竞赛到战争的各种对抗中，都更有利于本来就更强大的一方；而以反常规的方式行事，即采用非传统的策略，则可以让资源处于劣势的一方取得胜利。

有一个课题研究了过去200年中实力不匹配的对手之间的战争，强大的一方获胜的比率为72%。但是，当弱势的一方了解自己的弱点，并使用了非常规策略，尽量减少这种弱点的影响时，他们获胜的比率为64%，这就让强大一方获胜的可能性减少了一半。正如格拉德威尔所指出的：“当弱者选择不按巨人的规则玩游戏时，他们就赢了。”因此，如果你已经拥有了你想要或需要的权力，那么你就应该采取一切手段，不仅确保自己遵循规则，而且也鼓励大家都这么做。但如果你仍然在通往权力的道路上，那么你就大可不必相信传统智慧和“遵循规则”那一套了。

From #

权力：为什么中为某些人所拥有

Links #

Content #

提出请求之所以会起到作用，原因之一在于：如果有人请我们提供建议或帮助，我们会感到荣幸。很少有什么事情能像别人特别是有才华的人寻求我们的帮助一样，给我们带来更强烈的自我肯定和自我增强感。

巴拉克·奥巴马刚进入参议院时，就是通过请求别人的帮助从而建立了人际关系。他向三分之一的参议员寻求建议，并让汤姆·达施勒（Tom Daschle）成为他的顾问指导。达施勒是民主党的前参议院领袖，当时刚刚在竞选连任中失利。奥巴马也向特德·肯尼迪（Ted Kennedy）和共和党参议员理查德·卢格（Richard Lugar）寻求指导。正如《纽约时报》中一篇关于奥巴马的文章所指出的：“一个好学生的角色为他赢得了一些国会议员的喜爱。”如果你让你的请求尽可能地具有恭维意味，那就更有可能让别人答应你的请求。

From #

权力：为什么中为某些人所拥有

Links #

Content #

人们低估了别人提供帮助的可能性。这是因为人们在考虑提出要求的时候，往往把重点放在给他人带来的成本上，而没有充分考虑对方说“不”的代价。

首先，拒绝提供帮助，会违反社会倡导的一种隐含规范，即表现得“乐善好施”。你愿意被视为慷慨的还是吝啬的呢？其次，拒绝别人亲自提出的要求是尴尬的。我们从小受到的教育就是要慷慨，所以我们倾向于答应别人的要求，这几乎是自动的反应。

再次，对一个请求帮助的人说“是”，这会巩固提供帮助者的权力。指导别人、答应别人共进晚餐或为别人开门，不仅会让别人依靠你、回报你，还有可能让别人成为你的忠实支持者，而且还意味着你可以为别人提供某种东西，而你也就拥有了权力。

From #

权力：为什么中为某些人所拥有

Links #

Content #

相对薪酬 #

各部门的起薪与高级职位的薪酬显示了相对权力。在前面提到的公用事业研究中，如果一个人在权力更高的部门开始他的职业生涯，他的起薪会比其他人高出大约 6%。虽然这个差异看似很小，但这家公司是在聘请新晋的管理者，令其接受较为标准化的培训并进行最初的轮岗计划，因此任何差异都有些出人意料。几年前，有人对不同国家、不同部门的最高级领导者，即“首席”高管进行了调查。数据显示，在德国，研发部门的薪酬最高；在日本，研发部门以及人力资源部门的薪酬最高；而在美国，薪酬最高的则是财务部门。这些相对薪酬水平显示了不同部门的权力，也说明在不同的国家中，部门之间的权力分配也有所不同。

办公室位置和设施 #

办公室的位置接近掌权者，这既显示了权力，也利于通过增加与掌权者的接触而获得权力。几年前，一些学生拿到了太平洋燃气电气公司总部各个部门的分布图。这家公司为北加州大部分和内华达州部分地区提供电力和天然气。随着时间的推移，工程部门办公室在大楼中的位置在下降，而律师和财务部门办公室的位置在上升。最后，工程部门搬到了离旧金山总部几公里以外的地方。与此同时，律师和财务人员在高级管理人员中的比重也在上升。办公室的位置非常重要，因此在一个人政治命运兴衰之时，往往会花费重金搬迁和重新装修办公室。在像白宫这样高度政治化的地方，情形尤为如此。正如理查德·尼克松总统的法律顾问约翰·迪恩（John Dean）所说：“成功和失败可以从办公室的大小、装饰和位置中看出。一个人搬迁到一个较小的办公室，他就是在走下坡路。如果有装修工在某人的办公室忙碌，这确定无疑是一个好迹象，表明他的事业现在蒸蒸日上。”

在委员会和高管层中的位置 #

要看财务部门的权力有多大，一个方法是看部门主管的年薪。但还有另一种方式，就是看看除了CEO外，谁是最有可能进入公司董事会的内部人员。在很多情况下，尤其是在董事会用外部人士替代内部人员时，财务主管是唯一在董事会上出现的内部管理人员。这就展示了财务部门的相对权力。

From #

权力：为什么中为某些人所拥有

Links #

Content #

左旋（rotate left）全称是围绕某个节点的左旋。右旋（rotate right）全称是围绕某个节点的右旋。

图中的 a，b，r 表示子树，可以为空。

Viewpoints #

From #

26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树

Links #

Content #

平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化得太严重。

二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。

如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？ #

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

完全二叉树的高度近似 log n，这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过 log n。

把红色节点加回去，高度会变成多少呢？ #

在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

Viewpoints #

From #

25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？

Links #

Content #

红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

1. 根节点是黑色的；
2. 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
3. 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

这里的第二点要求“叶子节点都是黑色的空节点”，稍微有些奇怪，它主要是为了简化红黑树的代码实现而设置的。在画图和讲解的时候，黑色的、空的叶子节点都省略掉了。

两个红黑树的图例。

Viewpoints #

From #

25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？

Links #

Content #

由苏联数学家Adelson-Velskii和Landis提出，所以又被称为AVL树。

平衡二叉树或为空树，或为具有以下性质的平衡二叉树：① 左右子树高度差的绝对值不超过1；② 左右子树也是平衡二叉树。节点左右子树的高度之差被称为平衡因子。在二叉查找树中，每个节点的平衡因子的绝对值不超过1即平衡二叉树。例如，一棵平衡二叉树及其平衡因子如下图所示:

最小不平衡子树 AVL树调整平衡的方法

在平衡二叉树中进行插入操作时只需从插入节点之父向上检查，发现不平衡便立即调整，调整一次平衡即可；而进行删除操作时需要一直从删除节点之父向上检查，发现不平衡便立即调整，然后继续向上检查，直到树根。

From #

Links #

AVL树的参考实现代码

Content #

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？

1. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
2. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
3. 尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
4. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
5. 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。

Viewpoints #

From #

24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？

Links #