文档章节

常见数据结构(二)-树(二叉树,红黑树,B树)

浮躁的码农
 浮躁的码农
发布于 06/21 23:40
字数 1899
阅读 15
收藏 0
点赞 0
评论 0

 

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树

写在前面

Binary Search Tree(二分查找树)

定义:A BST is a binary tree in symmetric order.

A binary tree is either:

  • Empty.
  • Two disjoint binary trees (left and right).

Symmetric order.Each node has a key, and every node’s key is:

  • Larger than all keys in its left subtree.
  • Smaller than all keys in its right subtree.

在java的实现中,每个节点(Node)由四个域组成:key,value,left,right。即:键,值,左子树,右子树。

private class Node {
    private Key key;
    private Value val;
    private Node left, right;

    public Node(Key key, Value val) {
        this.key = key;
        this.val = val;
    }
}

Binary Search Tree

  • 查找:得到相应键的值,若无此键则返回null.
/* 查找 */
public Value get(Key key) {
    Node x = root;
    while (x != null) {
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x = x.left;
        } else if (cmp > 0) {
            x = x.right;
        } else { // if (cmp == 0)
          return x.val;
        }
    }
    return null;
}
  • 插入:如果小,往左;如果大,往右;如果null,插入;如果存在,覆盖。
/* 插入 */
public void put(Key key, Value val) {
    root = put(root, key, val);
}

/* 辅助函数,递归调用 */
private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val);
    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 { // if (cmp == 0)
        x.val = val;
    }
    return x;
}

比较的次数为节点的深度+1,由于插入节点的顺序会有差异,所以树的高度不确定,最坏的情况是N个节点的树高度为N。

  • 删除:列出下面几种处理方法 
    • 将值置为null,在树中保留键
    • 删除最小值:一直向左找到左子树为null的节点,用它的右子节点代替它。
    • Hibbard deletion

下面重点讲一下Hibbard deletion,分为三种情况:

  1. 没有子节点的节点,将其parent link置为null即可。
  2. 有一个子节点的节点,删除该节点并以子节点代替即可。
  3. 有两个子节点的节点,找到该节点t的下一个节点x(即右子树的最小节点),在右子树删除这个节点,并将该节点x放到t的位置。
/* 删除 */
private Node delete(Node x, Key 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; // no right child
        if (x.left == null) return x.right; // no left child
        Node t = x;
        x = min(t.right); // replace with successor
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    x.count = size(x.left) + size(x.right) + 1;
    return x;
}

2-3 Search Trees(2-3树)

在介绍红黑树前,先介绍一下2-3树,便于后面理解红黑树。

2-3树是二分查找树的变形,每个节点是下面两种情况之一:

  • 2-node:一个键,两个分叉(smaller,larger)
  • 3-node:两个键,三个分叉(smaller,between,larger)

2-3 trees

在底部向一个3-node插入。

  • 向3-node插入一个键,临时成为一个4-node
  • 将4-node中间的key移动到父节点
  • 向上重复
  • 如果到了顶端的根节点,且根节点是4-node,将其分成3个2-nodes.

总结起来就是:当插入的值导致节点变四叉时进行分裂,将中间的值传给上一个节点,并将另外两个值作为两个子节点分开,若上一节点也因此变成四叉,依次类推。分裂4-node是一个local transformation,只会进行常数次数的操作。高度加一由且仅由顶节点分裂造成

2-3 trees proof

树的高度,在查找和插入时,保证了logarithmic的性能。

  • Worst case: lg N. [all 2-nodes]
  • Best case: log3 N ≈ 0.631 lg N. [all 3-nodes]

Red-Black BSTs(红黑树)

这里的红黑树均指Left-leaning red-black BSTs。主要是用二叉树的形式来表示2-3树,用一个“内部”的left-leaning连接来表示3-node。red link是2-3tree的三叉节点的连接两个key的内部link,大值作为根节点,小值作为左子节点,故名left leaning 红黑树。

红黑树定义

一个等价的定义,A BST such that:

  • No node has two red links connected to it.
  • Every path from root to null link has the same number of black links.
  • Red links lean left.

红黑树对应2-3树

红黑树的java表示

private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node {
    Key key;
    Value val;
    Node left, right;
    boolean color;// color of parent link
}

private boolean isRed(Node x) {
    if (x == null) return false;
    return x.color == RED;
}

左转-右转-变色

红黑树插入过程中可能用到的三个基本操作(左转,右转,变色):

  • left rotate
  • right rotate
  • flip colors

下面依次介绍

  • 左转

红黑树左转

/* left rotate */
private Node rotateLeft(Node h) {
   assert isRed(h.right);
   Node x = h.right;
   h.right = x.left;
   x.left = h;
   x.color = h.color;
   h.color = RED;
   return x;
}
  • 右转

红黑树右转

/* right rotate */
private Node rotateRight(Node h) {
    assert isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    return x;
}
  • 变色

红黑树变色

/* flip colors */
private void flipColors(Node h) {
    assert !isRed(h);
    assert isRed(h.left);
    assert isRed(h.right);
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

插入操作

红黑树插入两个节点

从图中可以看出,插入的次序不同,需要转换的操作也不同,分三种情况(图中每一列是一种情况):

  1. 已有a和b时,c插入在b的右子节点,直接变色即可
  2. 已有b和c时,a插入在b的左子节点,先右转把b滑上去,成1中的状态,再变色即可
  3. 已有a和c时,b插入在a的右子节点,先左转把a滑下去,成2中的状态,再右转+变色即可

从上面的分析可以看出,三种情况之间有转换关系,且逐步趋向简单,如下图所示:

红黑树状态转换

根本原因在于,2-3树中,是把3-node中处于中间的那个键传递给父节点,所以在红黑树中,当有一个节点连了两个 red link时,说明这三个点是一个3-node,但次序还需要调整,从而达到中间键在最上的状态,进而变色。而这个这个调整的趋势则是先让b处于a,c中间(即a的父,c的左子,成一条线),再让b成为a,c的父节点,最后变色。记住这个顺序和原因,写代码就简单了,状态3->状态2->状态1

private Node put(Node h, Key key, Value val) {
    //insert at bottom (and color it red)
    if (h == null) return new Node(key, val, RED);
    int cmp = key.compareTo(h.key);
    if (cmp < 0) {
        h.left = put(h.left, key, val);
    } else if (cmp > 0) {
        h.right = put(h.right, key, val);
    } else {
        h.val = val;
    }

    if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);// lean left
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);//balance 4-node
    if (isRed(h.left) && isRed(h.right)) flipColors(h);//split 4-node

    return h;
}

红黑树的高度 h <= 2 lg N,证明:

  • Every path from root to null link has same number of black links.
  • Never two red links in-a-row.

B-Trees(B树)

最后简单提一下B树,就是将2-3树一般化,将每个节点的key-link pairs增加到 M - 1

  • At least 2 key-link pairs at root.
  • At least M / 2 key-link pairs in other nodes.
  • External nodes contain client keys.
  • Internal nodes contain copies of keys to guide search.

B-Trees

在B树中查找

  • Start at root.
  • Find interval for search key and take corresponding link.
  • Search terminates in external node.

在B树中插入

  • Search for new key.
  • Insert at bottom.
  • Split nodes with M key-link pairs on the way up the tree.

命题:A search or an insertion in a B-tree of order M with N keys requires between log M-1 N and log M/2 N probes

本文转载自:https://blog.csdn.net/h3243212/article/details/52819734

共有 人打赏支持
浮躁的码农

浮躁的码农

粉丝 58
博文 714
码字总数 141530
作品 0
松江
程序员
JAVA中的数据结构 - 真正的去理解红黑树

一, 红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-...

浮躁的码农
2015/06/23
0
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0
算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方
2017/12/14
0
0
Java关于数据结构的实现:树

关于作者 郭孝星,程序员,吉他手,主要从事Android平台基础架构方面的工作,欢迎交流技术方面的问题,可以去我的Github提issue或者发邮件至guoxiaoxingse@163.com与我交流。 文章目录` 一 ...

郭孝星
2017/09/28
0
0
数据结构之树

数据结构之树 目录: 二叉树的结构 二叉树的性质 二叉树的遍历 二叉树的特例 二叉树典型程序 树是一种编程中常常用到的一种数据结构,它的逻辑是:除了根结点之外每个结点只有一个父结点,根...

花开半夏qb
2016/11/29
0
0
JDK TreeMap Red-Black Tree

介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewi...

zuoer
2011/12/18
0
0
数据结构(C语言版)第五章:树

5.2 二叉树 我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正...

fzyz_sb
2013/12/07
0
2
Java集合--TreeMap完全解析

4 TreeMap 上一篇,介绍了集合框架中的HashMap对象,主要讲述了HashMap的底层实现和基本操作。本篇,让我们继续来学习Map集合,今天的主角是TreeMap。 相比于HashMap来说,TreeMap理解起来更...

贾博岩
2017/09/10
0
0
当我们在聊TreeMap(一)——红黑树详解Java代码实现

本文出自:https://blog.csdn.net/DT235201314/article/details/80661157 一丶概述 上一篇讲HashMap,避开了红黑树,这边讲TreeMap,好好说一下红黑树。 二丶概述目录图 三丶聊聊TreeMap 数据...

天一方蓝
06/13
0
0
常见数据结构(二)-树(二叉树,红黑树,B树)

常见数据结构(二)-树(二叉树,红黑树,B树) 标签: algorithms [TOC] 本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课...

brianway
2016/10/14
763
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Jvm堆内存的划分结构和优化,垃圾回收详解(详细解答篇)

在JVM中堆空间划分如下图所示 上图中,刻画了Java程序运行时的堆空间,可以简述成如下2条 1.JVM中堆空间可以分成三个大区,新生代、老年代、永久代 2.新生代可以划分为三个区,Eden区,两个幸...

嘻哈开发者
8分钟前
0
0
CentOS 7.4 设置系统字符编码

1.语言变量LANG在 /etc/locale 文件中。 2.可以通过/ect/profile 来修改LC_TYPE 变量的值 添加如下代码 export LC_ALL="zh_CN.GBK" export LANG="zh_CN.GBK" 到profile文件中,变量的可以修改...

qimh
9分钟前
0
0
Kafka相关使用

安装前提,需要有jdk环境,还有zookeeper环境 zookeeper下载地址:https://www.apache.org/dyn/closer.cgi/zookeeper/ zookeeper安装参考:https://www.jianshu.com/p/f7037105db46 kafka的下......

朝如青丝暮成雪
10分钟前
0
0
CentOS7 解决无法使用tab自动补全 tab代码提示

一、前言 对于刚刚开始学习linux的新人来说,linux的一切都显着神秘,只能惊叹于大牛在Linux上行云流水的操作。今天介绍一下在linux中自动补全的功能。 对于新人来说,在不懂得技巧的情况下,...

ziluopao
16分钟前
0
0
redis安装

https://www.cnblogs.com/feijl/p/6879929.html

ghou-靠墙哭
16分钟前
0
0
Spring核心——注解自动装载

从配置上扩展 之前的文章介绍了Spring的IoC容器配置管理方面的详细内容,需要了解的可以从IoC容器的设计模式开始阅读。在介绍基于注解配置的配置之前我们再重复一下在之前提到的基本认识: ...

随风溜达的向日葵
19分钟前
1
0
ElasticSearch学习(8)—— SearchType

Elasticsearch有四种类型的SearchType 1、query and fetch 向索引的所有分片(shard)都发出查询请求,各分片返回的时候把元素文档(document)和计算后的排名信息一起返回。这种搜索方式是最...

叶枫啦啦
21分钟前
0
0
MYSQL备份工具-mysqldump

介绍 mysqldump 是文本备份还是二进制备份 它是文本备份,如果你打开备份文件你将看到所有的语句,可以用于重新创建表和对象。它也有 insert 语句来使用数据构成表。 语法 mysqldump 的语法是...

郭恩洲_OSC博客
23分钟前
0
0
我的第一个go web框架

使用了beego等go web开发框架之后,感觉各种不方便,尤其是在接收参数、和自定义输出的时候,各种难受,定义各种model,这不是找事情嘛??尤其是在角色权限控制的时候我也感觉力不从心。。。...

独坐苔痕但观罗敷
24分钟前
0
0
自动代码生成图形化工具

自动生成Spring代码 https://github.com/EliMirren/Spring-generator 自动生成Vertx https://gitee.com/duhua/vertx-generator...

奋斗的小牛
26分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部