gpt4 book ai didi

data-structures - Rope 数据结构解释?

转载 作者:行者123 更新时间:2023-12-04 07:02:19 30 4
gpt4 key购买 nike

我正在阅读维基百科上的绳索数据结构,但我对描述有些困惑。

维基链接:http://en.wikipedia.org/wiki/Rope_(data_structure)

说明

A rope is a binary tree having leaf nodes that contain a short string.

Each node has a weight value equal to the length of its string plus the sum of all leaf nodes' weight in its left subtree, namely the weight of a node is the total string length in its left subtree for a non-leaf node, or the string length of itself for a leaf node.

Thus a node with two children divides the whole string into two parts: the left subtree stores the first part of the string. The right subtree stores the second part and its weight is the sum of the left child's weight and the length of its contained string.



下图是维基百科的例子之一。

Rope data structure tree
.

我无法查看上图中数字的来源。

Each node has a weight value equal to the length of its string plus the sum of all leaf nodes' weight in its left subtree


  • C = 6 + 0(E + C 的空字符串的长度)?
  • B = 6 + 3 + 0 + 0(E + F + C 的空字符串长度 + B 的空字符串长度)?
  • 那不可能是对的,为什么是 A 22? (6+6+9 = 21?6+6+3+9 = 24?)

  • 我很确定我错过了一些东西。有人可以帮我清理一下吗?

    谢谢。

    最佳答案

    Each node has a weight value equal to the length of its string plus the sum of all leaf nodes' weight in its left subtree...



    A 没有右子树,所以它的值是所有叶节点的权重之和(即使 A 有右子树,它的值也会相同):6+3+2+4+1+6=22

    B 的左子树有两片叶子:6+3=9

    C 在它的左子树中有一片叶子:6

    关于data-structures - Rope 数据结构解释?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28685485/

    30 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com