the smallest key in subtree rooted at x; null if no such key
976778
private RedBlackTreeNode<Key, Value> min(RedBlackTreeNode<Key, Value> x) {
	// assert x != null;
	if (x.getLeft() == null)
	    return x;
	else
	    return min(x.getLeft());
    }
957874
def _get_node_pos(self, key):
        
        if not self._hashring:
            return None

        key = self._gen_key(key)

        nodes = self._sorted_keys
        pos = bisect(nodes, key)

        if pos == len(nodes):
            return 0
        return pos
1187196
public boolean has(String key){
		LazyNode child=root.child;
		while(child!=null){
			if(keyMatch(key,child)){
				return true;
			}
			child=child.next;
		}
		return false;
	}
945062
def _findroot(self, x):
        """"""
        if x.startswith("."):
            x = x[1:]
        if not x.endswith("."):
            x += "."
        max = 0
        root = "."
        root_key = ""
        for k in six.iterkeys(self):
            if x.startswith(k + "."):
                if max < len(k):
                    max = len(k)
                    root = self[k]
                    root_key = k
        return root, root_key, x[max:-1]
341228
function minValueNode(root) {
  var current = root;
  while (current.left) {
    current = current.left;
  }
  return current;
}
101170
private PatriciaNode<V> findNearestNode(String key) {
        PatriciaNode<V> current = root.getLeft();
        PatriciaNode<V> parent = root;

        while (parent.getBit() < current.getBit()) {
            parent = current;
            if (!keyMapper.isSet(current.getBit(), key)) {
                current = current.getLeft();
            } else {
                current = current.getRight();
            }
        }
        return current;
    }
1017416
final TreeMapEntry<K,V> getHigherEntry(K key) {
        TreeMapEntry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else {
                if (p.right != null) {
                    p = p.right;
                } else {
                    TreeMapEntry<K,V> parent = p.parent;
                    TreeMapEntry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }
        }
        return null;
    }
95471
def kth_smallest(self, root, k):
        
        count = []
        self.helper(root, count)
        return count[k-1]
929410
def return_small_clade(treenode):
    ""
    node = treenode
    while 1:
        if node.children:
            c1, c2 = node.children
            node = sorted([c1, c2], key=lambda x: len(x.get_leaves()))[0]
        else:
            return node
1368828
public Tree<K, V> lookup(Tree<K, V> tree, K x) {
        if (tree == null)
            return null;

        int cmp = ordering.compare(x, tree.getKey(kf));

        if (cmp < 0) return lookup(tree.getLeft(), x);
        else if (cmp > 0) return lookup(tree.getRight(), x);
        else return tree;
    }
261613
def nearest_keys(self, key):
        """"""
        if not isinstance(key, tuple):
            _key = (key,)
        if self.__stale:
            self.generate_tree()
        d, idx = self.__tree.query(
            _key, self.k_neighbors, distance_upper_bound=self.distance_upper_bound)

        try:
            return [self.__keys[id][0] for id in idx if id < len(self.__keys)]
        except TypeError:
            # if k_neighbors = 1 query is not returnng arrays
            return self.__keys[idx]
744479
static int getLeafKeyEnd(Object[] node)
    {
        int len = node.length;
        if (len == 0)
            return 0;
        else if (node[len - 1] == null)
            return len - 1;
        else
            return len;
    }
784797
public Tree getNextSibling() {
		if (parent != null && key != null) {
			if (key instanceof Integer) {
				int idx = (int) key;
				if (parent.size() >= idx - 1) {
					return null;
				}
				return parent.get(idx + 1);
			}
			boolean found = false;
			for (Tree child : parent) {
				if (key.equals(child.key)) {
					found = true;
					continue;
				}
				if (found) {
					return child;
				}
			}
		}
		return null;
	}
970510
private static final int binarySearchForRootPrimaryNode(
            int[] rootPrimaryIndexes, int length, long[] nodes, long p) {
        if(length == 0) { return ~0; }
        int start = 0;
        int limit = length;
        for (;;) {
            int i = (int)(((long)start + (long)limit) / 2);
            long node = nodes[rootPrimaryIndexes[i]];
            long nodePrimary = node >>> 32;  // weight32FromNode(node)
            if (p == nodePrimary) {
                return i;
            } else if (p < nodePrimary) {
                if (i == start) {
                    return ~start;  // insert s before i
                }
                limit = i;
            } else {
                if (i == start) {
                    return ~(start + 1);  // insert s after i
                }
                start = i;
            }
        }
    }
844710
private void getLastChild() {

        // nodekey of the root of the current subtree
        final long parent = getNode().getDataKey();

        // traverse tree in pre order to the leftmost leaf of the subtree and
        // push
        // all nodes to the stack
        if (((ITreeStructData)getNode()).hasFirstChild()) {
            while (((ITreeStructData)getNode()).hasFirstChild()) {
                mStack.push(getNode().getDataKey());
                moveTo(((ITreeStructData)getNode()).getFirstChildKey());
            }

            // traverse all the siblings of the leftmost leave and all their
            // descendants and push all of them to the stack
            while (((ITreeStructData)getNode()).hasRightSibling()) {
                mStack.push(getNode().getDataKey());
                moveTo(((ITreeStructData)getNode()).getRightSiblingKey());
                getLastChild();
            }

            // step up the path till the root of the current subtree and process
            // all
            // right siblings and their descendants on each step
            if (getNode().hasParent() && (getNode().getParentKey() != parent)) {

                mStack.push(getNode().getDataKey());
                while (getNode().hasParent() && (getNode().getParentKey() != parent)) {

                    moveTo(getNode().getParentKey());

                    // traverse all the siblings of the leftmost leave and all
                    // their
                    // descendants and push all of them to the stack
                    while (((ITreeStructData)getNode()).hasRightSibling()) {

                        moveTo(((ITreeStructData)getNode()).getRightSiblingKey());
                        getLastChild();
                        mStack.push(getNode().getDataKey());
                    }
                }

                // set transaction to the node in the subtree that is last in
                // document
                // order
                moveTo(mStack.pop());
            }
        }
    }
1134117
private V getForNullKey() {
	for (Entry<K, V> e = table[0]; e != null; e = e.next) {
	    if (e.key == null) return e.value;
	}
	return null;
    }
359692
def smallest(self):
        '''
        
        '''
        if len(self) == 0:
            raise IndexError, "smallest of empty priorityDictionary"
        heap = self.__heap
        while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:
            lastItem = heap.pop()
            insertionPoint = 0
            while 1:
                smallChild = 2*insertionPoint+1
                if smallChild+1 < len(heap) and heap[smallChild] > heap[smallChild+1] :
                    smallChild += 1
                if smallChild >= len(heap) or lastItem <= heap[smallChild]:
                    heap[insertionPoint] = lastItem
                    break
                heap[insertionPoint] = heap[smallChild]
                insertionPoint = smallChild
        return heap[0][1]