悠哉杂学 - B树
type: channel
link: https://uinit.cn/index.php/tag/B树/
items: 二叉树、B树、红黑树！

二叉树、B树、红黑树！
type: item
date: 2021-06-24T12:44:00+08:00
description: 本文主要讲解下最近一直听到的红黑树，看看究竟是什么神仙鬼怪。二叉树满足以下两个条件的树就是二叉树：本身是有序树（若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(Ordered Tree)）；树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2； 简单地理解，二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉查找树要了解红黑树之前，免不了先看下二叉查找树是什么。维基百科上的定义二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；2.若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值； 3.任意节点的左、右子树也分别为二叉查找树；图示理解下图为查找值为29的节点，有以下步骤：1.查看根节点412.因为41> 29 ,所以查看41的左孩子203.因为20 < 29 ,所以查看20的右孩子29，发现其正好是要查看的节点。退化二叉查找树有个非常严重的问题，如果数据的插入是从大到小插入的，或者是从小到大插入的话，会导致二叉查找树退化成单链表的形式，俗称“瘸子“。1.左瘸子：例如，插入数据依次为{5,4,3,2,1}（从大到小），则如下图所示：2.右瘸子：例如，插入数据依次为{1,2,3,4,5}（从小到大），则如下图所示：为了解决该问题，出现了一些解决方法，即平衡，能够使得树趋向平衡，这种自衡的树叫做平衡树。平衡树平衡树(Balance Tree，BT)指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有AVL树（二叉平衡搜索树），B树（多路平衡搜索树，2-3树，2-3-4树中的一种），红黑树等。AVL树AVL树（由发明者Adelson-Velsky 和 Landis 的首字母缩写命名），是指任意节点的两个子树的高度差不超过1的平衡树。又称自平衡二叉搜索树。AVL树能解决上文二叉查找树中的右瘸子问题，例如，插入数据依次为{1,2,3,4,5}（从小到大），则如下图所示：AVL树会对不符合高度差的结构进行调整，从而使得二叉树趋向平衡。2-3树2-3树，是指每个具有子节点的节点（内部节点，internal node）要么有两个子节点和一个数据元素，要么有三个子节点和两个数据元素的自平衡的树，它的所有叶子节点都具有相同的高度。简单点讲，2-3树的非叶子节点都具有两个分叉或者三个分叉，所以，称作2叉-3叉树更容易理解。另外一种说法，具有两个子节点和一个数据元素的节点又称作2节点，具有三个子节点和两个数据元素的节点又称作3节点，所以，整颗树叫做2-3树。所有叶子点都在树的同一层，一样高。性质1. 满足二叉搜索树的性质 性质2. 节点可以存放一个或两个元素 性质3. 每个节点有两个或三个子节点创建2-3树的规则插入操作1.向2-节点中插入元素2.向一颗只含有一个3-节点的树中插入元素2-3-4树含义 2节点：包含两个子节点和一个数据元素 3节点：包含三个子节点和一个数据元素 4节点：包含四个子节点和一个数据元素2-3-4树，它的每个非叶子节点，要么是2节点，要么是3节点，要么是4节点，且可以自平衡，所以称作2-3-4树。规则规则1. 加入新节点时，不会往空的位置添加节点，而是添加到最后一个叶子节点上规则2. 四节点可以被分解三个2-节点组成的树，并且分解后新树的根节点需要向上和父节点融合插入操作1.原本的2-3-4树2.对于上图的2-3-4树，插入一个节点17，由于规则1，节点17不会加入节点[16,18,20]的子树，而是与该节点融合。3.由于规则2，节点[16,17,18,20]是一个4节点，将该节点进行拆解成新的树，将18作为子树的根节点进行拆分。4.此时树暂时失去了平衡，我们需要将拆分后的子树的根节点向上进行融合。5.同理可得，由于规则2，节点[6,10,14,18]是一个4节点，将该节点进行拆解成新的树，将14作为子树的根节点进行拆分，完成了2-3-4树的构建。总结了下插入节点的过程，无非也就为了符合两条规则，那么，2-3树，2-3-4树都有了，那是不是也有2-3-4-5树，2-3-4-5--...-n树的存在呢？事实上是有的，世人把这一类树称为一个名字：B树。B树B树，表示的是一类树，它允许一个节点可以有多于两个子节点，同时，也是自*衡的，叶子节点的高度都是相同的。所以，为了更好地区分一颗B树到底属于哪一类树，我们给它一个新的属性：度（Deg…