Modify the tree if its right subtree is too small compared to the left
Return the new root if any
340746
function rightTooSmall(node) {
		if (balanceFactor(node) <= 1) { return node; }   // Right is not too small, don't change
		if (balanceFactor(node.left) < 0) {leftRotation(node.left);}
		return rightRotation(node);
	}
801181
private void adjustTree(IndexTreePath<E> subtree) {
    final Logging log = getLogger();
    if(log.isDebugging()) {
      log.debugFine("Adjust tree " + subtree + "\n");
    }

    // get the root of the subtree
    int nodeIndex = subtree.getIndex();
    N node = getNode(subtree.getEntry());

    // overflow in node; split the node
    if(hasOverflow(node)) {
      // do the split
      Assignments<E> assignments = settings.splitStrategy.split(this, node);
      final N newNode = node.isLeaf() ? createNewLeafNode() : createNewDirectoryNode();

      List<E> entries1 = new ArrayList<>(assignments.getFirstAssignments().size());
      List<E> entries2 = new ArrayList<>(assignments.getSecondAssignments().size());
      // Store final parent distances:
      for(DistanceEntry<E> ent : assignments.getFirstAssignments()) {
        final E e = ent.getEntry();
        e.setParentDistance(ent.getDistance());
        entries1.add(e);
      }
      for(DistanceEntry<E> ent : assignments.getSecondAssignments()) {
        final E e = ent.getEntry();
        e.setParentDistance(ent.getDistance());
        entries2.add(e);
      }
      node.splitTo(newNode, entries1, entries2);

      // write changes to file
      writeNode(node);
      writeNode(newNode);

      if(log.isDebuggingFine()) {
        log.debugFine(new StringBuilder(1000)//
            .append("Split Node ").append(node.getPageID()).append(" (").append(this.getClass()).append(')').append(FormatUtil.NEWLINE)//
            .append("      newNode ").append(newNode.getPageID()).append(FormatUtil.NEWLINE)//
            .append("      firstPromoted ").append(assignments.getFirstRoutingObject()).append(FormatUtil.NEWLINE)//
            .append("      firstAssignments(").append(node.getPageID()).append(") ").append(assignments.getFirstAssignments()).append(FormatUtil.NEWLINE)//
            .append("      firstCR ").append(assignments.computeFirstCover(node.isLeaf())).append(FormatUtil.NEWLINE)//
            .append("      secondPromoted ").append(assignments.getSecondRoutingObject()).append(FormatUtil.NEWLINE)//
            .append("      secondAssignments(").append(newNode.getPageID()).append(") ").append(assignments.getSecondAssignments()).append(FormatUtil.NEWLINE)//
            .append("      secondCR ").append(assignments.computeSecondCover(node.isLeaf())).append(FormatUtil.NEWLINE));
      }

      // if root was split: create a new root that points the two split nodes
      if(isRoot(node)) {
        // FIXME: stimmen die parentDistance der Kinder in node & splitNode?
        IndexTreePath<E> newRootPath = createNewRoot(node, newNode, assignments.getFirstRoutingObject(), assignments.getSecondRoutingObject());
        adjustTree(newRootPath);
      }
      // node is not root
      else {
        // get the parent and add the new split node
        E parentEntry = subtree.getParentPath().getEntry();
        N parent = getNode(parentEntry);
        if(log.isDebugging()) {
          log.debugFine("parent " + parent);
        }
        double parentDistance2 = distance(parentEntry.getRoutingObjectID(), assignments.getSecondRoutingObject());
        // logger.warning("parent: "+parent.toString()+" split: " +
        // splitNode.toString()+ " dist:"+parentDistance2);
        parent.addDirectoryEntry(createNewDirectoryEntry(newNode, assignments.getSecondRoutingObject(), parentDistance2));

        // adjust the entry representing the (old) node, that has been split
        double parentDistance1 = distance(parentEntry.getRoutingObjectID(), assignments.getFirstRoutingObject());
        // logger.warning("parent: "+parent.toString()+" node: " +
        // node.toString()+ " dist:"+parentDistance1);
        node.adjustEntry(parent.getEntry(nodeIndex), assignments.getFirstRoutingObject(), parentDistance1, this);

        // write changes in parent to file
        writeNode(parent);
        adjustTree(subtree.getParentPath());
      }
    }
    // no overflow, only adjust parameters of the entry representing the node
    else {
      if(!isRoot(node)) {
        E parentEntry = subtree.getParentPath().getEntry();
        N parent = getNode(parentEntry);
        E entry = parent.getEntry(subtree.getIndex());
        boolean changed = node.adjustEntry(entry, entry.getRoutingObjectID(), entry.getParentDistance(), this);
        // write changes in parent to file
        if(changed) {
          writeNode(parent);
          adjustTree(subtree.getParentPath());
        }
      }
      // root level is reached
      else {
        E rootEntry = getRootEntry();
        node.adjustEntry(rootEntry, rootEntry.getRoutingObjectID(), rootEntry.getParentDistance(), this);
      }
    }
  }
1246193
def _get_substructure(self, treelist, pos):
        """"""
        subtree = None
        if len(pos) > 1:
            subtree = self._get_substructure(treelist[pos[0]][1], pos[1:])
        else:
            try:
                subtree = treelist[pos[0]]
            except (IndexError, TypeError):
                pass
        return subtree
153052
def add_adjust(self, data, prehashed=False):
        
        subtrees = self._get_whole_subtrees()
        new_node = Node(data, prehashed=prehashed)
        self.leaves.append(new_node)
        for node in reversed(subtrees):
            new_parent = Node(node.val + new_node.val)
            node.p, new_node.p = new_parent, new_parent
            new_parent.l, new_parent.r = node, new_node
            node.sib, new_node.sib = new_node, node
            node.side, new_node.side = 'L', 'R'
            new_node = new_node.p
        self.root = new_node
225647
public boolean canTraverseOutsideSubtree()
  {

    if (null != m_left && m_left.canTraverseOutsideSubtree())
      return true;

    if (null != m_right && m_right.canTraverseOutsideSubtree())
      return true;

    return false;
  }
211602
def move(self, newX1) :
		""""""
		if self.x1 != None and self.x2 != None :
			offset = newX1-self.x1
			aux_moveTree(offset, self)
		elif len(self.children) > 0 :
			offset = newX1-self.children[0].x1
			aux_moveTree(offset, self)
159373
private MtasRBTreeNode addRange(MtasRBTreeNode n, Integer left, Integer right,
      int additionalId, long additionalRef, Integer id, Long ref) {
    MtasRBTreeNode localN = n;
    if (localN == null) {
      String key = left.toString() + "_" + right.toString();
      localN = new MtasRBTreeNode(left, right, MtasRBTreeNode.RED, 1);
      localN.addIdAndRef(id, ref, additionalId, additionalRef);
      index.put(key, localN);
    } else {
      if (left <= localN.left) {
        localN.leftChild = addRange(localN.leftChild, left, right, additionalId,
            additionalRef, id, ref);
        updateMax(localN, localN.leftChild);
      } else {
        localN.rightChild = addRange(localN.rightChild, left, right,
            additionalId, additionalRef, id, ref);
        updateMax(localN, localN.rightChild);
      }
      if (isRed(localN.rightChild) && !isRed(localN.leftChild)) {
        localN = rotateLeft(localN);
      }
      if (isRed(localN.leftChild) && isRed(localN.leftChild.leftChild)) {
        localN = rotateRight(localN);
      }
      if (isRed(localN.leftChild) && isRed(localN.rightChild)) {
        flipColors(localN);
      }
      localN.n = size(localN.leftChild) + size(localN.rightChild) + 1;
    }
    return localN;
  }
8429
function replace(oldNode, newNode){
    return oldNode[PARENT_NODE] ? oldNode[PARENT_NODE].replaceChild(newNode, oldNode) : oldNode;
  }
50472
def aux_insertTree(childTree, parentTree):
	""""""
	if childTree.x1 != None and childTree.x2 != None :
		parentTree.insert(childTree.x1, childTree.x2, childTree.name, childTree.referedObject)

	for c in childTree.children:
		aux_insertTree(c, parentTree)
992350
def rebuild_tree(cls, session, tree_id):
        
        session.query(cls).filter_by(tree_id=tree_id)\
            .update({cls.left: 0, cls.right: 0, cls.level: 0})
        top = session.query(cls).filter_by(parent_id=None)\
            .filter_by(tree_id=tree_id).one()
        top.left = left = 1
        top.right = right = 2
        top.level = level = cls.get_default_level()

        def recursive(children, left, right, level):
            level = level + 1
            for i, node in enumerate(children):
                same_level_right = children[i - 1].right
                left = left + 1

                if i > 0:
                    left = left + 1
                if same_level_right:
                    left = same_level_right + 1

                right = left + 1
                node.left = left
                node.right = right
                parent = node.parent

                j = 0
                while parent:
                    parent.right = right + 1 + j
                    parent = parent.parent
                    j += 1

                node.level = level
                recursive(node.children, left, right, level)

        recursive(top.children, left, right, level)
651921
def replace_nodes(root, old, new):

    '''
     
    '''

    rep = Replacer(old, new)
    rep.visit(root)
    return
49830
def _prune_some_if_small(self, small_size, a_or_u):
        ""
        # Assert that we're not messing things up.
        prev_app_size = self.app_size()
        prev_use_size = self.use_size()

        keep_nodes = []
        prune_app_size = 0
        prune_use_size = 0
        for node in self._nodes:
            node_size = node.app_size() if a_or_u else node.use_size()
            if node_size < small_size:
                if a_or_u:
                    prune_app_size += node_size
                    prune_use_size += node.use_size()
                else:
                    prune_app_size += node.app_size()
                    prune_use_size += node_size
            else:
                keep_nodes.append(node)

        # Last "leftover" node? Merge with parent.
        if len(keep_nodes) == 1 and keep_nodes[-1]._isdir is None:
            prune_app_size += keep_nodes[-1]._app_size
            prune_use_size += keep_nodes[-1]._use_size
            keep_nodes = []

        if prune_app_size:
            if not keep_nodes:
                # The only node to keep, no "leftovers" here. Move data
                # to the parent.
                keep_nodes = None
                assert self._isdir and self._nodes is not None
                self._set_size(prune_app_size, prune_use_size)
            elif keep_nodes and keep_nodes[-1]._isdir is None:
                # There was already a leftover node. Add the new leftovers.
                keep_nodes[-1]._add_size(prune_app_size, prune_use_size)
            else:
                # Create a new leftover node.
                keep_nodes.append(DuNode.new_leftovers(
                    self._path, prune_app_size, prune_use_size))

        # Update nodes and do the actual assertion.
        self._nodes = keep_nodes
        assert prev_app_size == self.app_size(), (
            prev_app_size, self.app_size())
        assert prev_use_size == self.use_size(), (
            prev_use_size, self.use_size())
416745
@Override
  protected void adjustTree(IndexTreePath<SpatialEntry> subtree) {
    if(getLogger().isDebugging()) {
      getLogger().debugFine("Adjust tree " + subtree);
    }

    // get the root of the subtree
    N node = getNode(subtree.getEntry());

    // overflow in node
    if(hasOverflow(node)) {
      if(node.isSuperNode()) {
        int new_capacity = node.growSuperNode();
        getLogger().finest("Extending supernode to new capacity " + new_capacity);
        if(isRoot(node)) { // is root
          node.adjustEntry(getRootEntry());
        }
        else {
          N parent = getNode(subtree.getParentPath().getEntry());
          SpatialEntry e = parent.getEntry(subtree.getIndex());
          HyperBoundingBox mbr = new HyperBoundingBox(e);
          node.adjustEntry(e);

          if(!SpatialUtil.equals(mbr, e)) { // MBR has changed
            // write changes in parent to file
            writeNode(parent);
            adjustTree(subtree.getParentPath());
          }
        }
      }
      else {
        int[] splitAxis = { -1 };
        // treatment of overflow: reinsertion or split
        N split = overflowTreatment(node, subtree, splitAxis);

        // node was split
        if(split != null) {
          // if the root was split: create a new root containing the two
          // split nodes
          if(isRoot(node)) {
            IndexTreePath<SpatialEntry> newRootPath = createNewRoot(node, split, splitAxis[0]);
            height++;
            adjustTree(newRootPath);
          }
          // node is not root
          else {
            // get the parent and add the new split node
            N parent = getNode(subtree.getParentPath().getEntry());
            if(getLogger().isDebugging()) {
              getLogger().debugFine("parent " + parent);
            }
            SpatialEntry newEntry = createNewDirectoryEntry(split);
            parent.addDirectoryEntry(newEntry);

            // The below variant does not work in the persistent version
            // E oldEntry = subtree.getEntry();
            // [reason: if oldEntry is modified, this must be permanent]
            SpatialEntry oldEntry = parent.getEntry(subtree.getIndex());

            // adjust split history
            SplitHistory sh = ((SplitHistorySpatialEntry) oldEntry).getSplitHistory();
            if(sh == null) {
              // not yet initialized (dimension not known of this tree)
              sh = new SplitHistory(oldEntry.getDimensionality());
              sh.setDim(splitAxis[0]);
              ((SplitHistorySpatialEntry) oldEntry).setSplitHistory(sh);
            }
            else {
              ((SplitHistorySpatialEntry) oldEntry).addSplitDimension(splitAxis[0]);
            }
            try {
              ((SplitHistorySpatialEntry) newEntry).setSplitHistory((SplitHistory) sh.clone());
            }
            catch(CloneNotSupportedException e) {
              throw new RuntimeException("Clone of a split history should not throw an Exception", e);
            }

            // adjust the entry representing the (old) node, that has
            // been split
            node.adjustEntry(oldEntry);

            // write changes in parent to file
            writeNode(parent);
            adjustTree(subtree.getParentPath());
          }
        }
      }
    }
    // no overflow, only adjust parameters of the entry representing the
    // node
    else {
      if(!isRoot(node)) {
        N parent = getNode(subtree.getParentPath().getEntry());
        SpatialEntry e = parent.getEntry(subtree.getIndex());
        HyperBoundingBox mbr = new HyperBoundingBox(e);
        node.adjustEntry(e);

        if(node.isLeaf() || // we already know that mbr is extended
            !SpatialUtil.equals(mbr, e)) { // MBR has changed
          // write changes in parent to file
          writeNode(parent);
          adjustTree(subtree.getParentPath());
        }
      }
      // root level is reached
      else {
        node.adjustEntry(getRootEntry());
      }
    }
  }
980276
def avl_split_first(root):
    
    if root is None:
        raise IndexError('Empty tree has no maximum element')
    root, left, right = avl_release_kids(root)
    if left is None:
        new_root, first_node = right, root
    else:
        new_left, first_node = avl_split_first(left)
        new_root = avl_join(new_left, right, root)
    return (new_root, first_node)
318747
public void renameNodesInTree(String oldName, String newName) {
		List<Node> nodes = getNodesFromTreeByName(oldName);
		Iterator i = nodes.iterator();
		while (i.hasNext()) {
			Node n = (Node) i.next();
			n.setName(newName);
		}
	}
574898
def patch_tree(actions, tree):
    """"""
    patcher = patch.Patcher()
    return patcher.patch(actions, tree)
1106521
private Tree<K, V> del(Tree<K, V> tree, K k) {
        if (tree == null)
            return null;

        int cmp = ordering.compare(k, tree.getKey(kf));
        if (cmp < 0) return delLeft(tree, k);
        else if (cmp > 0) return delRight(tree, k);
        else return append(tree.getLeft(), tree.getRight());
    }