关于一些树

树

路径（path）：从结点 ，……， 的序列。如 A-E-J-P

路径的长（length）：路径的边数，k-1

深度（depth）：从根结点到本结点的唯一路径的长

前序遍历：对当前结点的处理工作是在儿子结点被处理之前进行的

中序遍历：对当前结点的处理工作是在左儿子结点被处理之后、右儿子结点被处理之前进行的

后序遍历：对当前结点的处理工作是在儿子结点被处理之后进行的

---

二叉查找树

对于一个结点，左子树中的值均小于这个结点，右子树中的值均大于这个结点

平均深度：O(log N)

template<class Object>
class BinarySearchTree {
public:

    BinarySearchTree();

    BinarySearchTree(const BinarySearchTree &rhs);

    BinarySearchTree(BinarySearchTree &&rhs);

    ~BinarySearchTree();

    const Object &findMin() const;

    const Object &findMax() const;

    bool contains(const Object &x) const {   // 查找书中是否存在值x
        return contains(x, root);
    }

    bool isEmpty() const;

    void printTree(ostream &out = cout) const;

    void makeEmpty();

    void insert(const Object &x) {
        insert(x, root);
    }

    void insert(Object &&x);

    void remove(const Object &x) {
        remove(x, root);
    }

    BinarySearchTree &operator=(const BinarySearchTree &rhs);

    BinarySearchTree &operator=(BinarySearchTree &&rhs);

private:
    struct Node {
        Object data;
        Node *left;
        Node *right;

        Node(const Object &theData, Node *lt, Node *rt) : data(theData), left(lt), right(rt) {}

        Node(Object &&theData, Node *lt, Node *rt) : data(theData), left(lt), right(rt) {}
    };

    Node *root;

    void insert(const Object &x, Node *&t);

    void insert(Object &&x, Node *&t);

    void remove(const Object &x, Node *&t);


    Node *findMin(Node *t) const;

    Node *findMax(Node *t) const;

    bool contains(const Object &x, Node *t) const;

    void makeEmpty(Node *&t);

    void printTree(Node *t, ostream &out) const;

    Node *clone(Node *t) const;
};

---

contains

判断是否存在于给定值相等的结点

通过递归调用，从根结点开始，如果比根结点小就递归到左子树；如果比根结点大就递归到右子树

template<class Object>
class BinarySearchTree {
public:
    bool contains(const Object &x) const {   // 查找书中是否存在值x
        return contains(x, root);
    }
private:
    Node *root;
    bool contains(const Object &x, Node *t) const;
}

template<class Object>
inline bool
BinarySearchTree<Object>::contains(const Object &x, BinarySearchTree::Node *t) const {
    if (t == nullptr)
        return false;
    else if (x < t->data)
        return contains(t->left);
    else if (t->data < x)
        return contains(t->right);
    else
        return true;
}

这种方式默认可以对data直接做出比较。实际上Object类型的对象判断可能需要用到运算符重载，这时候可以通过仿函数调用特定的比较方法

template<class Object, class Comparator=less<Object>>
class BinarySearchTree {
public:
    bool contains(const Object &x) const {   // 查找书中是否存在值x
        return contains(x, root);
    }
private:
    Node *root;
    Comparator isLessThan;	// 仿函数对象
    bool contains(const Object &x, Node *t) const;
}

template<class Object, class Comparator>
inline bool
BinarySearchTree<Object, Comparator>::contains(const Object &x, BinarySearchTree::Node *t) const {
    if (t == nullptr)
        return false;
    else if (isLessThan(x, t->data))
        return contains(x, t->left);
    else if (isLessThan(t->data, x))
        return contains(x, t->right);
    else
        return true;
}

---

findMin 和 findMax

根据查找二叉树的特性，min 必定在左子树的终止点，max 在右子树的终止点

可以通过递归和循环两种方式查找

递归

template<class Object, class Comparator>
inline BinarySearchTree<Object, Comparator>::Node *
BinarySearchTree<Object, Comparator>::findMin(BinarySearchTree::Node *t) const {
    if (t == nullptr)
        return nullptr;
    else if (t->left == nullptr)
        return t;
    else
        return findMin(t->left);
}

循环

template<class Object, class Comparator>
inline BinarySearchTree<Object, Comparator>::Node *
BinarySearchTree<Object, Comparator>::findMin(BinarySearchTree::Node *t) const {
    if (t == nullptr)
        return nullptr;
    else if (t->right == nullptr)
        return t;
    else
        return findMin(t->right);
}

---

insert

做好判断，采用递归插入

template<class Object, class Comparator>
inline void
BinarySearchTree<Object, Comparator>::insert(const Object &x, BinarySearchTree::Node *&t) {
    if(t== nullptr)
        t=new Node(x, nullptr, nullptr);
    else if(isLessThan(x,t->data))
        insert(x,t->left);
    else if(isLessThan(t->data,x))
        insert(x,t->right);
//    else
//        ;
//  此条件判断出被插入值已经存在于树中，不做任何操作
//  可以通过在Node类中置入计数器，判断被插入次数
}

---

remove

删除时存在多种情况

1. 被删除的结点是叶子结点，那直接删除即可
2. 被删除的结点只有一个子树，将子树接过来即可
   
3. 被删除的结点（下图中为结点 2）有两个子树，利用右子树的最小结点（下图中为结点 3）代替到结点 2 的位置。如果结点 3 存在右子树，将这个右子树接到结点 3 的父结点的左边即可
   

template<class Object, class Comparator>
inline void
BinarySearchTree<Object, Comparator>::remove(const Object &x, BinarySearchTree::Node *&t) {
    if (t == nullptr)
        return;
    else if (isLessThan(x, t->data))
        remove(x, t->left);
    else if (isLessThan(t->data, x))
        remove(x, t->right);
    else if (t->left != nullptr && t->right != nullptr) {
        t->data = findMin(t->right)->data;
        // 获得被删除结点的右子树中最小结点的值
        remove(t->data, t->right);
        // 在右结点中删除被移动的结点
    } else {
        Node *oldNode = t;
        t = (t->left == nullptr) ? t->left : t->right;
        // 如果被删除的结点有一个子树，则移动这个子树到被删除的位置
        delete oldNode;
    }
}

考虑到有些树情况特殊，可以使用懒惰删除的方法。即在Node中设置计数器，当计数器为 0 时表示这个结点不存在，执行真正的删除操作

---

析构函数

对所有的结点需要做一个delete操作，使用递归方法

template<class Object, class Comparator=less <Object>>
class BinarySearchTree {
public:
    ~BinarySearchTree() {
        makeEmpty();
    }

        void makeEmpty() {
        makeEmpty(root);
    }
}

template<class Object, class Comparator>
inline void
BinarySearchTree<Object, Comparator>::makeEmpty(BinarySearchTree::Node *&t) {
    if (t != nullptr) {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t = nullptr;
}

---

拷贝构造函数

template<class Object, class Comparator=less <Object>>
class BinarySearchTree {
public:
    BinarySearchTree(const BinarySearchTree &rhs) : root(nullptr) {
        root = clone(rhs.root);
    }

    BinarySearchTree(BinarySearchTree &&rhs) noexcept: root(nullptr) {
        root = clone(rhs.root);
    }
}

template<class Object, class Comparator>
inline BinarySearchTree<Object, Comparator>::Node *
BinarySearchTree<Object, Comparator>::clone(BinarySearchTree::Node *t) const {
    if (t == nullptr)
        return nullptr;
    else
        return new Node{t->data, clone(t->left), clone(t->right)};
}

---

AVL 树

树上任一结点的左子树和右子树的高度之差不超过 1

结点的平衡因子 = 左子树高度 - 右子树高度

AVL 树的各个结点的平衡因子只为-1，0，1

高度为h的 AVL 树，最少结点数S(h)=S(h-1)+S(h-2)+1

除去可能的插入和删除外，所有的树操作都可以以时间O(log N)执行

---

旋转：向 AVL 树中插入新结点时可能会破坏平衡，修正树来恢复平衡的操作叫旋转

思路：在一颗 AVL 树中插入一个结点导致不平衡，从这个结点开始，向上寻找第一个不平衡的子树（称为最小不平衡子树），对这个子树做调整，则整颗树恢复平衡状态

最小不平衡子树 A 存在四种情况：

1. LL：在 A 的左孩子的左子树中插入导致不平衡
2. RR：在 A 的右孩子的右子树中插入导致不平衡
3. LR：在 A 的左孩子的右子树中插入导致不平衡
4. RL：在 A 的右孩子的左子树中插入导致不平衡

---

旋转 LL

1. 在插入新结点前，根据二叉排序树特性，得出大小关系：BL < B < BR < A < AR
2. 新结点根据大小情况插入在BL
3. 将 B 结点右旋设置为根结点，A 结点右旋设置为根结点的右孩子
4. 根据大小关系，将 BL 设置为根结点 B 的左孩子，BR 设置为 A 结点的左孩子，AR 设置为 A 结点的右孩子

---

代码思路

gf->lchild/rchild 和 f 指向 A 结点，p 指向 B 结点

f->lchild = p->rchild
p->rchild = f
gf->lchild/rchild = p

---

旋转 RR

1. 在插入新结点前，根据二叉排序树特性，得出大小关系：AL < A < BL < B < BR
2. 新结点根据大小情况插入在BR
3. 将 B 结点左旋设置为根结点，A 结点左旋设置为根结点的左孩子
4. 根据大小关系，将 BR 设置为根结点 B 的右孩子，BL 设置为 A 结点的右孩子，AL 设置为 A 结点的左孩子

---

代码思路

f->rchild = p->lchild
p->lchild = f
gf->lchild/rchild = p

---

旋转 LR

1. 在插入新结点前，根据二叉排序树特性，得出大小关系：BL < B < CL < C < CR < A < AR
2. 将 BR 分为 C 结点及左右子树
3. 新结点根据大小情况插入 BR（具体是 CL 还是 CR 无所谓）
4. 左旋 C 结点，然后再右旋 C 结点

---

旋转 RL

1. 在插入新结点前，根据二叉排序树特性，得出大小关系：AL < A < CL < C < CR < B < BR
2. 将 BL 分为 C 结点及左右子树
3. 新结点根据大小情况插入 BR（具体是 CL 还是 CR 无所谓）
4. 右旋 C 结点，然后再左旋 C 结点

---

总结

左孩子右旋，右孩子左旋

LL/RR 只需右旋/左旋一次

LR/RL 需要右旋/左旋一次，然后右旋/左旋依次

即：在左就往右旋转，在右就往左旋转

---

B 树

概念

B 树，又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示。一颗 m 阶 B 树或为空树，或为满足如下特性的 m 叉树：

1. 树中每个结点至多有 m 棵子树，即至多含有 m-1 个关键字
2. 若根结点不是终端结点，则至少有两棵子树
3. 除根结点外的所有非叶结点至少有[m/2]（向上取整）棵子树， 即至少含有[m/2]-1个关键字
4. 非叶结点的结构
   

   n：关键字个数，[m/2]-1 <= n <= m-1

   K：关键字，

   P：指向子树根结点的指针

5. 对任一结点，其所有子树高度相同（高度一般排除叶子结点）
6. 所有的叶子结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定的树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）

---

B 树的高度

---

总结

---

插入删除

对于 m 阶 B 树，无论插入还是删除，时刻谨记结点中关键字个数 n 的限制：m/2 <= n <= m-1

根结点可以只有一个关键字

以 5 阶 B 树为例：2 <= n <= 4

---

插入

1. 空白根结点插入

   按序插入即可

2. 结点满时插入

   以中间位置（m/2）为界限，将关键字分成两部分，左边包含的关键字在原结点，右边包含的关键字在新结点，中间位置的结点插入原结点的父结点

   

3. 新元素一定按序插入到最底层的终端结点

   

4. 终端结点满时，重复操作 2，分裂并插入到父结点

   将终端结点的中间位置提到父结点时，应当选择此指向此终端结点的指针（①），在父结点中的右边

   

5. 父结点满时，分裂父结点，并将终端结点分配到第二层的结点中；会导致 B 树高度 +1

   

---

删除

1. 终端结点中的关键字可以直接删除，但是需要主要关键字个数是否低于下限

   

2. 非终端结点中的关键字再删除时，可以利用其直接前驱/直接后继来替换，也就是转换成终端结点中关键字的删除操作

   

3. 删除终端结点的关键字，如果删除后低于下限，可以从兄弟结点中借用前驱/后继来补充

   

   同理可得，借用前驱来填补

   戏称为，先当儿子后当爹法 hhhhhh

4. 当前驱和后继都借不出关键字（即都会突破下限），合并兄弟结点

   

   可能会合并根结点，合并后 B 树高度-1

---

B+ 树

m 阶 B+ 树满足以下条件：

1. 每个分支结点最多有 m 个子树/孩子结点
2. 非叶根结点至少有 2 颗子树，其他每个分支结点至少有[m/2]颗子树
3. 结点的子树个数与关键字个数相等

   如结点（3，9，15），有三个子树（1，3）、（6，8，9）和（13，15）

4. 所有叶节点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶节点按大小顺序链接起来（指针 p）
   所有非叶结点仅起索引作用，只有叶子结点中包含对应记录的存储地址
5. 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

---

查找

例：查找 9

方法一：

1. 查找根结点（15，56），小于 15，下转到第一个分支结点
2. 顺序查找到 9，下转第二个结点
3. 顺序查找到 9，获得指向其记录的指针

方法二：

由 p 指针直接顺序查找

---

磁盘 I/O

OS 利用 B+ 树记录磁盘上的文件目录结构

1. 磁盘被分为一个个区块，将第一个区块读取到内存，得到根结点记录的信息
2. 从信息中得到目标分区的存储区块，于是将目标区块再读取到内存中
3. 依次类推，最后找到对应的叶子结点，得到对应的文件存储的区块
4. 内存读取区块，得到目标文件

为什么不用 B 树而是用 B+ 树？

首先，看一下 B 树和 B+ 树的一个区别

B 树的结点中包含了关键字对应记录，即访问到这个结点时就可以得到记录

B+ 树中分支结点不包括关键字对应记录，只有在叶子结点中才记录有指向保存记录的地址（即叶子结点中也不能直接得到记录，需要根据指针指向对应的存储地址

而磁盘中的区块是固定大小的，则同样大小的区块，利用 B+ 树可以存储更多的关键字（毕竟不像 B 树一样直接把记录存储在结点中）

这样，同样的文件系统，B+ 树的阶更大，树更矮，磁盘的读取次数就更少，查找速度就更快

对比内存，磁盘的读取速度及其慢，更多的磁盘读取意味着更大的资源开销