Cuts this entry from its parent and adds it to the root list, and then
does the same for its parent, and so on up the tree.
Runtime: O(log n)
550855
private void cutAndMakeRoot(Entry entry) {
        Entry oParent = entry.oParent;
        if (oParent == null) return;  // already a root

        oParent.degree--;
        entry.isMarked = false;

        // update parent's `oFirstChild` pointer
        Entry oFirstChild = oParent.oFirstChild;
        assert oFirstChild != null;

        if (oFirstChild.equals(entry)) {
            if (oParent.degree == 0) {
                oParent.oFirstChild = null;
            }
            else {
                oParent.oFirstChild = entry.next;
            }
        }

        entry.oParent = null;
        unlinkFromNeighbors(entry);

        // add to root list
        mergeLists(entry, oMinEntry);
        if (oParent.oParent != null) {
            if (oParent.isMarked) {
                cutAndMakeRoot(oParent);
            }
            else {
                oParent.isMarked = true;
            }
        }
    }
824613
function(stopOnParents) {
		var nodeList = [];
		this.rootNode.visit(function(node){
			if( node.selected ) {
				nodeList.push(node);
				if( stopOnParents === true ){
					return "skip"; // stop processing this branch
				}
			}
		});
		return nodeList;
	}
210894
def list_to_tree(cls, files):
        """"""

        def attach(branch, trunk):
            """Insert a branch of directories on its trunk."""
            parts = branch.split('/', 1)
            if len(parts) == 1:  # branch is a file
                trunk[FILE_MARKER].append(parts[0])
            else:
                node, others = parts
                if node not in trunk:
                    trunk[node] = defaultdict(dict, ((FILE_MARKER, []), ))
                attach(others, trunk[node])

        tree = defaultdict(dict, ((FILE_MARKER, []), ))
        for line in files:
            attach(line, tree)
        return tree
73422
def drop(self):
        
        if self.is_root:
            raise ValueError("Cannot drop root node!")

        parent = self.parent
        for child in self.children:
            child.parent = parent
            parent.children.add(child)
        self.children = set()

        parent.sequence_ids.update(self.sequence_ids)
        self.sequence_ids = set()

        parent.remove_child(self)
1072143
public static <T> T root(TreeDef.Parented<T> treeDef, T node) {
		T lastParent;
		T parent = node;
		do {
			lastParent = parent;
			parent = treeDef.parentOf(lastParent);
		} while (parent != null);
		return lastParent;
	}
1108181
def insert(index, value)
      node = self
      cidx = nil

      # Traverse the tree to find the right node to add or replace the value.
      while node do
        # All nodes that we find on the way that are full will be split into
        # two half-full nodes.
        if node.size >= @tree.node_size
          # Re-add the index from the last parent node since we will descent
          # into one of the split nodes.
          index += node.parent.offsets[cidx] if node.parent
          node = node.split_node
        end

        # Once we have reached a leaf node we can insert or replace the value.
        if node.is_leaf?
          node.values.insert(index, value)
          node.parent.adjust_offsets(node, 1) if node.parent
          return
        else
          # Descend into the right child node to add the value to.
          cidx = node.search_child_index(index)
          if (index -= node.offsets[cidx]) < 0
            node.fatal "Index (#{index}) became negative"
          end
          node = node.children[cidx]
        end
      end

      node.fatal "Could not find proper node to insert the value while " +
        "looking for index #{index}"
    end
334278
def append_ancestor_entry(ancestors, ancestor, class_methods, instance_methods = nil)
      if class_methods || instance_methods
        ancestor_entry = {}
        ancestor_entry[:class] = class_methods if class_methods
        ancestor_entry[:instance] = instance_methods if instance_methods
        ancestors << {ancestor => ancestor_entry}
      end
    end
1360299
def remove_entry(self, fs_entry):
        
        try:
            self._root_elements.remove(fs_entry)
        except ValueError:  # fs_entry may not be in the root elements
            pass
        if fs_entry.parent:
            fs_entry.parent.remove_child(fs_entry)
        # Reset file lists so they get regenerated without the removed file(s)
        self._all_files = None
82297
Entry forceRemove()
  {
    Entry removedEntry = null;

    checkEntryParent();
        
    if(atTop)
    {
      //if we are at the top of the list and we are the first top cursor
      if(parentList.firstTopCursor == this)
      {
        //set the first top cursor to be the next one in the list
        parentList.firstTopCursor = (Cursor) next;                
      }
      //mark us as not at the top
      atTop = false;
    }
    else if(atBottom)
    {
      //if we are at the bottom of the list and we are the first bottom cursor
      if(parentList.firstBottomCursor == this)
      {
        //set the first bottom cursor to be the next one in the list
        parentList.firstBottomCursor = (Cursor) next;                
      }
      //mark us as not at the bottom
      atBottom = false;
    }
    else
    {
      //if we are pointing to an actual entry in the list
      if(current.firstCursor == this)
      {
        //and we are the first cursor on that entry
        //set the first cursor to be the next one in the list
        current.firstCursor = (Cursor) next;
      }
      //set the current entry to null
      current = null;
    }
    //actually remove this cursor from the list
    removedEntry = super.forceRemove();
    
    return removedEntry;
  }
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());
      }
    }
  }
243336
public void addChildren(
        CmsTreeItem parent,
        List<CmsCategoryTreeEntry> children,
        Collection<String> selectedCategories) {

        if (children != null) {
            for (CmsCategoryTreeEntry child : children) {
                // set the category tree item and add to parent tree item
                CmsTreeItem treeItem = buildTreeItem(child, selectedCategories);
                m_childrens.get(parent.getId()).add(treeItem.getId());
                m_childrens.put(treeItem.getId(), new ArrayList<>(child.getChildren().size()));
                if ((selectedCategories != null) && selectedCategories.contains(child.getPath())) {
                    openWithParents(parent);

                }
                if (m_isSingleSelection) {
                    if (treeItem.getCheckBox().isChecked()) {
                        parent.getCheckBox().setChecked(false);
                    }
                }
                parent.addChild(treeItem);
                addChildren(treeItem, child.getChildren(), selectedCategories);
            }
        }
    }
839878
def uproot(tree):
        
        uprooted = tree.copy()
        uprooted.parent = None
        for child in tree.all_children():
            uprooted.add_general_child(child)
        return uprooted
212450
def add_root(cls, **kwargs):
        """"""

        if len(kwargs) == 1 and 'instance' in kwargs:
            # adding the passed (unsaved) instance to the tree
            newobj = kwargs['instance']
            if newobj.pk:
                raise NodeAlreadySaved("Attempted to add a tree node that is "\
                    "already in the database")
        else:
            newobj = cls(**kwargs)

        newobj._cached_depth = 1
        if not cls.node_order_by:
            try:
                max = get_result_class(cls).objects.filter(
                    parent__isnull=True).order_by(
                    'sib_order').reverse()[0].sib_order
            except IndexError:
                max = 0
            newobj.sib_order = max + 1
        newobj.save()
        return newobj
1064664
private void addChildren(CmsTreeItem parent, List<CmsCategoryTreeEntry> children, List<String> selectedCategories) {

        if (children != null) {
            for (CmsCategoryTreeEntry child : children) {
                // set the category tree item and add to parent tree item
                CmsTreeItem treeItem = buildTreeItem(child, selectedCategories);
                if ((selectedCategories != null) && selectedCategories.contains(child.getPath())) {
                    parent.setOpen(true);
                    openParents(parent);
                }
                parent.addChild(treeItem);
                addChildren(treeItem, child.getChildren(), selectedCategories);
            }
        }
    }
640151
private void cutFromParent(Node<K, V> n) {
        if (n.o_s != null) {
            if (n.y_s != null) {
                n.y_s.o_s = n.o_s;
            }
            if (n.o_s.o_c == n) { // I am the oldest :(
                n.o_s.o_c = n.y_s;
            } else { // I have an older sibling!
                n.o_s.y_s = n.y_s;
            }
            n.y_s = null;
            n.o_s = null;
        }
    }
193979
private void deleteEntry(TreeMapEntry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            TreeMapEntry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }
1298529
def add_child(self, tree):
        '''
        '''
        tree.parent = self
        self.children.append(tree)
        return tree