数据结构---树(Tree)

1. 简介

在数据结构中,是一种层次结构的数据结构,由节点(node)组成,其中每个节点通过边(edge)与其他节点连接。树是一种非线性的数据结构,广泛用于表示具有层级关系的数据。常见的树包括二叉树、平衡树、红黑树、B树等。

1.1 基本概念

  • 节点(Node):树中的基本元素,包含数据和指向子节点的指针(或引用)。

  • 边(Edge):连接树中两个节点的连接线。

  • 根节点(Root):树的顶层节点,没有父节点。

  • 子节点(Child Node):某个节点的下级节点。

  • 父节点(Parent Node):某个节点的上级节点。

  • 叶节点(Leaf Node):没有子节点的节点。

  • 深度(Depth):树中某个节点到根节点的路径长度。

  • 高度(Height):树中某个节点到其最深叶节点的最长路径长度。

  • 子树(Subtree):树的某个节点及其所有后代节点构成的树。

1.2 常见树类型

  • 二叉树(Binary Tree):每个节点最多有两个子节点,通常称为“左子节点”和“右子节点”。

  • 二叉搜索树(Binary Search Tree, BST):一种特定的二叉树,满足以下性质:对于树中的每个节点,左子树的所有节点值小于节点的值,右子树的所有节点值大于节点的值。

  • 平衡树(Balanced Tree):是一种二叉搜索树,要求任何节点的左右子树高度差的绝对值不超过某个阈值(如AVL树和红黑树)。

  • 堆(Heap):一种完全二叉树,满足堆的性质(如最大堆和最小堆)。

  • B树(B-tree):一种自平衡的树数据结构,广泛应用于数据库和文件系统中。

1.3 树的常见操作

  • 插入操作:在二叉树或二叉搜索树中插入新节点。二叉树的插入操作较为简单,通常通过递归方式将节点插入到空子树中。二叉搜索树的插入需要遵循二叉搜索树的特性,将新节点放入合适的位置。

  • 删除操作:删除节点时需要处理三个情况:1)节点是叶子节点,直接删除;2)节点有一个子节点,用该子节点替代;3)节点有两个子节点,通常使用右子树的最小节点或左子树的最大节点替代。

  • 查找操作:在二叉搜索树中,查找操作通过与节点的值进行比较,从根节点开始向左或向右子树递归查找,直到找到目标节点。

  • 遍历操作:树的遍历可以分为深度优先遍历(前序、中序、后序遍历)和广度优先遍历(层次遍历)。遍历操作通常用于访问树中的所有节点。

    • 前序遍历(Pre-order):根节点 -> 左子树 -> 右子树

    • 中序遍历(In-order):左子树 -> 根节点 -> 右子树

    • 后序遍历(Post-order):左子树 -> 右子树 -> 根节点

    • 层次遍历(Level-order):逐层从上到下访问每一层节点

2. 树的分类

2.1 二叉树(Binary Tree)

二叉树是每个节点最多有两个子节点的树结构。二叉树广泛应用于数据存储和表示中。

  • 性质

    • 每个节点至多有两个子节点,通常称之为左子节点和右子节点。

    • 在二叉树中,节点的排列可以使得某些算法(如查找、插入和删除)非常高效。

  • 应用

    • 表达式树:用于表示数学表达式,叶节点是操作数,非叶节点是运算符。

    • Huffman编码树:用于压缩数据时,基于频率构造的树。

定义节点和二叉树的基本操作

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

public class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        root = null;
    }

    // 插入操作 (递归插入)
    public void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        return root;
    }

    // 查找操作
    public boolean search(int val) {
        return searchRec(root, val);
    }

    private boolean searchRec(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        } else if (val < root.val) {
            return searchRec(root.left, val);
        } else {
            return searchRec(root.right, val);
        }
    }

    // 中序遍历
    public void inorderTraversal() {
        inorderRec(root);
    }

    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.val + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.insert(10);
        bt.insert(5);
        bt.insert(15);
        bt.inorderTraversal();  // 输出: 5 10 15
    }
}

2.2 二叉搜索树(Binary Search Tree, BST)

二叉搜索树是一种特殊的二叉树,满足以下性质:

  • 对于每个节点,左子树的所有节点值小于当前节点的值,右子树的所有节点值大于当前节点的值。

  • 操作

    • 插入:从根节点开始,递归地将新节点插入到左子树或右子树。

    • 查找:从根节点开始,比较当前节点的值与目标值,根据大小关系选择左子树或右子树进行查找。

    • 删除:删除节点时,需要考虑节点的子节点情况,常用的策略是用右子树最小的节点替代被删除的节点。

  • 应用

    • 高效的查找、插入和删除操作。

    • 数据库中实现索引。

插入和查找操作

class BSTNode {
    int val;
    BSTNode left, right;

    BSTNode(int val) {
        this.val = val;
        left = right = null;
    }
}

public class BinarySearchTree {
    BSTNode root;

    public BinarySearchTree() {
        root = null;
    }

    // 插入操作 (递归)
    public void insert(int val) {
        root = insertRec(root, val);
    }

    private BSTNode insertRec(BSTNode root, int val) {
        if (root == null) {
            root = new BSTNode(val);
            return root;
        }
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else {
            root.right = insertRec(root.right, val);
        }
        return root;
    }

    // 查找操作
    public boolean search(int val) {
        return searchRec(root, val);
    }

    private boolean searchRec(BSTNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        } else if (val < root.val) {
            return searchRec(root.left, val);
        } else {
            return searchRec(root.right, val);
        }
    }

    // 中序遍历
    public void inorderTraversal() {
        inorderRec(root);
    }

    private void inorderRec(BSTNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.val + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(10);
        bst.insert(5);
        bst.insert(15);
        bst.inorderTraversal();  // 输出: 5 10 15
    }
}

2.3 平衡树(Balanced Tree)

平衡树是一类二叉搜索树,它的高度是有限制的,保证树的高度与节点数量呈对数关系。常见的平衡树包括AVL树红黑树

  • 性质:对于每个节点,其左右子树的高度差不超过1(AVL树)或对每个节点施加颜色和高度限制(红黑树)。

  • 应用:由于平衡树的高度较小,它能够提供高效的查找、插入和删除操作。

A是平衡树,B不是。

2.4 红黑树(Red-Black Tree)

红黑树是一种自平衡的二叉查找树,具有如下性质:

  • 每个节点是红色或黑色。

  • 根节点是黑色。

  • 每个红色节点的两个子节点都是黑色。

  • 从任意节点到其所有叶子节点的路径上,必须有相同数量的黑色节点。

  • 操作

    • 插入:插入新节点后,通过旋转和调整节点颜色来恢复红黑树的平衡。

    • 删除:删除节点后,可能需要通过旋转和调整来维持树的平衡。

  • 应用

    • Java中的TreeMapTreeSet,C++的std::mapstd::set

一个简化的红黑树(平衡树)插入和平衡算法

enum Color { RED, BLACK }

class RBTreeNode {
    int val;
    Color color;
    RBTreeNode left, right, parent;

    RBTreeNode(int val) {
        this.val = val;
        this.color = Color.RED;
        left = right = parent = null;
    }
}

public class RedBlackTree {
    private RBTreeNode root;
    private RBTreeNode TNULL;

    public RedBlackTree() {
        TNULL = new RBTreeNode(0);
        TNULL.color = Color.BLACK;
        root = TNULL;
    }

    // 左旋转
    private void leftRotate(RBTreeNode x) {
        RBTreeNode y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // 右旋转
    private void rightRotate(RBTreeNode x) {
        RBTreeNode y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    // 插入修正
    private void fixInsert(RBTreeNode k) {
        RBTreeNode u;
        while (k.parent.color == Color.RED) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left;
                if (u.color == Color.RED) {
                    u.color = Color.BLACK;
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rightRotate(k);
                    }
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    leftRotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right;
                if (u.color == Color.RED) {
                    u.color = Color.BLACK;
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        leftRotate(k);
                    }
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    rightRotate(k.parent.parent);
                }
            }
            if (k == root) {
                break;
            }
        }
        root.color = Color.BLACK;
    }

    // 插入节点
    public void insert(int key) {
        RBTreeNode node = new RBTreeNode(key);
        RBTreeNode y = null;
        RBTreeNode x = root;

        while (x != TNULL) {
            y = x;
            if (node.val < x.val) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node;
        } else if (node.val < y.val) {
            y.left = node;
        } else {
            y.right = node;
        }

        node.left = TNULL;
        node.right = TNULL;
        node.color = Color.RED;

        fixInsert(node);
    }

    // 查找操作
    public boolean search(int key) {
        return searchTreeHelper(root, key) != TNULL;
    }

    private RBTreeNode searchTreeHelper(RBTreeNode node, int key) {
        if (node == TNULL || key == node.val) {
            return node;
        }
        if (key < node.val) {
            return searchTreeHelper(node.left, key);
        }
        return searchTreeHelper(node.right, key);
    }

    public static void main(String[] args) {
        RedBlackTree rbt = new RedBlackTree();
        rbt.insert(10);
        rbt.insert(20);
        rbt.insert(30);
        System.out.println(rbt.search(20));  // 输出: true
        System.out.println(rbt.search(40));  // 输出: false
    }
}

2.5 B树(B- Tree)

B树是一种多叉自平衡树,广泛应用于数据库和文件系统中。

  • 性质

    • 节点可以有多个子节点,并且每个节点包含多个键值。

    • B树的所有叶子节点都在同一层,查找操作的效率与树的高度成对数关系。

  • 操作

    • 查找:从根节点开始,根据键值顺序逐层查找。

    • 插入:在合适的位置插入新节点,若节点已满,则进行分裂。

    • 删除:删除节点时需要保持树的平衡。

  • 应用

    • 数据库的索引结构,文件系统中的目录管理。

简单操作

import java.util.*;

class BTreeNode {
    List<Integer> keys;
    List<BTreeNode> children;
    boolean isLeaf;

    public BTreeNode(boolean isLeaf) {
        this.isLeaf = isLeaf;
        keys = new ArrayList<>();
        children = new ArrayList<>();
    }
}

public class BTree {
    private BTreeNode root;
    private int t;  // 阶数

    public BTree(int t) {
        this.t = t;
        root = new BTreeNode(true);
    }

    // 插入操作
    public void insert(int key) {
        if (root.keys.size() == 2 * t - 1) {
            BTreeNode s = new BTreeNode(false);
            s.children.add(root);
            split(s, 0);
            root = s;
        }
        insertNonFull(root, key);
    }

    private void insertNonFull(BTreeNode node, int key) {
        int i = node.keys.size() - 1;
        if (node.isLeaf) {
            node.keys.add(0);
            while (i >= 0 && key < node.keys.get(i)) {
                node.keys.set(i + 1, node.keys.get(i));
                i--;
            }
            node.keys.set(i + 1, key);
        } else {
            while (i >= 0 && key < node.keys.get(i)) {
                i--;
            }
            i++;
            BTreeNode child = node.children.get(i);
            if (child.keys.size() == 2 * t - 1) {
                split(node, i);
                if (key > node.keys.get(i)) {
                    i++;
                }
            }
            insertNonFull(node.children.get(i), key);
        }
    }

    private void split(BTreeNode parent, int i) {
        BTreeNode fullChild = parent.children.get(i);
        BTreeNode newChild = new BTreeNode(fullChild.isLeaf);
        parent.children.add(i + 1, newChild);
        parent.keys.add(i, fullChild.keys.get(t - 1));

        for (int j = t; j < fullChild.keys.size(); j++) {
            newChild.keys.add(fullChild.keys.get(j));
        }
        fullChild.keys = fullChild.keys.subList(0, t - 1);

        if (!fullChild.isLeaf) {
            for (int j = t; j < fullChild.children.size(); j++) {
                newChild.children.add(fullChild.children.get(j));
            }
            fullChild.children = fullChild.children.subList(0, t);
        }
    }

    public static void main(String[] args) {
        BTree btree = new BTree(3);
        btree.insert(10);
        btree.insert(20);
        btree.insert(5);
        btree.insert(6);
        btree.insert(12);
    }
}

2.6 B+树(B+ Tree)

B+树是B树的一个变种,所有数据值都保存在叶子节点中,非叶子节点仅作为索引。

  • 性质

    • 叶子节点通过链表连接,可以进行高效的范围查询。

    • 非叶子节点仅用于索引,不保存实际数据。

  • 操作

    • 查找:与B树相似,查找过程中只关注索引。

    • 范围查询:由于叶子节点通过链表连接,范围查询非常高效。

  • 应用

    • 数据库索引,尤其是在关系型数据库中的主键索引。

3. 并查集(Union-Find)

并查集是一种用于处理集合合并和查询问题的数据结构。它支持两种主要操作:

  • 查找(Find):确定某个元素属于哪个集合。

  • 合并(Union):将两个集合合并成一个集合。

树的实现

  • 并查集通常使用树来表示集合,每个集合对应一棵树,根节点表示集合的代表元素。

  • 路径压缩(Path Compression):在查找操作中,将沿途的节点直接连接到根节点,从而加速后续的查找操作。

  • 按秩合并(Union by Rank):合并操作时,始终将较小的树合并到较大的树下,保持树的深度较小。

应用场景

  • 图论:判断图中两个节点是否连通,求解最小生成树(Kruskal算法)。

  • 社交网络:检测社交网络中的用户是否属于同一群体。

  • 动态连通性问题:实时查询和更新网络中各个节点之间的连接关系。

4. 差异

  • 二叉树最适合简单应用,但如果不平衡,效率较低。

  • 二叉搜索树在插入和查找操作上较为高效,但在最坏情况下可能退化为链表。

  • AVL树红黑树提供平衡结构,保证了操作的对数时间复杂度,非常适合对性能要求较高的应用。

  • B树B+树多用于磁盘存储中,尤其适用于范围查询和数据库索引,因为它们是多路平衡树,能够处理更大规模的数据。B+树在数据库中应用广泛,特别适合做范围查询。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/937089.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【unity】从零开始制作平台跳跃游戏--界面的认识,添加第一个角色!

在上一篇文章中&#xff0c;我们已经完成了unity的环境配置与安装⬇️ 【Unity】环境配置与安装-CSDN博客 接下来&#xff0c;让我们开始新建一个项目吧&#xff01; 新建项目 首先进入unityHub的项目页面&#xff0c;点击“新项目”&#xff1a; 我们这个系列将会以2D平台…

Ubuntu K8s

https://serious-lose.notion.site/Ubuntu-K8s-d8d6a978ad784c1baa2fc8c531fbce68?pvs74 2 核 2G Ubuntu 20.4 IP 172.24.53.10 kubeadmkubeletkubectl版本1.23.01.23.01.23.0 kubeadm、kubelet 和 kubectl 是 Kubernetes 生态系统中的三个重要组件 kubeadm&#xff1a; 主…

【ARM】ARM架构麒麟V10安装jdk1.8

ARM架构麒麟V10安装jdk1.8&#xff0c;就一句话安装 yum install java-1.8.0-openjdk java-1.8.0-openjdk-devel 关注我&#xff0c;继续【ARM】安装mysql 简单快捷。

Redis--高并发分布式结构

目录 一、引言 二、redis 1.什么是redis&#xff1f; 三、基础概念 1.什么是分布式&#xff1f; 2.应用服务和数据库服务分离 3.负载均衡 4.分库分表 5.微服务架构 四、总结 一、引言 本篇文章就简单介绍一下什么是redis&#xff0c;以及一些关于高并发和分布式结构的…

Repo管理

文章目录 前言Repo介绍清单仓库清单仓库的组成 初始化Repo同步远程仓库Repo实际应用 前言 我们知道&#xff0c;Git是用来管理某一个仓库&#xff0c;那当一个项目用到了多个仓库时&#xff0c;怎么来同步管理这些仓库呢&#xff1f;这个时候就可以引入Repo管理。 Repo介绍 …

python 数据分析之地图数据绘制

python 数据分析之地图数据绘制 1、根据历史的2023年GDP数据做地图分析 import numpy as np import matplotlib import matplotlib.pyplot as plt matplotlib.rcParams[font.family] SimHei import pandas as pd import folium from folium import Map import geopandas as…

分治算法(单选题)

2-1 分数 2 下列多少种排序算法用了分治法&#xff1f; 堆排序插入排序归并排序快速排序选择排序希尔排序 A.2 B.3 C.4 D.5 正确答案 A 2-2 分数 2 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题&#xff0c;分别解决问题&#xff0c;最后将子…

探索 HTTP 请求头中的 “Host” 字段及其安全风险

探索 HTTP 请求头中的 “Host” 字段及其安全风险 大家好&#xff0c;今天我们来聊聊 HTTP 请求头中的“Host”字段&#xff0c;以及它的使用方法和安全风险。 什么是Host字段 在 HTTP 请求头中&#xff0c;“Host”字段是一个至关重要的部分。它告诉服务器&#xff0c;我们…

将 Ubuntu 22.04 LTS 升级到 24.04 LTS

Ubuntu 24.04 LTS 将支持 Ubuntu 桌面、Ubuntu 服务器和 Ubuntu Core 5 年&#xff0c;直到 2029 年 4 月。 本文将介绍如何将当前 Ubuntu 22.04 系统升级到最新 Ubuntu 24.04 LTS版本。 备份个人数据 以防万一&#xff0c;把系统中的重要数据自己备份一下~ 安装配置SSH访问…

渗透测试-前端验签绕过之SHA256

本文是高级前端加解密与验签实战的第1篇文章&#xff0c;本系列文章实验靶场为Yakit里自带的Vulinbox靶场&#xff0c;本文讲述的是绕过SHA256签名来爆破登录。 绕过 通过查看源代码可以看到key为 1234123412341234通过查看源代码可以看到是通过SHA256来进行签名的&#xff0…

解锁医学数据分析新姿势:堆叠图的奇妙世界

在医学数据分析中&#xff0c;数据的可视化是一个非常重要的环节。通过图形展示&#xff0c;我们可以更直观地理解数据之间的关系和趋势。今天&#xff0c;我们将介绍一种非常有用的图形——堆叠图&#xff08;Stacked Bar Chart&#xff09;&#xff0c;并展示如何在Python中使…

接口测试Day01-HTTP请求

概念 接口&#xff1a;系统之间&#xff08;外部系统与内部系统&#xff0c;内部系统与内部系统&#xff09;数据交通的通道。 接口测试&#xff1a;校验 接口回发的 响应数据 与 预期结果 是否一致。 接口测试&#xff0c;可以绕过前端界面。直接对 服务器进行测试&#xff01…

04、GC基础知识

JVM程序在跑起来之后&#xff0c;在数据的交互过程中&#xff0c;就会有一些数据是过期不用的&#xff0c;这些数据可以看做是垃圾&#xff0c;JVM中&#xff0c;这些垃圾是不用开发者管的&#xff0c;它自己会有一套垃圾回收系统自动回收这些内存垃圾&#xff0c;以备后面继续…

一、STM32MP257开发板初体验

文章目录 STM32MP257开发板初体验1. 硬件介绍2. 下载编译源码3. 烧录4. 启动 STM32MP257开发板初体验 从本篇文章开始本专栏将详细记录学习STM32MP257过程中的学习心得&#xff0c;旨在详细掌握嵌入式LINUX中的全流程内容&#xff0c;主要包括启动流程分析、驱动分析、Yocto系…

分析M0G突破后急剧下跌内因,x.game阐述不利面延续多久

MOG最新消息显示&#xff0c;美国唐纳德-的一则声明公开表示支持一种基于以太坊网络ERC-20代币标准的病毒式meme代币——Mog Coin&#xff08;MOG&#xff09;&#xff0c;这一消息迅速发酵。然而&#xff0c;令人意想不到的是&#xff0c;在这位全球知名政治人物的背书之后&am…

P8772 求和 P8716 回文日期

文章目录 [蓝桥杯 2022 省 A] 求和[蓝桥杯 2020 省 AB2] 回文日期 [蓝桥杯 2022 省 A] 求和 题目描述 给定 n n n 个整数 a 1 , a 2 , ⋯ , a n a_{1}, a_{2}, \cdots, a_{n} a1​,a2​,⋯,an​, 求它们两两相乘再相加的和&#xff0c;即 S a 1 ⋅ a 2 a 1 ⋅ a 3 ⋯ a…

【优选算法】二分算法(在排序数组中查找元素的第一个和最后一个位置,寻找峰值,寻找排序数组中的最小值)

二分算法简介&#xff1a; 提到二分我们可能都会想起二分查找&#xff0c;二分查找要求待查找的数组是有序的&#xff0c;与我们今天讲的二分算法不同&#xff0c;并不是数组元素严格按照有序排列才可以使用二分算法&#xff0c;只要数组中有一个点可以将数组分为两个部分&…

升级Ubuntu 24.04 LTS报错“Oh no! Something has gone wrong.”

强烈建议&#xff1a;升级Ubuntu系统之前先配置好SSH远程访问 最近升级Ubuntu系统&#xff08;18->24&#xff09;&#xff0c;经历了一些惊魂时刻&#xff0c;复盘下来没有重装系统的最得益于SSH访问。 在升级到24.04版本时&#xff0c;一切似乎表现得很正常&#xff0c;…

大模型底座 Transformer 的核心技术解析

1. 引言 说明目标 在深度学习领域&#xff0c;Transformer架构已成为近年来最重要的技术突破之一。它最早由Vaswani等人在2017年的论文《Attention is All You Need》中提出&#xff0c;迅速成为自然语言处理&#xff08;NLP&#xff09;和其他序列建模任务的核心工具。传统方法…

2.生成Transformation

目录 前言 Source FlatMap KeyBy sum print 总结 前言 以下面的WordCount为例 package com.wlh.p1;import org.apache.flink.api.common.functions.FlatMapFunction; import org.apache.flink.api.java.functions.KeySelector; import org.apache.flink.api.java.tuple…