树 - 二叉查找树

2020-03-23 本文已影响0人天命_风流

二叉查找树也叫二叉搜索树，是二叉树中最常见的一种类型。顾名思义，二叉查找树是为了实现快速查找而生的，当然，它不仅仅支持快速查找，还支持快速插入、删除数据。

二叉查找树

二叉查找树要求，在树种的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，右子树的每个节点的值，都要大于这个节点的值。注意，这里说的是子树中的每个节点，而不是孩子节点中的值：

二叉查找树.jpg

二叉查找树的查找操作

首先取根节点，如果它的值等于查找值，就返回。如果查找值小于该节点，则进入左子树查找，如果大于，进入右子树查找。这是一个递归查找的过程，具体可以看下面的过程：

二叉查找树-查找.jpg

有代码帮助你理解：

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

二叉查找树的插入操作

插入操作类似查找操作。新插入的数据一般都会落在叶子节点上，我们依然主要比对插入数据和节点的大小关系。

如果插入的数据比节点数据大，且右子树为空，直接将数据插入到右节点的位置。如果不为空，就在递归遍历右子树，直到找到插入位置为止。
小于的情况也类似。

下面是插入的过程：

二叉查找树-插入.jpg
代码如下：

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

二叉查找树的删除操作

由于涉及二叉树的结构连续，二叉查找树的删除操作比较麻烦，需要分成三种情况：

要删除的节点没有子节点，我们只需要将父结点的指针设置为 null。例如图中删除节点 55 。
要删除的节点只有一个子节点，我们需要更新其父结点的指针指向要删除节点的子节点。例如图中删除节点 13 ，需要将 16 的 left 指针指向 15 。
要删除的节点有两个子节点，我们需要找到右子树中的最小节点代替该节点，并将最小节点删除。（也可以使用左子树中的最大节点代替）。例如途中删除节点18。

二叉查找树-删除.jpg

代码如下：

public void delete(int data) {
  Node p = tree; // p指向要删除的节点，初始化指向根节点
  Node pp = null; // pp记录的是p的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP表示minP的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将minP的数据替换到p中
    p = minP; // 下面就变成了删除minP了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

实际上，我们还有一个非常简单、取巧的方法，就是将要删除的节点做一个 “deleted” 标记，而不真正将它在内存中删除。这种方法会浪费内存空间，但是删除操作变得简单了许多。

二叉查找树的其它操作

中序遍历二叉查找树，可以输出有序数列，时间复杂度为O(n)。
支持快速查找最大节点和最小节点。
支持快速查找前驱节点和后继节点。（注意，这里的前驱节点是指数据排序后的前驱数据，而不是父节点。）

支持重复数据的二叉查找树

之前我们一直讨论的都是数据中没有重复数据的情况，现在我们有聊一聊对重复数据的两种应对办法：

第一种方法比较容易：一个节点不一定要存储一个数据，我们可以通过链表或其它支持动态扩容的数据结构，把值相同的数据都存储在同一个节点上。
第二种方式比较优雅：
在插入过程中，如果一个节点值和当前值相同，就默认把它们当做比当前节点大处理（放入右子树）。二叉查找树-插入相同的数.jpg

在查找数据的时候，遇到相同的节点，我们并不停止查找，而是继续在有子树中查找，直到遇到叶子节点。

二叉查找树-查找可能相同的数.jpg 对于删除操作，我们可以先找到每个要删除的及诶但，然后再按之前的删除操作依次删除。

二叉查找树-删除相同的数.jpg

下面是我自己写的二叉排序树，可以作为参考：

import random


class Binary_Node():
    '''
    二叉树节点
    '''

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def find(root, data, res=[]):
    '''
    查找函数
    :param root: 树的根节点
    :param data: 要查找的数值
    :param res: 一个列表，返回所有 node.data = data 的结点
    :return: res
    '''

    if data == root.data:
        res.append(root)

    # print('这里是find函数，节点数据为{}，查找数据为{}'.format(root.data, data))

    if data < root.data:
        if root.left:  # 如果左子树存在，继续递归
            return find(root.left, data, res)
        else:  # 不存在，返回None
            return res
    else:
        if root.right:  # 如果右子树存在，继续递归
            return find(root.right, data, res)
        else:  # 不存在，返回None
            return res


def insert(root, data):
    '''
    这个函数负责将 data 插入到二叉排序树中
    :param root: 根节点
    :param data: 插入的数值
    :return:None
    '''

    if data < root.data:
        if root.left:  # 如果左子树存在，继续递归
            insert(root.left, data)
        else:  # 如果左子树不存在，进行插入
            temp = Binary_Node(data)
            root.left = temp

    else:
        if root.right:  # 如果右子树存在，继续递归
            insert(root.right, data)
        else:  # 不存在，插入
            temp = Binary_Node(data)
            root.right = temp


def delete(data, root=None, parent_root=None, ):
    '''
    删除所有节点值为 data 的结点
    :param data: 删除的值
    :param root: 根节点，注意这里使用了递归，所以 root 不一定是二叉排序树的 根节点
    :param parent_root:如果root不是树的根节点，parent_root 就是 root 的父节点
    :return:None
    '''
    if not root:  # 如果当前节点为None,直接返回即可
        return

    if root.data != data:  # 如果当前节点值和删除值不同，继续递归
        if data < root.data:
            delete(data, root=root.left, parent_root=root)
        else:
            delete(data, root=root.right, parent_root=root)

    else:  # 节点值相同，也就是 root.data == data 的情况。需要对节点删除并维护树
        if root.left and root.right:  # 如果root有两个子树，将右侧最小节点替换这个节点值
            minp = root.right  # minp最终会变成root的右侧子树的最下节点
            minpp = root  # minpp是minp的父节点
            while minp.left:  # 一直找到最大值节点
                minpp = minp
                minp = minp.left

            root.data = minp.data  # 交换节点值

            if minpp.left == minp:  # 维护树的结构
                minpp.left = None
                del minp
            elif minpp.right == minp:  # root右子树的最大值为root.right指向的结点的情况
                minpp.right = minp.right
                del minp
            # print('两个节点')
            delete(data, root=root, parent_root=parent_root)  # 由于树种可能存储了相同的数值，所以依然需要递归

        else:  # 如果 root 只有一个子树或没有孩子
            if root.left != None:
                child = root.left
            elif root.right != None:
                child = root.right
            else:
                child = None
            # child为需要接续的结点

            if parent_root == None:  # 如果root为根节点
                root = child
            elif parent_root.left == root:
                parent_root.left = child
            else:
                parent_root.right = child

            # print('一个节点')
            delete(data, root=child, parent_root=parent_root)#应对重复值的情况


def creat_binary_tree(d_list):
    '''
    创建一个二叉排序树
    :param d_list: 列表，根据列表创建排序树
    :return: 树的根节点
    '''
    root = Binary_Node(d_list[0])#用列表第一个数据做根节点，之后的数据都是对这个树的插入
    for i in d_list[1:]:
        insert(root, i)

    return root


def show_tree(root):
    '''
    使用中序遍历输出树的数据，根据排序树的性质，输出应当是有序的
    :param root: 根
    :return:None
    '''

    if not root:
        return

    show_tree(root.left)
    print(root.data, end=' ')
    show_tree(root.right)


if __name__ == '__main__':
    data = [i for i in range(10)]
    random.shuffle(data)

    print(data) # 创建了一个无序的列表，我们将用这个列表构建二叉排序树

    root = creat_binary_tree(data)
    insert(root, 1)
    show_tree(root)

    x = find(root, 1)
    print([i.data for i in x])

    delete(1, root=root, parent_root=None)
    show_tree(root)

二叉查找树的时间复杂度分析

来看一下下面的二叉查找树：

二叉查找树-时间复杂度分析.jpg
通过上面的图片可以看出，二叉查找树的时间复杂度其实和树的高度成正比，也就是O(height)。所以，求树查找的时间复杂度可以转换成求查找树的高度，针对不同的情况，我们有不同的复杂度：

最坏情况：二叉查找树退化成一个链表，复杂度为O(n)。
一般情况：二叉树不规则，这时复杂度也难以分析。
最好情况：二叉树是一棵完全二叉树，通过分析，可以算出其高度小于等于 logn，故复杂度为O(logn)。

二叉查找树和散列表的对比

散列表的插入、删除、查找操作的时间复杂度为常量级。而二叉树在平衡的情况下相应的时间复杂度为O(logn)，那么相对散列表，我们为什么还要使用二叉查找树呢？

这可能有以下几点原因：

散列表中的数据无序存储，而二叉查找树可以通过中序遍历很容易的地出有序序列。
散列表的扩容操作耗时，且面对散列冲突时性能不稳定。
散列表的构造比二叉查找树要服装，需要考虑的东西很多。比如，散列函数的设计、冲突解决方案、扩容等。而平衡二叉查找树只需要考虑平衡性一个问题，且该问题的解决方案比较成熟。

小结

二叉查找树是一种特殊的二叉树，它支持快速查找、插入、删除等操作。

二叉查找树中，每个节点的值都大于左子树节点的值，小于右子树节点的值。当面对重复数据的时候，我们可能需要做一些额外操作。

二叉查找树的操作和树的高度成正比，当查找树退化成链表时，复杂度会升高。

为了避免退化，我们可以使用平衡二叉树，而在这之中，最出名的是红黑树，但是红黑树的实现过于复杂，所以你只需要知道，红黑树是一个动态数据结构，可以很方便地实现数据的查找、插入、删除等操作即可。

以上就是这一节的全部内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间