二叉树的概念和性质/向上调整、向下调整算法/堆的插入和删除/堆排序/Top-K问题【上】【数据结构/二叉树/初阶/C语言实现】

简介: 二叉树的概念和性质/向上调整、向下调整算法/堆的插入和删除/堆排序/Top-K问题【上】【数据结构/二叉树/初阶/C语言实现】

1. 树

二叉树是树的一种,学习二叉树之前需要学习树.

1.1 树的概念

树是一种递归定义非线性数据结构.之所以被称之为树,是因为其特殊结构.

  • 树的根结点只有它本身,无前驱结点(就是它作为第一个)
  • 其余结点分为若干个大于零的集合,这些集合叫做子树.
  • 每个子树只有一个前驱,可以有若干个(包括0)个后继.
  • "树"的结构是相同的.

例如在上图中

  • 根结点:A
  • B的前驱:A
  • B的后继:E和F
  • 以A为起点,可以分为3个子树.

注意:

  • 子树不能相交,即树不能成环.则到达任意一个叶结点只有一条路径
  • 递归:任何一棵树都能被分为根结点和子树

1.2 树的相关概念

结点的度 一个结点含有的子树个数
叶结点 度为0的结点
父结点 若一个结点含有子结点,则这个结点是该子结点的父结点
子结点 一个结点的子树的根结点为该结点的子结点
树的深度 树中结点最大层次
结点的祖先 从跟到该结点所经分支上所有结点
子孙 以某结点为根的子树中任意一个结点
分支结点 度不为0的结点
兄弟结点 具有相同父结点的结点
树的度 最大的结点的度
结点的层次 根为第一层,根的子结点为第二层…
堂兄弟结点 父结点在同一层结点
森林 由若干互不相交的树组成的集合

显然,人们将树这种数据结构和人类的族谱类比,并提出了许多相对容易理解的概念,这是学习树的前提.

1.3 树的表示

树是一种非线性数据结构,我们很容易想到用链表和动态开辟的数组来表示和存储树.

实际上,能表示树的方法有很多,这里说明最优结构:孩子兄弟表示法.

何为(左)孩子(右)兄弟表示法?

每个结点都有两个指针,分别称为左孩子和右兄弟.

对于一个结点而言:

左孩子指针始终指向该结点的左孩子.

右兄弟指针始终指向该结点的另一个孩子,也就是右孩子,即左孩子的兄弟.

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子节点
struct Node* _pNextBrother; // 指向其下一个兄弟节点
DataType _data; // 节点中的数据
};

2. 二叉树

2.1 概念

二叉树(Binary tree)是每个结点最多只有两个分支(即不存在度大于2的结点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

–维基百科

因而二叉树只有一下几种情况:

2.2 特殊二叉树

满二叉树

每一层的结点数都达到最大值的二叉树,即为满二叉树.若二叉树的层数为k,结点总数为等于2k-1,则它就是满二叉树

性质

  • 共有2k-1个结点(以1为首项,公比为2的等比数列的前k项和)
  • 结点个数一定为奇数
  • 第i层有2i-1个结点
  • 有2k-1个叶子
  • 具有n个结点的满二叉树的深度为log2n+1

完全二叉树

在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干结点,则此二叉树为完全二叉树.

性质

  • 结点的范围在2k-1~2k-1之间
  • 具有n个结点的完全二叉树的深度为log2n+1

通过图示可以知道,满二叉树是一种特殊的完全二叉树.深度为k的完全二叉树其前k-1层为满二叉树,第k层是连续的叶结点(连续即结点按从左到右的顺序排列)

2.3 二叉树的性质(小结)

  • 任何一颗二叉树,度为0的叶结点个数永远比度为2的结点的个数大1.即n0 = n2+1.
  • 非空二叉树第i层上最多有2i-1个结点
  • 深度为h的二叉树最多有2h-1个结点
  • 对于具有n个结点的完全二叉树,按从上至下从左到右的顺序,依次对数组下标编号,有以下规律(i是下标):
  • i=0,根结点
  • i>0:该结点的父节结点的下标是(i-1)/2
  • 2i+1<n:该结点的左孩子结点的下标是i2+1
  • 2i+2<n:该结点的右孩子结点的下标是i2+2

请注意以上规律成立的前提,即所有的数组下标不能越界.

只有完全二叉树才有以上父子结点下标之间的关系

父结点的下标[(i-1)/2]对左孩子和右孩子都成立,使用下标是用int来限制其范围的,相当于对(i-1)/2向下取整.

2.4 二叉树的存储

二叉树的存储可以使用数组和链表(二叉链表或三叉链表),但数组的使用是有局限性的.

人们之所以使用二叉树,是因为它是一个具有良好特性(父子结点的下标有关系)的数据结构,所以将数据以二叉树的形式处理会更高效,操作这些数据的方法也就是通过父子结点下标的关系.

所以利用下标关系的前提是将数据在数组中的下标对应完全二叉树的性质.

用数组存储满二叉树(特殊的完全二叉树)不存在空间浪费,而对于一般二叉树,则需要将其所有结点的度补满,用"空"实现满二叉树然后再存入数组,但这样做会造成空间上的浪费.

所以对于一般二叉树,一般用链式存储.

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}

3. 二叉树的顺序存储

3.1 结构

上文提到,只有完全二叉树使用顺序存储效率最高,所以本小节提到的所有二叉树都是完全二叉树.

3.2 堆

堆是一种用数组存储的数据结构,请区分内存的"堆区".

堆的结构是完全二叉树.

堆分为大堆和小堆,它们的性质相反.

(小)堆的性质

  • 堆的每个结点的值总是大于它的父结点的值,小于它的所有子结点的值.即:所有的父结点的值都小于孩子结点的值.
  • 从上面这句话可以推出,小堆的堆顶元素(下标为0)一定是所有元素中值最小的.

大堆的性质相反.

注意:堆中的元素并不一定是有序的,只要满足第一个性质则为小/大堆

堆的特点能让我们快速找到这个集合中的最值

对堆的理解

在物理结构上,堆是用数组存储的

在逻辑结构上,堆是用完全二叉树存储的

物理结构 != 逻辑结构

堆存在的意义

从使用者的角度:堆使一个集合的所有数据按某种规则(父子下标关系)排列,通过这种规则,人们可以快速处理数据.其使用场景有:

  1. 堆排序

其时间复杂度为O(N*logN)

  1. Top-k问题

以上问题下文都会讲解.

3.3 实现堆

请再次注意:堆是一种用数组存储的数据结构.所以我们只需要使用数组,让数据以堆的特性存储即可.

下面皆以小堆为例.

–这非常重要

如何让物理结构中的数据排列成逻辑结构中的堆?

换句话说,如何按堆的规则通过数组的下标操作数据,使得每个父结点的值都小于其孩子结点的值?

3.3.1 向下调整算法(AdjustDown)

首先需要知道向下调整算法的前提:

从向下调整开始的结点开始,其两个子树必须都是(大/小)堆.

请思考为什么(下面有答案)

核心思想
  1. 选出左右孩子中值最小的
  2. 让它和父结点比较,如果孩子结点的值更小,则交换它们的位置.
  3. 以此类推,直到不满足第二个条件或遇到叶结点为止.

注意:所有的下标都不能越界

请注意

向下调整必须满足该结点的两个子树都是(大/小)堆.

因为堆的堆顶元素必须是整个集合的最值,所以父结点和孩子结点比较,必须让孩子结点也是它这个集合中的最值,这样才能实现"堆顶是集合的最值"这个效果.

本节的目的是实现堆,也就是所有数据都未被处理,哪来的"子树都是堆"这一前提呢?如何使用向下调整算法呢?

  1. 从数组最后一个元素开始,将它看作堆,对其向下调整.每次调整完毕后,再把要调整的对象往前移动一位.
  2. 以此类推,直到调整到根结点为止.
void AdjustDown(HeapDataType* a, int size, int parent)
{
  //默认左孩子最小
  int child = parent * 2 + 1;
  //终止条件:child下标越界时
  while (child < size)
  {
    //若右孩子比左孩子更小,则更新child
    if (a[child + 1] < a[child])
    {
      child++;
    }
    //如果孩子比父亲更小,则交换
    //记得限制右孩子的下标
    if (child + 1 < size && a[child] < a[parent])
    { //每次交换后都要迭代(只有交换后才迭代)
      //想想为什么?
      //迭代注意顺序
      Swap(&(a[child]), &(a[parent]));
      parent = child;
      child = parent * 2 + 1;
    }
    else//注意这个巧妙的break
    {
      break;
    }
  }
}

注意:

  • 比较左孩子和右孩子,可以不用分别使用两个变量leftchild和rightchild,先默认左孩子是最小的,下标+1也就是右孩子,这样比较更高效.这种思想在查找最大的数这个问题中有体现,是广被接受的思想.
  • while的终止条件是孩子结点child下标越界时,所以括号内要填入循环继续的条件.
  • 在比较左右孩子的if语句中要限制右孩子的下标,因为右孩子的下标是孩子和父亲三个结点中下标最大的那个.
  • 迭代孩子和父亲结点的顺序.往哪边走,就先改相反的那边.比如这里是向下调整,那就先改上面的结点,也就是父亲结点.
  • 因为向下调整的前提是两个子树都是堆,如果不符合交换位置的条件,就说明这个两个堆就算不调整也能整合成一个堆,直接break.
小小结

向下调整的主要作用就是让建堆,让两个集合(这两个集合都是堆)整合成一个堆.

3.3.2 向上调整算法(AdjustUp)

向上调整算法的核心思想和向下调整算法类似.

它在堆上插入元素使用,通过下面的文字,图示和代码理解其作用.

核心思想
  1. 将孩子结点和父结点的值比较.
  2. 若孩子结点的值小于父结点的值,交换.
  3. 以此类推,直至根结点.

void AdjustUp(HeapDataType* a, int child)
{
  int parent = (child - 1) / 2;
  while (parent >= 0)
  {
    //向上调整需要比较左右孩子吗?
    if (a[child] < a[parent])
    {
      Swap(&(a[child]), &(a[parent]));
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

注意:

  • 注意点同向下调整
  • 不同的地方是向上调整不需要判断左右孩子结点的大小.因为传入的参数是具体的两个孩子中的一个.
  • while循环的终止条件是父亲结点parent下标越界,但是也可以用child>0代替.思考为什么?
小小结

向上调整的对象是一棵二叉树,作用是调整插入后的堆的结构,使其符合堆的结构.

3.3.3 小结

  1. 向上调整和向下调整都是在已知的父子结点下标关系前提下进行的,这是父子结点迭代的唯一条件.
  2. 向上调整主要用在堆的插入元素操作中.
  3. 向下调整主要用在建堆操作和删除堆顶元素操作中.
  4. 在哪里改变,就往相反的方向调整.

代码技巧

  1. else的使用
  2. 大于小于号的对应.建大堆都使用大于号,建小堆都使用小于号,这样修改的时候更加方便.
  3. 交换功能独立封装成一个接口.

3.3.4 堆的插入(HeapPush)

堆的插入并不是像顺序表链表一样,可以在任意位置插入元素.元素只能在堆尾被插入,也就是最后一个元素.

如果不加以处理,插入的元素的值的大小可能会影响它的祖先,有可能会使整棵树的父子关系打乱,使得它不符合堆的结构.

所以在插入元素以后,需要对其处理,怎么处理呢?

上面的小结总结到:在哪里改变,就往相反的方向调整.

补充:实际上,"尾上插入"是物理结构上的改变,而对应逻辑结构的改变是堆的结构被改变了.

既然是从尾插,那就从尾开始调整,也就只能向上调整.这是"模板化"的理解.从堆本身的特点理解:就是要让这个新元素放到它应该放的位置,使得这个堆能保持它的特性:每个父结点的值都小于其孩子结点的值.

void HeapPush(HP* php, HeapDataType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc failed\n");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  //尾插要在if外面
  php->a[php->size] = x;
  php->size++;
  //向上调整
  AdjustUp(php->a, php->size - 1);
}

注意:

  • 除了最后一行以外,都是常规的顺序表Push接口的操作
  • 插入元素是插到数组的尾上,所以对其向上调整

3.3.5 堆的删除(HeapPop)

堆的删除并不是删除某一个元素,这对"堆"这种数据结构而言是没有意义的.

回到前文,堆存在的意义不是这种数据结构本身,而是堆有良好的特性,能够快速找到一个集合中的最值,也就是取堆顶数据.

所以删除堆顶的元素对堆而言才是有意义的,因为我们取出了整个集合的最值.

那么,直接删除堆顶的元素可行吗?

显然,删除了堆顶的数据就破坏了堆的结构(必须要有根结点,且值最小),挪动覆盖也不可行,这会让父子关系混乱,因为父子关系是由下标确定的.

思路:

将数组首尾元素交换,size--即删除.但此时结构也被改变了,堆顶的元素已经不再是最小值了.

但此思想巧妙的是,恰好根结点的两个子结点形成的子树都是堆,而改变的恰好是堆顶(上文提到哪里改变就往相反方向调整),所以恰好能使用向下调整算法.

这样便能恢复堆的结构,让新的集合的最值放在堆顶.

void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  //交换堆首尾元素的位置
  Swap(&(php->a[0]), &(php->a[php->size - 1]));
  //删除堆尾的元素
  php->size--;
  //从堆顶开始向下调整
  AdjustDown(php->a, php->size, 0);
}

注意:

  • "删除"某个位置的元素,只需要让它不在数组下标的范围即可,这里就是size--,让要删除的元素放到原数组的尾端,新数组的长度变短.
  • 注意判空,数组下标越界.
  • 将原来堆顶元素置于末尾,新堆顶元素的两个子树都是堆,满足向下调整的前提.

3.3.6 堆的实现「剩余代码」

在上面已经给出了AdjustDown,AdjustUp,HeapPopHeapPush接口,下面给出剩下的接口(仅供参考).

实际上,上面四个接口是最重要的,其他接口和顺序表别无二致.

void Swap(HeapDataType* e1, HeapDataType* e2)
{
  HeapDataType tmp = *e1;
  *e1 = *e2;
  *e2 = tmp;
}
HeapDataType HeapTop(HP* php)
{
  assert(php);
  return php->a[0];
}
void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = 0;
  php->size = 0;
}
void HeapDestory(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = 0;
  php->size = 0;
}
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
void HeapPrint(HP* php)
{
  assert(php);
  for (int i = 0; i < php->size; ++i)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}

注意:

  • 初始化函数HeapInit的赋值符号不要写成双等于号,否则会让realloc函数报错.

3.3.7 建堆的时间复杂度

不是因为我懒,而是大佬写的太好了^ ^

堆排序中建堆过程时间复杂度O(n)怎么来的?

3.4 堆的应用

3.4.1 堆排序(HeapSort)

首先以一个例子引入.

打印排序:

  1. 依次取堆顶元素,打印
  2. 删除该元素,重新调整,更新堆顶元素

这并不是真正的排序,只是打印的效果上是排序.

这样会造成"思维定式":打印升序对应建小堆,因为每次打印都是打该集合中最小的值.打印降序反之.

首先就对打印这件事来说,它依赖堆这个数据结构的实现,难道每次给数据排序都要写一个堆吗?而且它的空间复杂度是O(N),也会有内存泄漏的风险.就这代码量和空间复杂度,不如用其他排序方法.打印本质上就没有利用堆这个数据结构良好的特性.

真正的排序并非如此.首先给出结论:

  • 升序建大堆
  • 降序建小堆

下面以小堆为例.

如何不通过堆,而将数组中的数据以堆的形式排列呢?

改进:

  1. 自下而上地使用向下调整来建堆
  2. "删除"堆顶元素,使这个最值沉到原数组尾部

其中重要的思想是将数组看作完全二叉树,也就是堆(实际上在之前就是这么做的).

最最重要的步骤就是建堆和删除操作

自上而下地建堆在本小节末尾会与自下而上建堆作比较.

建堆

从倒数第一个非叶结点开始,对其进行向下调整操作.每调整一次,结点往前走一步,直到遇到根结点.

这里一上来就提到了"叶结点",说明我们在这个时候把这个数组看作堆.

实际上,从最后一个结点开始调整也是可以的,不过有一些结点的下标太大,无法进入向下调整中的while循环.

倒数第一个非叶结点就是能进入向下调整while循环的最大下标.

排序

将堆顶和堆尾的元素交换,每交换一次向下调整,然后用size--的操作缩小数组长度,"删除"此次这个集合中的最值.

代码
void HeapSort(int* a, int n)
{
    //建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  {
    AdjustDown(a, n, i);
  }
    //删除堆顶元素
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);//交换堆顶和堆尾元素
    AdjustDown(a, end, 0);//每交换一次都要向下调整
    --end;//缩小数组长度,让最值沉到末尾
  }
}
void TestHeapSort()
{
  int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
  HeapSort(a, sizeof(a) / sizeof(int));
}

为什么不自上而下

向下调整的时间复杂度是O(N)

向上调整的时间复杂度是O(logN)

自下而上的时间复杂度是O(N*logN)

自上而下的时间复杂度是O(N)

3.4.2 Top-K问题

Top-K问题实际上就是在一个集合中找前K个最值.

下面以前k个最大元素为例.

找到一个集合(有N个元素)中的前k个最值,可以有三种方法:

1. 排序

堆排序的时间复杂度是O(N+NlogN).
当N足够大,可以认为时间复杂度是O(N
logN).

2. 建N个数的小堆

依次取出堆顶元素,取k次.

时间复杂度是O(N+logN*K).

前者是建堆的时间复杂度,后者是向下调整K次的时间复杂度.

*3. 建k个元素的小堆

前面两种办法在N非常大的时候效率都不高,不论是时间还是空间上.

思路:

  1. 用数组的前k个数建立小堆
  2. 剩下的N-k个数依次和堆顶元素的值比较,如果比堆顶的更大,则交换
  3. 当遍历完数组所有元素,这个堆就是这个集合中前k个最大的元素

为什么是小堆?

如果是大堆,只能选出一个最大的元素,那这样最坏的情况用上面的方法再遍历N次才能选出前k个最大的数.这不就是用遍历实现吗?

如果是小堆,就不会出现最大的数卡在堆顶的情况.

时间复杂度O(k+(N-K)*logK).

如何实现:

  1. 从最后一个非叶子结点开始,从后往前插入前k个数.

这么做的目的是:先用一些数据建立一个枝干,为要找的数据准备位置.

  1. 遍历剩下的元素,与堆顶比较,若比堆顶大,则替换它,每交换一次必须向下调整.

只要通过画图理解了上面的步骤,就会知道最终这个堆是前k个最大值以降序方式排列的.

void PrintTopK(int* a, int n, int k)
{
  int* kMinHeap = (int*)malloc(sizeof(int)*k);
  assert(kMinHeap);
    //先用kMinHeap数组接收所有元素
  for (int i = 0; i < k; i++)
  {
    kMinHeap[i] = a[i];
  }
    // 1. 用前k个元素建堆
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDwon(kMinHeap, k, i);
  }
  // 2. 将剩余n-k个元素依次与堆顶元素交换,不满足则替换
  for (int j = k; j < n; j++)
  {
    if (a[j] > kMinHeap[0])
    {
      kMinHeap[0] = a[j];
            //每次替换都要向下调整
      AdjustDwon(kMinHeap, k, 0);
    }
  }
    //打印
  for (int i = 0; i < k; i++)
  {
    printf("%d ", kMinHeap[i]);
  }
  printf("\n");
}
void TestTopk()
{
  int n = 10000;
  int* a = (int*)malloc(sizeof(int)*n);
  srand(time(0));
  for (int i = 0; i < n; ++i)
  {
    a[i] = rand() % 1000000;
  }
  a[5] = 1000000 + 1;
  a[42] = 1000000 + 2;
  a[51] = 1000000 + 3;
  a[541] = 1000000 + 4;
  a[120] = 1000000 + 5;
  a[67] = 1000000 + 6;
  a[90] = 1000000 + 7;
  a[76] = 1000000 + 8;
  a[45] = 1000000 + 9;
  a[5554] = 1000000 + 10;
  PrintTopK(a, n, 10);
}

注意:

  • 建堆的下标是从k-1开始的.(k-1)/2则是倒数第一个非叶子结点
  • 每次破坏了堆的结构,都要向下调整以恢复.

注:本文部分图片来源于学习课件.

目录
相关文章
|
26天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
29天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
49 5
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
107 8
|
2月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
73 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
32 0
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
26 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
74 0
数据结构与算法学习十八:堆排序
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
28 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
30 0