前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
MCP广场
返回腾讯云官网
社区首页 >专栏 >libuv源码阅读(5.1)--tree.h之伸展树

libuv源码阅读(5.1)--tree.h之伸展树

原创
作者头像
wanyicheng
修改于 2021-03-08 01:54:46
修改于 2021-03-08 01:54:46
46300
代码可运行
举报
文章被收录于专栏：纸上得来终觉浅纸上得来终觉浅
运行总次数：0
代码可运行
关联问题
换一批

伸展树：

可以参考我另外个博客，当时学习C的时候写的：

点这里 https://juejin.cn/post/6892567524118888462

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
// 根节点类型声明
#define SPLAY_HEAD(name, type)                                                \
struct name {                                                                 \
  struct type *sph_root; /* root of the tree */                               \
}

// 初始化 root 节点
#define SPLAY_INITIALIZER(root)                                               \
  { NULL }

// 初始化 root 节点
#define SPLAY_INIT(root) do {                                                 \
  (root)->sph_root = NULL;                                                    \
} while (/*CONSTCOND*/ 0)

// 每个伸展树节点都有左右2个子节点
#define SPLAY_ENTRY(type)                                                     \
struct {                                                                      \
  struct type *spe_left;          /* left element */                          \
  struct type *spe_right;         /* right element */                         \
}

// 取得对应的指针
#define SPLAY_LEFT(elm, field)    (elm)->field.spe_left
#define SPLAY_RIGHT(elm, field)   (elm)->field.spe_right
#define SPLAY_ROOT(head)          (head)->sph_root
#define SPLAY_EMPTY(head)         (SPLAY_ROOT(head) == NULL)

// 朝着右边旋转 也就是目前从 根节点往下的 3个节点为 / 这种一字型排列方式 
/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                             \
  SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);              \
  SPLAY_RIGHT(tmp, field) = (head)->sph_root;                                 \
  (head)->sph_root = tmp;                                                     \
} while (/*CONSTCOND*/ 0)

// 上面情况的对称情况 \ 这种排列
#define SPLAY_ROTATE_LEFT(head, tmp, field) do {                              \
  SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);              \
  SPLAY_LEFT(tmp, field) = (head)->sph_root;                                  \
  (head)->sph_root = tmp;                                                     \
} while (/*CONSTCOND*/ 0)

// 把新发现的 比目前元素大的节点 接入 right 节点的左节点下面 然后同时 移动根节点 和 right节点
#define SPLAY_LINKLEFT(head, tmp, field) do {                                 \
  SPLAY_LEFT(tmp, field) = (head)->sph_root;                                  \
  tmp = (head)->sph_root;                                                     \
  (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);                     \
} while (/*CONSTCOND*/ 0)

// 把新发现的 比目前元素小的节点 接入 left 节点的右节点下面 然后同时 移动根节点 和 left节点
#define SPLAY_LINKRIGHT(head, tmp, field) do {                                \
  SPLAY_RIGHT(tmp, field) = (head)->sph_root;                                 \
  tmp = (head)->sph_root;                                                     \
  (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);                    \
} while (/*CONSTCOND*/ 0)

// 找到最终节点后 交换 root 的左右节点 和 left指针的右节点 right指针的左节点
#define SPLAY_ASSEMBLE(head, node, left, right, field) do {                   \
  SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);             \
  SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);            \
  SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);             \
  SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);             \
} while (/*CONSTCOND*/ 0)

/* Generates prototypes and inline functions */

#define SPLAY_PROTOTYPE(name, type, field, cmp)                               \
void name##_SPLAY(struct name *, struct type *);                              \
void name##_SPLAY_MINMAX(struct name *, int);                                 \
struct type *name##_SPLAY_INSERT(struct name *, struct type *);               \
struct type *name##_SPLAY_REMOVE(struct name *, struct type *);               \

// 寻找目标元素 做一次伸展操作 把目标元素或者最接近目标元素的节点上升到根节点                                                                                                                                                            \/* Finds the node with the same key as elm */                                 \
static __inline struct type *                                                 \
name##_SPLAY_FIND(struct name *head, struct type *elm)                        \
{                                                                             \
  if (SPLAY_EMPTY(head))                                                      \
    return(NULL);                                                             \
  name##_SPLAY(head, elm);                                                    \
  if ((cmp)(elm, (head)->sph_root) == 0)                                      \
    return (head->sph_root);                                                  \
  return (NULL);                                                              \
}                                                                             \

// 寻找树中下一个比元素大的节点 做一次伸展 然后沿着新节点的右子树的左子树一直往下                                                                                                                                                                                                                                         \
static __inline struct type *                                                 \
name##_SPLAY_NEXT(struct name *head, struct type *elm)                        \
{                                                                             \
  name##_SPLAY(head, elm);                                                    \
  if (SPLAY_RIGHT(elm, field) != NULL) {                                      \
    elm = SPLAY_RIGHT(elm, field);                                            \
    while (SPLAY_LEFT(elm, field) != NULL) {                                  \
      elm = SPLAY_LEFT(elm, field);                                           \
    }                                                                         \
  } else                                                                      \
    elm = NULL;                                                               \
  return (elm);                                                               \
}                                                                             \
                                                                              \
static __inline struct type *                                                 \
name##_SPLAY_MIN_MAX(struct name *head, int val)                              \
{                                                                             \
  name##_SPLAY_MINMAX(head, val);                                             \
  return (SPLAY_ROOT(head));                                                  \
}
// 寻找最大或者最小值

/* Main splay operation.
 * Moves node close to the key of elm to top
 */
#define SPLAY_GENERATE(name, type, field, cmp)                                \
struct type *                                                                 \
name##_SPLAY_INSERT(struct name *head, struct type *elm)                      \
{                                                                             \
    if (SPLAY_EMPTY(head)) {                                                  \
      SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;                \
    } else {                                                                  \
      int __comp;                                                             \
      name##_SPLAY(head, elm);                                                \
      __comp = (cmp)(elm, (head)->sph_root);                                  \
      if(__comp < 0) {                                                        \
        SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);         \
        SPLAY_RIGHT(elm, field) = (head)->sph_root;                           \
        SPLAY_LEFT((head)->sph_root, field) = NULL;                           \
      } else if (__comp > 0) {                                                \
        SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);       \
        SPLAY_LEFT(elm, field) = (head)->sph_root;                            \
        SPLAY_RIGHT((head)->sph_root, field) = NULL;                          \
      } else                                                                  \
        return ((head)->sph_root);                                            \
    }                                                                         \
    (head)->sph_root = (elm);                                                 \
    return (NULL);                                                            \
}                                                                             \
// 插入元素 非空情况下  做一次伸展 然后根据目标元素和根节点的比较 决定如何插入

// 删除元素 伸展一次后 根据是否左右子树都存在 如果都存在 则 把原根节点的左子树取出来 做一次伸展 把最接近原节点值的元素作为新节点                                                                                                                                                                                                                                                                                                                        \
struct type *                                                                 \
name##_SPLAY_REMOVE(struct name *head, struct type *elm)                      \
{                                                                             \
  struct type *__tmp;                                                         \
  if (SPLAY_EMPTY(head))                                                      \
    return (NULL);                                                            \
  name##_SPLAY(head, elm);                                                    \
  if ((cmp)(elm, (head)->sph_root) == 0) {                                    \
    if (SPLAY_LEFT((head)->sph_root, field) == NULL) {                        \
      (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);                \
    } else {                                                                  \
      __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
      (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);                 \
      name##_SPLAY(head, elm);                                                \
      SPLAY_RIGHT((head)->sph_root, field) = __tmp;                           \
    }                                                                         \
    return (elm);                                                             \
  }                                                                           \
  return (NULL);                                                              \
}                                                                             \
                                                                              \
void                                                                          \
name##_SPLAY(struct name *head, struct type *elm)                             \
{                                                                             \
  struct type __node, *__left, *__right, *__tmp;                              \
  int __comp;                                                                 \
                                                                              \
  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;            \
  __left = __right = &__node;                                                 \
                                                                              \
  while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {                      \
    if (__comp < 0) {                                                         \
      __tmp = SPLAY_LEFT((head)->sph_root, field);                            \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if ((cmp)(elm, __tmp) < 0){                                             \
        SPLAY_ROTATE_RIGHT(head, __tmp, field);                               \
        if (SPLAY_LEFT((head)->sph_root, field) == NULL)                      \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKLEFT(head, __right, field);                                   \
    } else if (__comp > 0) {                                                  \
      __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if ((cmp)(elm, __tmp) > 0){                                             \
        SPLAY_ROTATE_LEFT(head, __tmp, field);                                \
        if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                     \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKRIGHT(head, __left, field);                                   \
    }                                                                         \
  }                                                                           \
  SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                      \
}                                                                             \
                                                                              \
/* Splay with either the minimum or the maximum element                       \
 * Used to find minimum or maximum element in tree.                           \
 */                                                                           \
void name##_SPLAY_MINMAX(struct name *head, int __comp)                       \
{                                                                             \
  struct type __node, *__left, *__right, *__tmp;                              \
                                                                              \
  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;            \
  __left = __right = &__node;                                                 \
                                                                              \
  while (1) {                                                                 \
    if (__comp < 0) {                                                         \
      __tmp = SPLAY_LEFT((head)->sph_root, field);                            \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if (__comp < 0){                                                        \
        SPLAY_ROTATE_RIGHT(head, __tmp, field);                               \
        if (SPLAY_LEFT((head)->sph_root, field) == NULL)                      \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKLEFT(head, __right, field);                                   \
    } else if (__comp > 0) {                                                  \
      __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if (__comp > 0) {                                                       \
        SPLAY_ROTATE_LEFT(head, __tmp, field);                                \
        if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                     \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKRIGHT(head, __left, field);                                   \
    }                                                                         \
  }                                                                           \
  SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                      \
}

// 根据 参数找 极值 正数就往右侧不断找 负数就是往左侧不断寻找

#define SPLAY_NEGINF  -1
#define SPLAY_INF     1

#define SPLAY_INSERT(name, x, y)  name##_SPLAY_INSERT(x, y)
#define SPLAY_REMOVE(name, x, y)  name##_SPLAY_REMOVE(x, y)
#define SPLAY_FIND(name, x, y)    name##_SPLAY_FIND(x, y)
#define SPLAY_NEXT(name, x, y)    name##_SPLAY_NEXT(x, y)
#define SPLAY_MIN(name, x)        (SPLAY_EMPTY(x) ? NULL                      \
                                  : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
#define SPLAY_MAX(name, x)        (SPLAY_EMPTY(x) ? NULL                      \
                                  : name##_SPLAY_MIN_MAX(x, SPLAY_INF))

#define SPLAY_FOREACH(x, name, head)                                          \
  for ((x) = SPLAY_MIN(name, head);                                           \
       (x) != NULL;                                                           \
       (x) = SPLAY_NEXT(name, head, x))

最主要的方法就是这个伸展函数：

先仔细说明下面几个变量的意思：

在遍历过程中，head->sph_root 始终指向目前正在处理的根节点；__left 左侧最大树，它的右节点不断延伸接入新发现的节点，这棵树的所有节点都比当前根节点小；__right 右侧最小树，它的左节点不断延伸接入新发现的节点，这棵树所有的节点都比根节点大； __node作为临时根节点，它的右节点指针指向 __left 指针第一次被赋值的时候的节点 也就是 左侧最大树的根节点 ，它的左节点指针指向 右侧最小树.

最后一行就是调用前面的方法，交互 4个指针 得到最终的伸展树。它符合二叉树的大小顺序，同时根节点就是目标节点 或者 最接近的目标节点。

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void                                                                          \
name##_SPLAY(struct name *head, struct type *elm)                             \
{                                                                             \
  struct type __node, *__left, *__right, *__tmp;                              \
  int __comp;                                                                 \
                                                                              \
  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;            \
  __left = __right = &__node;                                                 \
                                                                              \
  while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {                      \
    if (__comp < 0) {                                                         \
      __tmp = SPLAY_LEFT((head)->sph_root, field);                            \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if ((cmp)(elm, __tmp) < 0){                                             \
        SPLAY_ROTATE_RIGHT(head, __tmp, field);                               \
        if (SPLAY_LEFT((head)->sph_root, field) == NULL)                      \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKLEFT(head, __right, field);                                   \
    } else if (__comp > 0) {                                                  \
      __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if ((cmp)(elm, __tmp) > 0){                                             \
        SPLAY_ROTATE_LEFT(head, __tmp, field);                                \
        if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                     \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKRIGHT(head, __left, field);                                   \
    }                                                                         \
  }                                                                           \
  SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                      \
}

总结：虽然伸展树在 libuv 没有用到，但是可以复习一下 伸展树的实现，splay那个伸展函数还是很微妙的。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

linux

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

linux
评论
登录后参与评论
暂无评论
登录 后参与评论
推荐阅读
编辑精选文章
换一批
万字详解高可用架构设计
2183
Go 开发者必备：Protocol Buffers 入门指南
1246
10分钟带你彻底搞懂分布式链路跟踪
786
多租户的 4 种常用方案
1615
亿级月活的社交 APP，陌陌如何做到 3 分钟定位故障？
1181
60页PPT全解：DeepSeek系列论文技术要点整理
2158
libuv源码阅读(5.2)--tree.h之红黑树
linux
总结: 红黑树是libuv中用来管理信号handler的，实现的独立性比较高，可以用于自己以后项目参考。
wanyicheng
2021/03/10
6120
Java数据结构与算法解析(八)——伸展树
insertkeytree
伸展树(Splay Tree)是特殊的二叉查找树。 它的特殊是指，它除了本身是棵二叉查找树之外，它还具备一个特点: 当某个节点被访问时，伸展树会通过旋转使该节点成为树根。这样做的好处是，下次要访问该节点时，能够迅速的访问到该节点。
老马的编程之旅
2022/06/22
3870
Java数据结构与算法解析(八)——伸展树
伸展树
数据结构
没看懂，多看几遍吧 1 简介： 伸展树，或者叫自适应查找树，是一种用于保存有序集合的简单高效的数据结构。伸展树实质上是一个二叉查找树。允许查找，插入，删除，删除最小，删除最大，分割，合并等许多操作，这些操作的时间复杂度为O(logN)。由于伸展树可以适应需求序列，因此他们的性能在实际应用中更优秀。 伸展树支持所有的二叉树操作。伸展树不保证最坏情况下的时间复杂度为O(logN)。伸展树的时间复杂度边界是均摊的。尽管一个单独的操作可能很耗时，但对于一个任意的操作序列，时间复杂度可以保证为O(logN)。 2 自
用户1154259
2018/01/17
1.3K0
伸展树
纸上谈兵: 伸展树 (splay tree)
数据库数据结构
我们讨论过，树的搜索效率与树的深度有关。二叉搜索树的深度可能为n，这种情况下，每次搜索的复杂度为n的量级。AVL树通过动态平衡树的深度，单次搜索的复杂度为log(n) (以上参考纸上谈兵 AVL树)。我们下面看伸展树(splay tree)，它对于m次连续搜索操作有很好的效率。 伸展树会在一次搜索后，对树进行一些特殊的操作。这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度。但伸展树并没有AVL的平衡要求，任意节点的左右子树可以相差任意深度。与二叉搜索树类似，伸展树的单次搜索也
Vamei
2018/01/18
7350
纸上谈兵: 伸展树 (splay tree)
面试官问我：什么是 “伸展树” ？
https网络安全编程算法二叉树
为了维持二叉查找树的高效率查找，就需要对二叉查找树进行平衡调整。在数据结构当中大名鼎鼎的红黑树、AVL，就是典型的自平衡二叉查找树。
小灰
2021/06/08
1.1K0
数据结构（7）-- Splay tree(伸展树)
tree
现在我们来介绍一种相对与AVL树更简单的数据结构，它叫伸展树，它保证从空树开始连续任意M次操作最多花费O(MlogN)时间。虽然这种保证并不排除任一次操作花费的时间为O(N)，但是我们关注的是最终的结果。
看、未来
2021/09/18
9620
伸展树(splay tree)
二叉树
对于二叉查找树而言，每次操作的最坏时间复杂度是O(N)。（当树退化为链表的时候）。为了解决这个问题，我们给树附加了一个平衡条件。平衡条件限制了任何节点的深度都不能过深。其中一种限制条件是：一颗二叉查找树的左子树和右子树的高度差不能超过1，这个条件限制产生了AVL树。
zy010101
2019/05/25
1.2K0
手植这棵自顶向下伸展树，何时亭亭如盖呢？
伸展树，解释起来真的很晕。先看一下我写的关于伸展树的理论部分吧：伸展树，据说比AVL树要简单一些。简单个球啊，写完了我还是晕晕的，所以又看了很久。
看、未来
2020/08/25
3760
手植这棵自顶向下伸展树，何时亭亭如盖呢？
讲透学烂二叉树(五)：分支平衡—AVL树与红黑树伸展树自平衡
二叉树
二叉树的最大优点的就是查找效率高，在二叉排序树中查找一个结点的平均时间复杂度是O(log₂N)；
周陆军
2021/08/16
6800
Splay模版:P3369[模版/普通平衡树]
insertparentrootsize
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在 O(logn)内完成插入、查找和删除操作. 它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan在1985年发明的.
用户7267083
2022/12/08
3140
Splay模版:P3369[模版/普通平衡树]
平衡树初阶——AVL平衡二叉查找树+三大平衡树（Treap + Splay + SBT）模板【超详解】
二叉树数据结构
平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图，由根节点指向子结点。但是不严格的说，我们也研究无向树。所谓无向树就是将有向树的所有边看成无向边形成的树状图。树是一种递归的数据结构，所以我们研究树也是按照递归的方式去研究的。 2.什么是二叉树。 我们给出二叉树的递归定义如下： （1）空树是一个二叉树。 （2）单个节点是一个二叉树。 （3）如果一棵树中，以它的左右子节点为根形成的子树都是二叉树，那么这棵树本身也是二叉树。 二
Angel_Kitty
2018/04/09
2.6K0
平衡树初阶——AVL平衡二叉查找树+三大平衡树（Treap + Splay + SBT）模板【超详解】
P3391 【模板】文艺平衡树（Splay）
数据结构编程算法
题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 输入输出格式 输入格式： 第一行为n,m n表示初始序列有n个数，这个序列依次是  m表示翻转操作次数 接下来m行每行两个数 [l,r][l,r] 数据保证  输出格式： 输出一行n个数字，表示原始序列经过m次变换后的结果 输入输出样例 输入样例#1
attack
2018/04/12
7610
libuv源码阅读(3)--heap-inl.h
容器
总结：最小时间堆是libuv用来管理 定时器容器的，每个定时器容器以超时时间排序，插入到堆中，每次事件循环中查看是否有超时的定时任务。
wanyicheng
2021/03/06
4310
libuv源码阅读(3)--heap-inl.h
CPython源码阅读笔记(1)
其他
目前 CPython 的开发已经迁移到了 Github 上，可以直接去 Github clone 对应的分支。 我们将基于 Python 2.7.13 版本， Linux x86_64 环境进行接下来的工作。 下载好代码以后以
鱼塘小咸鱼
2018/11/06
4.6K0
libuv源码阅读(2)--queue.h
linux
这是一种双向队列的实现，假设现在有2个strcut BASE 和 A 要通过双向队列组织起来，BASE作为队列头结点的持有者，A作为队列元素插入：
wanyicheng
2021/03/06
4700
libuv源码阅读(2)--queue.h
#106. 二逼平衡树（附带详细代码注释）
数据结构二叉树编程算法
内存限制：512 MiB时间限制：4000 ms标准输入输出 题目类型：传统评测方式：文本比较 上传者： 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道模板题。 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 查询 x xx 在区间内的排名； 查询区间内排名为 k kk 的值； 修改某一位置上的数值； 查询 x xx 在区间内的前趋（前趋定义为小于 x xx，且最大的数）； 查询 x xx 在区间内的后继（后继定义为大于 x xx，且最小的数）。 输入格式 第一行
attack
2018/04/12
9600
LCT学习笔记
编程算法
最近自学了一下LCT(Link-Cut-Tree)，参考了Saramanda及Yang_Zhe等众多大神的论文博客，对LCT有了一个初步的认识，LCT是一种动态树，可以处理动态问题的算法。对于树分治中的树链剖分，只能处理静态的数据或者在轻重链上的边或点的权值，对于其他动态的处理就毫无办法了。因此我们就需要引入LCT这个东西。那么问题来了，LCT到底是什么呢？我弄了很久总算是理解了LCT，打算总结一下LCT的基本操作。 ①浅谈对LCT的初步印象 LCT用来维护动态的森林，以及一些链上操作，是处理节点无序的有根
Angel_Kitty
2018/04/09
1.2K0
LCT学习笔记
红黑树
null
历史上AVL树流行的另一变种是红黑树(red black tree)。对于红黑树的操作在最坏情形下花费O(log N)时间，而且我们将看到，(对于插入操作的)一种慎重的非递归实现可以相对容易地完成(与AVL树相比)。
狼啸风云
2019/10/28
7900
红黑树
Link Cut Tree入门
access
LCT 是 link cut tree 的简称，顾名思义~ 就是树带动态的增删边的操作.
ACM算法日常
2020/04/22
1.4K0
Link Cut Tree入门
技术总结|tailq详解
遍历变量队列内核调试
（1）定义：TAILQ_ENTRY(type) 初始化一个type类型的entry
用户1904552
2023/04/17
1.2K0
技术总结|tailq详解
推荐阅读
编辑精选文章
万字详解高可用架构设计Go 开发者必备：Protocol Buffers 入门指南10分钟带你彻底搞懂分布式链路跟踪
相关讨论
大佬，求求源码？源码怎么上传？有源码吗？
相关课程
JavaAI代码助手快速上手训练营大数据
libuv源码阅读(5.2)--tree.h之红黑树
6120
Java数据结构与算法解析(八)——伸展树
3870
伸展树
1.3K0
纸上谈兵: 伸展树 (splay tree)
7350
面试官问我：什么是 “伸展树” ？
1.1K0
数据结构（7）-- Splay tree(伸展树)
9620
伸展树(splay tree)
1.2K0
手植这棵自顶向下伸展树，何时亭亭如盖呢？
3760
讲透学烂二叉树(五)：分支平衡—AVL树与红黑树伸展树自平衡
6800
Splay模版:P3369[模版/普通平衡树]
3140
平衡树初阶——AVL平衡二叉查找树+三大平衡树（Treap + Splay + SBT）模板【超详解】
2.6K0
P3391 【模板】文艺平衡树（Splay）
7610
libuv源码阅读(3)--heap-inl.h
4310
CPython源码阅读笔记(1)
4.6K0
libuv源码阅读(2)--queue.h
4700
#106. 二逼平衡树（附带详细代码注释）
9600
LCT学习笔记
1.2K0
红黑树
7900
Link Cut Tree入门
1.4K0
技术总结|tailq详解
1.2K0
相关推荐
libuv源码阅读(5.2)--tree.h之红黑树
更多 >
wanyicheng0
LV.1
这个人很懒，什么都没有留下～
文章
38
获赞
46
专栏
1
作者相关精选
换一批
加入讨论
的问答专区 >
码事漫谈0
1高级后端开发工程师擅长3个领域
相关课程
一站式学习中心 >
Java
1920人在学
java
AI代码助手快速上手训练营
1853人在学
腾讯云代码助手
大数据
533人在学
大数据
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论
1
本文部分代码块支持一键运行，欢迎体验
本文部分代码块支持一键运行，欢迎体验