tree-rotation

    5热度

    1回答

    证明的最大转数为两棵树成为等于

    在书中算法导论 - 创造性的方法，问题4.24： 设T1和T2是两个任意的树，每个都具有n个节点。证明对T1应用至多2n的旋转是足够的，以便它等于T2。 对于二叉搜索树，我想通了一个算法： 查找等于T2的根元素，让我们把它定位根。 使用AVL旋转策略，旋转target-root使其成为T1的新根。 在此过程中，可能会执行多次旋转。 对于T1和T2的左子树，按照上面的方式递归处理它们。 对于T1和T
    algorithm tree avl-tree tree-rotation 2013-11-24

    2热度

    2回答

    AVL树中的额外情况

    AVL树似乎有四种转换：左 - 左，左 - 右，右 - 左和右 - 右。但是，似乎也可能有其他情况。我提出这个为左均衡： 没有留下也不是，右旋转可以平衡这棵树。用什么算法来平衡它？
    algorithm data-structures avl-tree tree-rotation 2015-12-22

    6热度

    2回答

    是否总是有可能使用树轮旋转将一个BST变成另一个BST？

    给定一组值，可能有许多不同的可能的二叉搜索树，可以从这些值形成。例如，对于值1，2，3，有五个BSTS我们可以从这些值使： 1 1 2 3 3 \ \ /\ / / 2 3 1 3 1 2 \ / \ / 3 2 2 1 许多数据结构是基于平衡二叉搜索树使用tree rotations作为一种原始的在不破坏所需的二分查找树不变式的情况下重塑B
    algorithm data-structures binary-search-tree tree-rotation 2012-12-25

    1热度

    1回答

    在红黑树上旋转

    我试图找出在重新平衡完成时红黑树中的旋转。我明白为什么轮换发生，但我不明白它是如何完成的。此外，像LL，RR，LR和RL这样的中间旋转是如何完成的，直到结果为止，并且如果有人告诉我关于何时执行这些旋转中的任何一个的任何经验法则，我也会感激。这里是旋转： Rr(2) is the case when black node deficiency is in right child of "py" i.
    red-black-tree tree-rotation 2013-10-28

    3热度

    2回答

    使用旋转的二叉树转换

    当我在中期研究二叉树时，发现任何任意的n节点二叉树可以转换成任何其他n节点二叉树，最多2 * n-2个旋转。有没有证据呢？我发现了一些有渐近符号的证明，但它并不那么清楚。我的意思是有人可以解释/说明它为什么是真的？如果它说n节点二叉树，它是否包含根？
    algorithm math data-structures binary-tree tree-rotation 2013-10-28

    1热度

    1回答

    最大。将新元素插入n元素红黑树时的旋转次数

    将新元素插入n元素时的最大旋转次数是多少？元素红黑树？ 如果我是正确的，插入不违反RBT requries规则最大2旋转（2例）。假设是这样，O(1)也是一个正确的答案？ 如果是这样，确认它请告诉我，什么需要最多3轮？
    red-black-tree tree-rotation 2014-02-10

    0热度

    1回答

    左旋转失败活得比原始的

    我试图实现一个平衡树，并写了一个函数，其左旋转来代替树： struct BST<'a> { l: Option<&'a BST<'a>>, r: Option<&'a BST<'a>> } impl<'a> BST<'a> { fn left_rotate(self) -> BST<'a> { /* * (x) (y)
    tree rust move-semantics lifetime tree-rotation 2017-01-02

    0热度

    2回答

    AVL Tree Rotation中的指针

    我无法理解为什么下面的树轮代码有效。如果T2指向y.left和y.left指向x，这是不是使最后一个指配x.right = T2等于x.right = x？指针是不是应指向最初的T2？ Node leftRotate(Node x) { Node y = x.right; Node T2 = y.left; // Perform rotation y.le
    java avl-tree tree-rotation 2017-05-31

    0热度

    1回答

    如何从下面的序列创建自下而上的splay树

    这是序列20,10,5,30,40,57,3,2,4,35,25,18,22,27 我已经尝试通过使每个新插入的节点作为根，但它不起作用。 有人可以一步一步给我解释吗？
    data-structures tree-balancing splay-tree tree-rotation 2015-12-26
最新问题