这是数据结构类重新复习笔记的第 三 篇，同专题的其他文章可以移步：https://www.jianshu.com/nb/39256701

树

树的实现

实现树时，对于每一个节点，除了存储该节点的数据以外，还需要存储一些外链。

一个典型的存储方式是：左孩子右兄弟法，即对于每一个节点，存储节点的数据、指向其孩子中最左边的孩子的指针、指向其紧邻的右侧的兄弟节点的指针。

struct TreeNode
{
    Object element;
    TreeNode * firstChild;
    TreeNode * nextSiling;
};

如下边的这棵树通过这种方式表现的结果是这样的：

采用“左子右兄弟”表示树

二叉树

二叉树（binary tree）是一棵每个节点都不能有多于两个儿子的树

二叉树的特点

• 二叉树第i层上至多有 2i-1 个节点
• 深度为k的二叉树至多有 2k-1 个节点
• 对于一棵非空二叉树，如果其叶子节点数为n0，度为2的节点数为n2，则n0=n2+1
• 具有n个节点的完全二叉树的深度为 [log2n]+1 (向下取整数)
• 如果对于n个节点的完全二叉树，第 i>0 的节点，其父节点为 [(i-1)/2] (向下取整)

二叉树的一个性质是平均二叉树的深度要比结点个数N小得多，这个性质有时很重要。分析表明，这个平均深度为O(√N)，而对于特殊类型的二叉树，即二叉查找树( binary search tree)，其深度的平均值是O(logN)。当然极端的树的深度也可以大到N-1。

二叉树的实现

由于二叉树的每个节点最多有两个儿子，所以可以直接连接到它们。

struct BinaryNode
{
    Object element;
    BinaryNode * left;
    BinaryNode * red;
};

二叉查找树

二叉查找树（Binary Search Trees）是二叉树，它的特点是：对于任何一个节点X，其左子树中的所有节点的值都小于该节点X，其右子树中的所有节点的值都大于该节点X。如下图中的左边就是一棵二叉查找是，而右侧不是：

二叉查找树

重要的方法与其实现

• isEmpty：是否为空树，这一点很重要，一般在进行树的相关操作时都会先确定是否是一个空树，只要指向根节点的指针为NULL，就表示是一个空树
• contains：是否包含某项，在确定树非空后，查找是否包含某个项，将目标项与根节点进行比较开始，如果比该节点大，就从右子树查找，如果比该节点小，就从左子树查找，如果出现相等的则表示包含该项，如果一直不相等且无子树可以继续查找，则不包含此项
• findMin：找到最小值，一直找左子树，直到找到没有左子树的左子树最左边的节点就是最小值
• findMax：找到最大值，一直找右子树，直到找到没有右子树的右子树最右边的节点就是最大值
• insert：插入某个值，从根节点开始比较，如果目标值比该节点大就插入其右子树，否则插入左子树，如果出现相等的情况说明有该元素不需要再插入，直到插入某个空节点为止
• remove：删除节点
  • 删除叶子节点：直接删除

  • 删除有一个子节点的节点：将该子节点挂到被删除的节点的父节点上，取代删除节点的位置

    
    删除只有一个子节点的子节点

  • 删除有两个子节点的节点：找到该节点右子树中的最小值或者左子树中的最大值，将其替换要删除的元素，然后递归地删除用来替换的最大/小值，为什么是递归地删除呢？因为被拿出来替换被删除值的那个最大/小值也会有子树，所以删除它的时候还要执行删除remove操作。但是最多只进行一次单子节点的删除工作，因为无论是右子树中的最小值还是左子树中的最大值，最多只有一个子树

    
    删除有两个子节点的子节

平均情况分析

操作	平均时间复杂度
isEmpty	O(1)
contains	O(logN)
findMin/findMax	O(logN)
insert	O(logN)
remove	O(1)

AVL树

AVL（Adelson-Velskii and Landis）树是带有平衡条件（balance condition）的二叉查找树，这个平衡条件很容易保持并且保证了树的深度为O(logN)。

AVL树要求每个节点的左子树和右子树的高度差最多为1。

AVL树

AVL树除了插入操作外，其他所有的操作都可以最多以O(logN)的时间执行

AVL树的插入

AVL树的插入比较复杂的点在于插入的值可能会破坏树原本的平衡，所以在插入值后需要进行旋转（rotation）

旋转的情况可以根据插入后的树的情况分为如下四种：

示意图来源：https://blog.csdn.net/gabriel1026/article/details/6311339

插入后的情况	描述	旋转方式
LL-左子树左高	在左子树根节点的左子树上插入节点而破坏平衡	右旋转
RR-右子树右高	在右子树根节点的右子树上插入节点而破坏平衡	左旋转
LR-左子树右高	在左子树根节点的右子树上插入节点而破坏平衡	先左旋后右旋
RL-右子树左高	在右子树根节点的左子树上插入节点而破坏平衡	先右旋后左旋

• LL-左子树左高的情况

  
  LL-左子树左高

• RR-右子树右高的情况

  
  RR-右子树右高

• LR-左子树右高的情况

  
  LR-左子树右高

• RL-右子树左高的情况

  
  RL-右子树左高

伸展树

伸展树与摊还时间

伸展树（splay tree）保证从空树开始任意连续M此对树的操作最多花费O(MlogN)的时间，即这M次连续的操作中即使有些操作耗时长，但是也有一些耗时短的操作，使得这M个连续的操作花费的总时间最坏为O(MlogN)。

摊还（amortized）：一般说来，当M次操作的序列总的最坏情形运行时间为O(M f(N))时,我们就说它的摊还(amortized)运行时间为O(f(N))。因此，一棵伸展树每次操作的摊还代价是O(logN)。经过一系列的操作，有的操作可能花费时间多一些，有的可能要少一些，不存在不好的输入队列。

如果任意特定操作可以有最坏时间界O(N)，而我们仍然要求一个O(logN)的摊还时间界，那么很清楚，只要有一个结点被访问，它就必须被移动。否则，一旦我们发现一个深层的结点，就有可能不断地对它进行访问。如果这个结点不改变位置，而每次访问又花费O(N)，那么M次访问将花费O(MN)的时间。这个思想和数据库中将经常访问到的数据前移以及操作系统中将经常访问的数据放入cache高速缓存等思想相同。（在许多应用中，当一个结点被访问时，它就很可能不久再被访问。研究表明，这种情况的发生比人们预料的要频繁得多。）

伸展（splaying）

伸展树的基本思想是将访问到的一个较深的节点通过旋转的方式将其旋转到根节点的位置，但是为了保证旋转过程中不让一些较浅的节点也被沦落到较深的位置，这里的伸展采用一定的策略：

• 首先，一个要被旋转到树根处的深节点X，如果X的父节点就是根节点，那么只要旋转X和树根即可
• 如果X的父节点不是根节点，将其父节点命名为P，同时X一定有祖父节点G，X、P、G三个节点存在两种排列关系：

  • “之字形”（zig-zag）：这种情况下执行一次AVL树同理的双旋转

    
    “之字形”（zig-zag）

  • “一字形”（zig-zig）：这种情况下直接将树左右对调（类似于跷跷板）

    
    “一字形”（zig-zig）

一个例子

如下图，想把 K1 节点调至树根处

一个伸展树的例子

首先由K1、K2、K3构成了一个“之字形”结构，使用双旋转方式得到如下的第一次调整

一个伸展树的例子

然后由K1、K4、K5构成了一个“一字形”结构，采用跷跷板的方式做第二次调整

一个伸展树的例子

树的遍历

树的遍历分为三种

• 先根遍历：每棵树按照 根-左子树-右子树 顺序遍历
• 中根遍历：每棵树按照 左子树-根-右子树 顺序遍历
• 后根遍历：每棵树按照 左子树-右子树-根 顺序遍历

B树

B树的思想很简单，如果我们使用二叉树，树的平均深度为logN，如果我们是一个M叉树（每个节点最多有M个子树），则树的平均深度为logMN，显然这样会使得树的深度降低。

M阶B树的规范

• 数据项存储在树叶上
• 非叶结点存储直到 M-1 个键，以指示搜索的方向；键 i 代表子树 i+1 中的最小的键
• 树的根或者是一片树叶，或者其儿子数在2和M之间
• 除根外，所有非树叶结点的儿子数在 [M/2]（向上取整）和M之间
• 所有的树叶都在相同的深度上并有 [L/2]（向上取整）和L之间个数据项

一个5阶B树的例子

一个5阶的B树，所有的非叶子节点的儿子都在3和5之间，从而有2到4个键，根可能只有两个的儿子，L=5，因此每个树叶有3到5个数据项，要求节点一半满，保证B树不致退化成简单的二叉树

一个5阶B树的例子

向B树中插入 57 数据项：按照键索引到插入数据的位置，插入数据项

一个5阶B树的例子

再插入 55 数据项，导致该叶子节点数据超出5，所以需要分裂其父节点成为两个叶子

一个5阶B树的例子

再插入 40 数据项，引起树叶被分裂成两片然后又造成父结点的分裂

一个5阶B树的例子

从B树中删除 99 数据项导致叶子节点的数据少于3从而合并叶子，而父节点也少于3从而再一次合并

一个5阶B树的例子

标准库（SLT）中的set和map

set

set是一个排序后的容器，不允许重复。set特有的操作是高效的插入、删除和执行基本查找。set也允许使用iterator来遍历。

set的方法

• 与vector和list相同的方法
  • iterator begin()：返回容器开始的迭代器
  • iterator end()：返回容器结尾处的迭代器
  • int size() const：返回容器内的元素个数
  • bool empty()：如果容器没有元素，返回 true，否则返回 false
• 特有的插入操作，set使用insert进行插入操作，由于非重复性，导致插入有可能会失败，insert操作返回一个iterator指明插入新项的位置或者失败时已有的项的位置.。pair是一个类模板，并且提供两个成员 first 和 second 用来访问返回值的两项成员
  • pair<iterator, bool> insert( const Object & x); ：插入Object x
  • pair<iterator, bool> insert( iterator hint, const Object & x);：在指定索引hint处插入Object x，比单参数的插入快得多，通常为O(1)
• erase删除操作
  • int erase( const Object & x); ：删除x，如果找到的话，返回删除元素的个数，显然只能返回0或者1
  • iterator erase( iterator itr);：删除有iterator指定的位置的对象
  • iterator erase( iterator start, iterator end);：删除由两个iterator指定的位置对象中间包含的所有元素，包含前不包含后
• find查找操作
  • iterator find( const Object & x) const;：查找x返回其位置

map

map用来存储排序后的由键和值组成的项的集合，键必须唯一，但是多个键可以同时对应一个值，即值不需要唯一，键保持逻辑排序后的顺序

map的方法

map的方法和set很像，但是其返回值是一个键-值对： pair<KeyType, ValueType>，map支持 begin、end、size、enmty、insert、find、erase、find

• insert操作必须提供 pair<KeyType, ValueType> 对象
• find仅需要一个键，但是返回值的iterator还是指向一个 pair<KeyType, ValueType> 对象，并可以用 first 访问返回的键，使用 second 访问返回的值

map还重载了数组索引的操作符 []：

ValueType & operator[] ( const KeyType & key );

如果map中存在key就返回只想相应值的引用，如果不存在key就在map中插入一个默认的值，然后返回指向这个插入的默认值的引用

---

转载请注明出处，本文永久更新链接：https://blogs.littlegenius.xin/2019/08/19/【数据结构】三树/