数据结构和算法设计 Vol3

二叉树中三种遍历方式：前序遍历、后序遍历和中序遍历；在普通二叉搜索树中的搜索search、插入insert、删除remove中的算法效率或者说复杂度和树的深度有关。因此在树的等价交换和基本操作的基础上，提出了平衡二叉树（BBST，Balanced binary search tree）的概念，由此延伸得到AVL、伸展树（Splay tree）、B树、红黑树、KD-树的概念，并可以看到这些在实际生活中的应用。

0x01 二叉树的遍历traversal

对二叉树的访问可以抽象为如下形式：按照某种约定的次序，对节点访问且仅一次。遍历之于二叉树的意义，同样在于为相关算法的实现提供通用的框架，此外这一过程等效于将半线性的树形结构转换为线性结构，但是二叉树不在属于线性结构，因此遍历过程更为复杂。

1.1 递归式遍历 recursively traversal

二叉树本身并不具有天然的全局次序，故为实现遍历，首选需要在各节点与其孩子之间约定某种局部次序，从而间接定义全局次序。分为左（L，left）、右（R，right）、节点（R，root），因此分为VLR、LVR、LRV三中心选择，也就是先序遍历（preorder）、中序遍历（inorder）、后序遍历（postorder）

添加图片注释，不超过 140 字（可选）

• 先序遍历（preorder）

首先核对X是不是空集，若x为空则直接退出

若x非空，则按照先序遍历，优先访问根节点，然后访问左子树和右子树

def travPre_R(set,visit):
    if(!x) return;
    visit(x.data);
    travPre_R(X.lc,visit)
    travPre_R(x.rc,visit)

添加图片注释，不超过 140 字（可选）

• 中序遍历（inorder）

各节点在中序遍历序列中

添加图片注释，不超过 140 字（可选）

• 后序遍历（postorder）

添加图片注释，不超过 140 字（可选）

递归遍历算法和迭代遍历算法都需要渐进的线性时间，而且相对而言，前者更加简明；但是迭代算法的时间和空间复杂度的常系数相比较递归更小，同时从迭代遍历完成可以加深对相关过程和技巧的理解

1.2 递归式遍历 recursively traversal

比较难，但可以加深理解

先序遍历可以分解为两段，沿着最左侧通路自上而下的访问各节点，以及自底向上遍历的对应右子树

添加图片注释，不超过 140 字（可选）

1.3 一些算法的实现

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 题目debug地址：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

class Solution:
    def inorderTraversal(self, root):
        '''
        题目描述：给定一个二叉树的根节点root，返回它的中序遍历
        二叉树的遍历分为深度遍历和广度遍历
        深度遍历分为前序、中序和后序三种遍历方法
        - 前序，根节点、左子树、右子树
        - 中序，左子树、根节点、右子树
        - 后序，左子树、右子树、根节点
        广度遍历就是常说的层次遍历的方法


        :param root:
        :return:
        '''
        stack,ret=[],[]
        # 设计一个栈作为中间变量
        # ret为最终结果
        cur=root # 初始化最初的值为cur
        while stack or cur:
            # 当stack为空并且cur为空停止，也就是所有都遍历完，同时也不存在左子树
            if cur:
                # 如果当前节点非空，则取这个节点到stack中
                # 将当前节点设置为节点的left node
                stack.append(cur)
                cur=cur.left
            else:
                # 如果stack非空，但是当前节点为空。说明遍历到最左边的
                # 取当前节点的上一个
                cur=stack.pop()
                ret.append(cur.val)
                cur=cur.right
        return ret

0x02 二叉搜索树（Binary Search tree)

二叉搜索树是满足顺序性的二叉树

任一节点r的左右子树中，所有的节点（若存在）均不大于（不小于）r 为回避边界情况，暂定假设所有节点不想等，因此可以简化为 任意节点r的左（右）子树中，所有的节点（若存在）均小于（大于）r

添加图片注释，不超过 140 字（可选）

从本章开始，讨论的重点将逐步转向查找技术，实际上在之前的章节已经就此做过一些讨论，比如在vector和list等结果中，已经给出了对应的ADT结构，但是遗憾的是这种接口的效率无法令人满意。

比如vector向量模版，针对无序和有序向量的查找提供了find()和search（）接口。前者的实现策略是将目标对象与向量存放的对象逐个对比，硬刺需要O(n)时间，后者利用二分查找策略可以确保O(logN)时间内完成单次查找，但是一旦向量本身需要修改，无论是插入还是删除，在最坏情况下每次需要O（n）的时间。

所以对于线性结构来说，既要求对象集合的组成可以高效率地动态调整，同时也要求能够高效率查找，lInear data structure很难胜任，那么高效率的动态修改和高效率的静态查找能否同时兼顾，如有可能又应该采用什么样的数据结构？

之后两章希望逐步了解其中的故事，涉及到的数据结构种类比较多，按照基本和高级两章分别进行讲解

本章首先介绍树式查找的总体构思、基本算法以及数据结构，通过对二分查找策略的抽象与推广来定义并实现二叉搜索树（Binary search tree)结构，虽然在最坏情况下渐进时间复杂度与之前并无实质性改变，但是这给出来一种基于半线性的树形结构。 之后提出理想平衡和适度平衡等概念，并相应引入和实现AVL树这种典型的平衡二叉搜索树（Balanced binary search tree)，借助精巧的平衡调整算法，AVL树可以保证即使在最坏情况下，单次动态修改和静态查找也可以在O(logN)的时间内完成，在之后的选择中给出balanced m-way search trees

添加图片注释，不超过 140 字（可选）

2.1 查找算法（Search）

采用减而治之的思路与策略，执行的过程可以描述为

从树根出发，逐步缩小查找范围，直到发现目标或缩小到空树。节点的插入和删除操作，都需要首先调用查找算法，并根据查找结果确定后序的处理方式，因此这里引用方式传递子树根节点，为后续操作提供必要的信息

添加图片注释，不超过 140 字（可选）

效率：在二叉搜索树的每一层，查找算法至多访问一个节点，且只需常数时间，因此总体所需要时间应线性正比于查找路径的长度，或最终返回节点的深度，在最坏的情况下可以达到\omiga n的复杂度；由此我们得到汽水，若要控制单次查找在最坏情况下的运行时间，需要从二叉搜索树的高度入手，后面讨论的平衡二叉搜索树正是基于这个思路的改进

2.2 插入算法（Insert）

一般在二叉搜索树中插入新节点e的过程，可以描述为函数insert(): 它的过程是首先调用search() 查找e，如果返回位置非空，则说明已有雷同节点从，插入操作失败，否则x必然是_hot节点的某一个空孩子，于是创建这个孩子并存入e，之后更新全树的规模记录，并调用updateHeightAbove（）来更新x和历代祖先的高度

添加图片注释，不超过 140 字（可选）

效率： 主要小孩在对算法search()和updateHeightAbove()的调用，时间复杂度同样取决与新节点的深度，在最坏情况下不超过全树的高度

2.3 删除算法（Remove）

从二叉搜索树中删除节点，首先需要调用BST::search（）来判断目标点是否的确存在树中，如果存在则需要返回其位置，方能对其进行具体实施删除操作，在删除的过程中分为单分支情况和双分支情况

效率： 删除操作所需要的时间主要消耗在对search()、succ（）和updateHeightAbove（） 的调用，在树中的任何高度，它们都至多消耗O（1）时间，故总体的渐进时间复杂度也不会超过全树的高度

添加图片注释，不超过 140 字（可选）

0x03 平衡二叉搜索树（Balanced binary search tree）

3.1 树高和性能

根据对二叉搜索树的实现与分析，search()、insert()和remove（）等主要接口的运行时间，均线性正比于二叉搜索树的高度，在最坏情况下，二叉搜索树可能彻底退化为列表，此时查找效率甚至会降低O(n)，因此如果不能有效控制树高，实际性能比之前的向量和列表并没有明显的区别。

为了描述出现这种最坏的情况的概率，这里使用平均复杂度的概念来看二叉搜索树的性能，使用两种常见的随机统计口径来进行分析

• 随机生成(randomly generated)，在这种情况下可以看出二叉搜索树的平均高度为\Omega(LogN)
• 随机组成(randomly composed)， 平均查找长度为 \Omega(\Sqrt(N))

对比两种情况，可以看出两种不同的统计口径中对于平衡二叉树的统计次数的重叠，在第一种平衡中会越是平衡的树越会被统计多次，因此相对而言，按照后面口径多得到的估计值更加可信。

3.2 理想平衡和适度平衡

在之前看对于二叉树（Binary tree）的基本操作，比如search()、insert（）、remove（）的性能主要取决与树的高度，因此在节点数目固定的情况下，应当尽可能的降低高度，也就是尽可能的让兄弟子树的高度彼此接近，让全树更加平衡，比如对于包含n节点的二叉树，最理想的情况是高度为log_2N,这种就是理想平衡的情况；但是适当放松要求可以让我们得到比较好的效果，也就是适度平衡。

比如将树高限制在渐进不超过O(logN),相比较严格的理想平衡二叉树会更加放松，这里介绍的AVL树、伸展树、红黑树、KD树等都属于适度平衡的类别，因此也可以归纳为平衡二叉搜索树（Balanced binary search tree）

平衡二叉搜索树的适度平衡性就是通过对树中每一个局部增加某种限制条件来保证的，

比如在红黑树中，从树根到叶节点的通路总是包含一样多的黑节点；

比如在AVL树中，兄弟节点的高度相差不过1

这种限制条件设定是非常精妙的，除了适度平衡性，还具有局部性

1. 经过单次动态修改操作后，至多之后O（logN）处局部不在满足限制条件
2. 可以在O(logN)的时间内，让这O（logN）处局部乃至全树重新满足限制条件

由此来让失去平衡的二叉搜索树，必然可以迅速转换称为一颗等价的平衡二叉搜索树，等价二叉搜索树之间的转换过程称为等价交换

3.3 等价交换

首先定义等价，也就是中序遍历相同的二叉树之间是等价的，这种特点可以概括为“上下可变，左右不乱”

虽然二叉搜索树可以转换为理想平衡的完全二叉树，但是这种转换也是需要时间的，如何实现这种局部失衡的调整的同时来保证修复的速度？

3.4 旋转调整

最基本的修复手段就是通过围绕特定节点的选装来实现等价前提下的局部拓扑调整，也就是单旋和双旋，zig和zag

添加图片注释，不超过 140 字（可选）

zig和zag均属于局部操作，仅涉及常熟个节点及其之间的链接关系，故可以在常数时间内完成，在后面实现各种二叉搜索数平衡化算法是支撑性的基本操作。

0x04 平衡二叉搜索树（BBST，Balanced binary search tree）的总结

本来直接看AVL的，但是由于太难了，不如在此对这一类的平衡二叉搜索树做一个总结，防止以后概念的混淆，同时在学习这些BBST的时候要注意基本概念产生的树的深度和算法（基本操作insert()、remove()、search() 之间的关

• AVL树，平衡二叉树之一，应用相对其他数据结构比较少，windows对进程地址空间的管理用到了AVL；由G. M. Adelson-Velsky和E. M. Landis不1962年収明[36] ，并以他们名字的首字母命名
• 伸展树（Splay tree），按照“最常用者优先”的启发式策略，引入并实现伸展树，；由D. D. Sleator和R. E. Tarjan亍1985年发明
• B、B-、B+树，平衡多路查找树（查找路径不只两个），主要用在文件系统以及数据库中做索引等
• 红黑树，广泛应用在C++STL中，比如map和set、Java的TreeMap
• KD-树结构，在四叉树（quadtree）和八叉树（octree）的一般性推广，是在计算几何类问题的求解的模式

4.1 AVL树

在二叉查找树中，任一节点对应的两棵子树的最大高度差为 1，这样的二叉查找树称为平衡二叉树

添加图片注释，不超过 140 字（可选）

特点：

尽管可以保证最坏情况下的单次操作速度，但需在节点中嵌入平衡因子等标识；更重要的是，删除操作之后的重平衡可能需做多 达(logn)次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。

保持树平衡的目的是可以控制查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)，相比普通二叉树最坏情况的时间复杂度是 O(n) ，AVL树把最坏情况的复杂度控制在可接受范围，非常合适对算法执行时间敏感类的应用。

4.2 伸展树（Splay tree）

1）刚刚被访问过的节点，极有可能在不久之后再次被访问到

2）将被访问的下一节点，极有可能就处于不久之前被访问过的某个节点的附近

特点：

伸展树实现简便、无需修改节点 结构、分摊复杂度低，但可惜最坏情况下的单次操作需要(n)时间，故难以适用于核电站、医 院等对可靠性和稳定性要求极高的场合。

4.3 B、B-、B+树

为此，需要充分利用磁盘之类外部存储器的另一特性：就时间成本而言，读取物理地址连续 的一千个字节，与读取单个字节几乎没有区别。既然外部存储器更适宜于批量式访问，不妨通过 时间成本相对极低的多次内存操作，来替代时间成本相对极高的单次外存操作。相应地，需要将 通常的二叉搜索树，改造为多路搜索树在中序遍历的意义下，这也是一种等价变换。

特点：

B树是所有节点的平衡因子均等于0的多路查找树（AVL树是平衡因子不大于 1 的二路查找树）。B 树节点可以保存多个数据，使得 B 树可以不用像 AVL 树那样为了保持平衡频繁的旋转节点。B树的多路的特性，降低了树的高度，所以B树相比于平衡二叉树显得矮胖很多。B树非常适合保存在磁盘中的数据读取，因为每次读取都会有一次磁盘IO，高度降低减少了磁盘IO的次数。

4.4 红黑树

为此首先需在AVL树“适度平衡”标准的基础上，进一步放宽条件。实际上，红黑树 所采用的“适度平衡”标准，可大致表述为：任一节点左、右子树的高度，相差不得超过两倍

特点：

而节点的路径长度决定着对节点的查询效率，这样我们确保了，最坏情况下的查找、插入、删除操作的时间复杂度不超过O(log n)，并且有较高的插入和删除效率。

4.5 KD-树结构

需要在理解多维查询的基础上查询

添加图片注释，不超过 140 字（可选）

循着上一节采用平衡二叉搜索树实现一维查询的构思，可以将待查询的二维点集组织为所谓 的kd-树（kd-tree）⑥结构。在任何的维度下，kd-树都是一棵递归定义的平衡二叉搜索树。