令你头疼的[树]

小闫同学啊

发布于 2019-07-18 15:38:48

5260

发布于 2019-07-18 15:38:48

文章被收录于专栏：小闫笔记小闫笔记

正文共： 4912 字 7 图预计阅读时间： 13 分钟

每日分享

The first step to accepting yourself is to stop comparing yourself to others.

接受自己的第一步就是停止将自己和别人进行比较。

小闫语录：

每个人都喜欢将自己和其他人进行比较，换来的却是无尽的烦恼。因为在比较的过程中，往往迷失了最初的自己。将他人作为自己的榜样，为自己提供前进的动力，这样无可厚非。但请不要妄自菲薄，弄丢了真实的你。将自己的弱点与他人的优点比较，只能垂头丧气。深受一些鸡汤的毒害，也许你认为努力了就一定成功，奋斗了就一定能超越他人，他人能做到的你一定能做到。但是你忽略了一件事，一只小鸡，即使被人从悬崖上丢下去，它也不会像老鹰一样展翅翱翔。了解自己，正视自己，接受自己，成就自己。

一条插播

在进行树的讲解之前，先插播一个小的知识点（并不是广告，不要害怕）。这个知识点和树没有关系，是突然想到的一个知识点。那就是重载。

重载存在于静态语言中，是面向对象编程中一个重要的概念。它指的是多个相同函数名的函数，根据传入的参数个数，参数类型而执行不同的功能。函数重载实质上是为了解决编程中参数可变不统一的问题。

那么作为动态语言的python有重载吗？各说纷纭。我们从概念入手，『相同函数名的函数』在python中是不存在的，函数会根据从上到下的执行顺序发生覆盖。『传入的参数个数』也由于python的传参方式，可以限定在一个函数实施。『参数类型』因为python中不需要声明变量类型，所以函数可以接受任何类型的参数，也就无法根据参数类型来支持重载。

python中的传参方式有默认参数/可变参数/可变关键字参数。我们可以通过设置缺省值，让原本两个参数，只传一个参数即可。

所以说，python中本身就不需要重载。如果非要用这个重载的话，也是有解决办法的。python3.4中就提供了一个转发机制可以实现重载。

from functools import singledispatch
@singledispatch
def function(obj):
    print('%r'%(obj))

@function.register(int)
def function_test(obj):
    print('Integer: %d' % (obj))

@function.register(str)
def function_test(obj):
    print('String: %s' % (obj))

@function.register(list)
def function_test(obj):
    print('List: %r' % (obj))

if __name__ == "__main__":
    function(1)
    function('hello')
    function([1,2,3])

结果为：

Integer: 1
String: hello
List: [1, 2, 3]

树的介绍

树分为无序树和有序树。树中任意节点的子节点之间没有顺序关系，称为无序树。相反，有顺序关系就是有序树。

1.有序树

二叉树：每个节点最多有两个子树。

完全二叉树：二叉树，除最底层外，其他各层节点数目均已达到最大值，且最底层所有节点从左向右连续地紧密排列。不能左边的还没挂满，右边的已经挂了一些节点。
满二叉树：非叶节点都挂满了元素。也就是叶节点都在最底层的完全二叉树。
排序二叉树：根节点左边小于根节点，右边的大于根节点。也称为二叉查找树、二叉搜索树、有序二叉树。时间复杂度是 O(logn)
平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。

霍夫曼树：用于信息的编码和数据压缩。带权路径最短的二叉树称为哈夫曼树或最优二叉树。

B树：对读写操作进行优化的自平衡二叉查找树，能够保持数据有序，拥有的子树多于两个。（排序多叉平衡树）

2.树的存储

树的存储可以采用顺序存储和链式存储。将数据结构存储在固定的数组中，虽然在遍历速度上有一定的优势，但是所占空间比较大，是非主流的存储方式。二叉树通常以链式存储。在链式存储时，有个小缺陷，就是指针域指针个数不定。由于对节点的个数无法掌握，常见的树的存储都将多叉树转换成二叉树进行处理，子节点个数最多为2。

链式存储数据时每个结点有两部分，一部分存储数据，一部分存储指针，即指向下一个元素存储位置。我们可以设计下面这样的二叉链表存储。

lchild	data	rchild
左孩子指针	数据域	右孩子指针

3.树的应用场景

1.路由协议使用了树的算法。

2.MySQL数据库索引使用了树结构。

3.文件系统的目录结构。

4.很多经典的AI算法都是树搜索。比如决策树。

4.MySQL索引

假如我们执行下面的一个SQL语句：

select * from students where name = xxx;

它会进行全表扫描，对比名字是否相等，如果数据量大，IO量也会很大，IO影响比较大。但是通过索引字段来查询，就要快的多。MySQL索引多采用B+树，下面就来回答为什么。

索引是有序的；索引是单独的文件；如果通过索引字段查询会先扫描索引区。

首先说一下B树，网上有大量介绍B树的文章，因此本文只简单的做一个介绍。B树是一种多路搜索树，它的每个节点可以拥有多个子节点，M路的B树最多能拥有M个孩子节点。那么为什么设计成多路的呢？这是为了降低树的高度，而且路数越多，树的高度越低，查询效率就高，但是不能无限多路，那样B树会退化成一个有序的数组。B树在文件系统的索引上用的比较多，这是考虑到文件系统和数据库都存在硬盘上，涉及到IO。当数据量大的时候很难一次性将所有的数据加载进内存，就更别提查询了。那怎么办？多路存储优势就显现了，每次只需加载B树的一个节点。虽然内存中红黑树比B树效率高，但是涉及到磁盘操作，B树要更胜一筹。

再来说一下B+树。B+树是对B树的改良，它将所有的数据存在叶子节点，叶子节点之间还加了指针，构成了有序链表。这样一来呢，就有一个极大的优点，就是只需遍历叶子节点就能遍历所有的数据。

面试题：B+树的时间复杂度为log(n)，hash时间复杂度为O(1)，那么为什么MySQL还要使用B+树而不是hash呢？

答：这与使用场景有关，hash虽然快，但是适合查询单条数据。我们使用MySQL时，常常需要查询大量的数据，这时候由于B+树叶子节点保存了所有数据，还是有序链表，它的查询效率就要高的多了。而且数据库的索引保存在硬盘中，我们需要考虑到往内存中加载的情况。数据量大的时候，无法一次性加载入内存，就无法查询了。B+树可以分批加载，每次只加载一个节点，解决了上面的问题，而且由于树的高度很低，查询效率也高的多的多。

二叉树

二叉树上面也提到了，就是每个节点最多有两个子树的树结构，通常被称为“左子树”和“右子树”。

它有很多性质，我们需要掌握两个：

性质1:在二叉树的第i层上至多有 2^(i-1)个结点（i>0）

性质2:深度为k的二叉树至多有 2^k-1个结点（k>0）

深度就是树中节点的最大层次。也称为树的高度。

1.二叉树的实现

我们先定义一个节点类，用来创建节点对象。节点包含数据域和指针域。数据域用来保存数据，指针域保存左孩子和右孩子的指针。

class Node(object):
    def __init__(self,item):
        self.item = item
        self.lchild = None
        self.rchild = None

然后再定义二叉树，一开始为空，实现添加节点的方法。

添加元素的时候，我们可以先创建一个队列。然后从根节点开始检查。根节点为空则将元素添加到根节点位置，根节点不为空则将根节点添加进队列。然后由根节点检查左孩子和右孩子，执行同样的操作。其实就是按照由上至下，从左往右的顺序检查树，将节点挂在为空的位置。

class BinaryTree(object):
    def __init__(self):
        self.root = None

    def add(self,item):
        # 将数据保存成一个节点对象
        node = Node(item)
        # 如果根节点为空，将节点放在根节点位置
        if self.root is None:
            self.root = node
            return
        # 实现一个队列
        queue = [self.root]
        while queue:
            # 为了先进先出，弹出第一个元素
            cur = queue.pop(0)
            # 如果左孩子为空，将节点挂到左孩子位置
            if cur.lchild is None:
                cur.lchild = node
                return
            # 左孩子不为空，将左孩子添加进队列
            else:
                queue.append(cur.lchild)
            # 如果右孩子为空，将节点挂在右孩子位置
            if cur.rchild is None:
                cur.rchild = node
                return
            # 右孩子不为空，将右孩子添加进队列中
            else:
                queue.append(cur.rchild)

2.二叉树的遍历

二叉树因为是二维结构，具有纵向和横向两个方向，所以分为深度（高度）优先和广度（层次或者宽度）优先两种遍历方式。好像一张表，深度优先就是咱们按列遍历，广度优先则是按行遍历。

2.1广度优先遍历(层次优先遍历)

我们在上面二叉树类中定义一个广度优先的遍历方法。目的就是按照广度优先，将每一层的元素都遍历出来，先第一层再第二层。

def breadth_travel(self):
    # 如果根节点为空，树都没有，不用遍历了，直接返回即可。
    if self.root is None:
        return
    # 如果有树，我们就要实现一个队列，将所有的节点都添加都队列中。
    queue = [self.root]
    while queue:
        cur = queue.pop(0)
        print(cur.item)
        if cur.lchild is not None:
            queue.append(cur.lchild)
        if cur.rchild is not None:
            queue.append(cur.rchild)

travel[ˈtrævəl]：游历、旅行。我们引申为遍历。 breadth[brɛdθ]：宽度，广度。

2.2深度优先遍历

深度优先就是另一个维度优先的遍历方式。它按照根节点遍历的顺序分为三种方式：先序遍历、中序遍历和后序遍历。

先序遍历：根节点 --> 左子树 --> 右子树中序遍历：左子树 --> 根节点 --> 右子树后序遍历：左子树 --> 右子树 --> 根节点

2.2.1先序遍历

def pre_travel(self, node):
    # 设置递归退出条件
    if node is None:
        return
    print(node.item)
    self.pre_travel(node.lchild)
    self.pre_travel(node.rchild)

我们先遍历根节点，然后将左孩子作为根节点遍历，再将右孩子作为根节点遍历，采用递归的方法，直至节点为空。

2.2.2中序遍历

def mid_travel(self, node):
    # 设置递归退出的条件
    if node is None:
        return
    self.mid_travel(node.lchild)
    print(node.item)
    self.mid_travel(node.rchild)

2.2.3后序遍历

def post_travel(self, node):
    # 设置递归退出的条件
    if node is None:
        return
    self.post_travel(node.lchild)
    self.post_travel(node.rchild)
    print(node.item)