二叉查找树

二叉查找树

二叉查找树定义

二叉查找树 (Binary Search Tree) 是按照平衡顺序排列的二叉树, 也称二叉搜索树、 有序二叉树(ordered binary tree),排序二叉树(sorted binary tree)。

首先, 要符合二叉树的特性:

  • 可以为空;
  • 也可以拥有连个互不相交的子树, 即: 左子树和右子树。

平衡排序, 每个节点都有一个 key, 并且每个节点的 key 都符合:

  • 大于左子树中所有节点的 key;
  • 小于右子树所有节点的 key ;

二叉查找树节点必须包含四个字段:

  • 一个 Key 和一个 Value
  • 对左子树和右子树的引用;

对应的 C# 代码实现如下:

class Node {
    public TKey Key;
    public TValue Val;
    public Node Left, Right;
}

上面的代码中, TKeyTValue 是泛型类型, TKey 必须实现 IComparable<TKey> 接口, 用于比较两个 TKey 实例的大小。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n) 。 二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数 组等。

二叉查找树常用操作

二叉查找树必须引用根节点, 定义如下:

public class BST<TKey, TValue> where TKey : IComparable<TKey> {

    private Node root;

}

查找

既然是二叉查找树, 查找操作肯定要先实现了, 二叉查找树查找的思路是:

  • 从根节点开始查找, 对于任意节点:
    • 如果该节点为 null , 则返回空值或者该类型的默认值, 表示找不到;
    • 将节点的 key 与要查找的 key 进行比较;
      • 如果要查找的 key 小于节点的 key , 则继续查找该节点的左子树;
      • 如果要查找的 key 大于节点的 key , 则继续查找该节点的右子树;
      • 如果相等, 表示已经找到, 返回该节点的值。

对应的 C# 代码实现如下:

public TValue Get(TKey key) {
    return Get(root, key);
}

private TValue Get(Node x, TKey key) {
    if (x == null) {
        return default(TValue);
    }
    int cmp = key.CompareTo(x.Key);
    if (cmp < 0) {
        return Get(x.Left, key);
    }
    if (cmp > 0) {
        return Get(x.Right, key);
    }
    return x.Val;
}

添加

添加操作与查找操作类似, 如果能够在树中找到 key 对应节点, 则设置节点的值, 如果 找不到, 则返回一个新的节点, 实现代码如下:

public void Put(TKey key, TValue val) {
    root = Put(root, key, val);
}

private Node Put(Node x, TKey key, TValue val) {
    if (x == null) {
        return new Node {
            Key = key, Val = val, N = 1
        };
    }
    int cmp = key.CompareTo(x.Key);
    if (cmp < 0) {
        x.Left = Put(x.Left, key, val);
    }
    else if (cmp > 0) {
        x.Right = Put(x.Right, key, val);
    }
    else {
        x.Val = val;
    }
    x.N = 1 + Size(x.Left) + Size(x.Right);
    return x;
}

删除

从二叉查找树中删除指定的节点稍微复杂一点, 要分下面三种情况:

1 删除最小 Key 节点

要删除二叉查找树的最小 key 节点:

  • 查找当前结点的左节点, 直到找到一个左节点为空的节点;
  • 将该节点替换为该节点的右节点;

对应的 C# 代码实现代码如下:

public void DeleteMin() {
    root = DeleteMin(root);
}

private Node DeleteMin(Node x) {
    if (x.Left == null) {
        return x.Right;
    }
    x.Left = DeleteMin(x.Left);
    x.N = Size(x.Left) + Size(x.Right) + 1;
    return x;
}

2 删除最大 key 节点

删除最大 key 节点的思路与删除最小 key 节点的思路类似, 查找节点的右节点即可, 对 应的 C# 实现代码如下:

public void DeleteMax() {
    root = DeleteMax(root);
}

private Node DeleteMax(Node x) {
    if (x.Right == null) {
        return x.Left;
    }
    x.Right = DeleteMax(x.Right);
    x.N = Size(x.Left) + Size(x.Left) + 1;
    return x;
}

3 删除任意 key 节点

要从二叉查找树中删除 key 为 k 的节点, 假设树中找到的节点为 t , 要分下面几 种情况:

如果节点 t 没有子节点, 将节点 t 的父节点指向 t 的引用设置为空即可;

节点 t 的右节点或左节点为空, 则用 t 的另一个节点替换掉 t 即可;

节点 t 的左右节点均不为空, 则需要从 t 的右节点开始找到并删除最小的节点 x , 并用节点 x 替换 t 的位置;

实现代码如下:

public void Delete(TKey key) {
    root = Delete(root, key);
}

private Node Delete(Node x, TKey key) {
    if (x == null) {
        return null;
    }
    int cmp = key.CompareTo(x.Key);
    if (cmp < 0) {
        x.Left = Delete(x.Left, key);
    }
    else if (cmp > 0) {
        x.Right = Delete(x.Right, key);
    }
    else {
        if (x.Right == null) {
            return x.Left;
        }
        if (x.Left == null) {
            return x.Right;
        }
        Node t = x;
        x = Min(t.Right);
        x.Right = DeleteMin(t.Right);
        x.Left = t.Left;
    }
    x.N = Size(x.Left) + Size(x.Right) + 1;
    return x;
}

二叉查找树最终可能的形状如下图所示:

在实际算法中, 应避免最差情况, 因为在这种情况下, 二叉树退化成链表, 查找操作的 速度由 O(LogN) 降为 O(N) 就完全没有意义了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 在 Xamarin.iOS 项目中访问 ArcGIS 云端专题数据图层

    本文介绍如何在 Xamarin.iOS 项目中使用使用 ArcGIS Server 云端专题数据, 假设你已经准备好了 ArcGIS Client Runtim...

    beginor
  • 在 Angular 应用中创建包含组件

    包含组件就是指可以包含其它组件的组件, 以 Bootstrap 的卡片 (Card) 为例, 它包含页眉 (header) 、 主体 (body) 和 页脚 (...

    beginor
  • 使用 DataX 增量同步数据

    DataX 是阿里巴巴集团内被广泛使用的离线数据同步工具/平台,实现包括 MySQL、Oracle、SqlServer、Postgre、HDFS、Hive、AD...

    beginor
  • Java架构:一文读懂微服务架构的重构策略

    你很有可能正在处理大型复杂的单体应用程序,每天开发和部署应用程序的经历都很缓慢而且很痛苦。微服务看起来非常适合你的应用程序,但它也更像是一项遥不可及的必杀技。如...

    Java知音
  • 一文读懂微服务架构的重构策略

    你很有可能正在处理大型复杂的单体应用程序,每天开发和部署应用程序的经历都很缓慢而且很痛苦。微服务看起来非常适合你的应用程序,但它也更像是一项遥不可及的必杀技。如...

    猿天地
  • React源码解析之completeUnitOfWork

    (1) 关于completeUnitOfWork()在哪里使用到,请看下 React源码解析之workLoop 中的二、performUnitOfWork

    进击的小进进
  • 最小生成树-Prim算法和Kruskal算法

    Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里...

    用户1215536
  • AWS SDE的在线编程挑战

    之前听闻硅谷公司面试时特别注重算法、数据结构、系统设计思路,很少关注你到底用什么编程语言,更不关心你会多少个框架,最近参加了AWS的Online Assessm...

    KevinYan
  • 卷积神经网络中PET/CT图像的纹理特征提取

    Author: Zongwei Zhou 周纵苇 Weibo: @MrGiovanni Email: zongweiz@asu.edu Please cit...

    用户1332428
  • Hyperledger Fabric交易流程

    1.区块链数据,这是用文件系统存储在Committer节点上的。区块链中存储了Transaction的读写集。 2.为了检索区块链的方便,所以用LevelDB...

    用户2909867

扫码关注云+社区

领取腾讯云代金券