1. They don't intersect - we omit the subtree rooted in this node. \r\n

2. They intersect but (a) is not nested in (b) - we continue searching in the subtree rooted in this node.\r\n

3. Interval (a) is nested in interval (b) - we found node which represents part of the interval we search for, therefore we don't continue searching in the subtree. intervalin = Interval ⟨#4,#5⟩ represented by node #3 is nested in interval ⟨#1,#2⟩. intervalinsert = After adding a new element we have to adjust the values of all nodes on the path from this leaf node to the root node accordingly. intervalkeyempty = Since the right node is empty, we choose key of the left node #1. intervalmax = We choose larger key of #2 and #1. intervalmin = We choose smaller key of #1 and #2. intervalout = Interval ⟨#4,#5⟩ represented by node #3 and interval ⟨#1,#2⟩ don't intersect. intervalpart = Interval ⟨#4,#5⟩ represented by node #3 is not nested in interval ⟨#1,#2⟩, but they intersect. intervalsum = We take the sum of left and right sons keys #2 + #1. intervaltree = Interval tree intervaltrees = Interval trees keys = Keys language = Language layout = Layout layout-compact = Compact layout-simple = Simple lazybinheap = Lazy binomial heap leftheap = Leftist heap leftinsertright = Since #1 > #2, we insert it in the right subtree. leftinsertup = Since #1 ≤ #2, #2 becomes the right son of #1. leftmeldnoson = Since #2 has no right son, we append the rest of the heap as the right son of #2. leftmeldrightg = Since #1 > #2, nothing happens and we continue along the right path. leftmeldrightl = Since #1 < #2, nothing happens and we continue along the right path. leftmeldstart = We start by comparing the roots as the first elements in the right path. leftmeldswapg = Since #1 ≥ #2, we swap the heaps and continue along the right path. leftmeldswapl = Since #1 ≤ #2, we swap the heaps and continue along the right path. leftrankstart = We make the heap leftist by swapping left and right children according to their ranks. If the rank of the right son is greater than the rank of the left son, we exchange them, otherwise nothing happens. leftrankupdate = We update the node ranks. lipsum = English lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut commodo, neque id accumsan imperdiet, metus felis pharetra est, nec molestie diam elit a lectus. Maecenas erat purus, tempor nec aliquam id, tincidunt vel dui. Cras fermentum suscipit porta. Aenean vel magna vestibulum augue hendrerit tincidunt et nec magna. Aliquam at metus et quam vehicula iaculis. Curabitur sapien est, ultrices id auctor vel, ullamcorper at ipsum. Mauris sodales adipiscing dignissim. max = max maxdheapbubbledown = We bubble the node down (swap it with the greatest child) until it is greater than all of its children. maxheap = Max Heap maxheapbubbledown = We bubble the node down (swap it with its greater child) until it is greater than both of its children. maxheapbubbleup = We bubble the node up (swap it with its parent) until its parent has greater priority. maximum = Maximum is #1. meld = Meld heaps ###1 and ###2 meldable-pq = Meldable priority queues min = min mindheapbubbledown = We bubble the node down (swap it with the smallest child) until it is smaller than all of its children. minheap = Min Heap minheapbubbledown = We bubble the node down (swap it with its smaller child) until it is smaller than both of its children. minheapbubbleup = We bubble the node up (swap it with its parent) until its parent has smaller priority. minimum = Minimum is #1. mode23 = 2-3 tree correspondence mode234 = 2-3-4 tree correspondence newroot = The tree is empty so we make a new root. next = Next nodes = Nodes notfound = Not found. opt = opt pairdecr = After decreasing the key, the heap property could be invalidated, so we cut the vertex and re-link it to the heap. pairincr = After increasing the key, the heap property could be invalidated, so we cut the vertex and re-link it to the heap. pairing = Pairing pairingbf = back-front pairingfb = front-back pairingheap = Pairing heap pairinglazymulti = lazy multipass pairinglrrl = left-to-right then right-to-left pairingmultipass = multipass pairingnaive = naive pairlinkmax = Since #1 < #2, we link #1 to #2. pairlinkmin = Since #1 < #2, we link #2 to #1. pairlrrl1 = If we choose "left-to-right then right-to-left" pairing, first we pair trees left to right. (We link the first and second, then the third and fourth and so on.) pairlrrl2 = Then we link each remaining tree to the last one working from the right to left. pairnaive = If "naive" combining rule is chosen, we choose one of the trees and successively link each of the remaing ones with it. pq = Priority queues previous = Previous rbdelete1 = Case I: Node's sibling is red: We recolor some nodes and transform it to Case II, III, or IV. rbdelete2 = Case II: Node's sibling and both his children are black: the extra black is moved up the tree. rbdelete3 = Case III: Node's sibling is black, the closer child is red, the next one is black: We transform it to Case IV. rbdelete4 = Case IV: Node's sibling and his child closer to us is black, the other one is red: By some recoloring and one rotation we can remove the extra black. rbinsertcase1 = Case I, red uncle: We color the father and uncle black, the grandfather red and continue from grandfather. rbinsertcase2 = Case II, black uncle, "inner" vertex: We transform this to Case III. rbinsertcase3 = Case III, black uncle "outer" vertex: We perform a rotation and recolor the nodes. redblack = Red-black tree rotate = Rotate #1. rotate-change = Nodes #1 and #2 exchange their roles: #1 becomes a new son of #2... rotate-change-b = ...and #1 becomes son of #2. rotate-change-nullb = ...and #1's son [null] becomes son of #2. rotate-change-parent = ...#1 becomes parent of #2... rotate-changes = Nodes #1 and #3 exchange their roles: #1 becomes a new son of #4 and #3 becomes a son of #1. Node #2 exchanges its parent #1 for #3. rotate-fall = This subtree descends. rotate-header = Rotate #1 rotate-newroot = ...#1 becomes the new root... rotate-preserves-order = Note that rotation preserves the order of nodes. rotate-rise = This subtree rises. rotate-root = Node #1 is root – we can't rotate it. rotations = Rotations scapegoat = Scapegoat tree search = Search show-order = Show order show-subtrees = Show subtrees size = Size skewheap = Skew heap skewheapswap = We swap the left and right children of every node on the right path except the lowest one. skipdelete = Now we delete the node from each level. skipfindstart = We start searching at the top left corner. skipinsertafter = We insert the new node right after this one. skipinsertnext = Next key is less than our key. We insert it right. skipinsertstart = We start at the top left corner and find appropriate place to insert the new node. skiplist = Skiplist skiplist-delete-found = We have found the node to delete. skiplist-down = Next key is > #1 so we go down. skiplist-head = Toss ##1: HEADS. We promote the node. skiplist-next = The next key is ≤ #1, so we go right. skiplist-tail = Toss ##1: TAILS. We stop. skiplist-tossing = Now we will toss a coin until it comes TAILS. For each HEAD, we promote the node up, so on average there will be 1/2^k nodes on the k-th level. splay = Splay splay-found = Found. We splay this node. splay-higher = Key #1 is not in the tree. We splay #2, the smallest higher key in the tree, instead. splay-insert-left = Note that the root and its left subtree is less than #1 while the whole root's right subtree is greater than #1. splay-insert-left2 = We simply make #1 the new root, link the current root left and it's right subtree right. splay-insert-right = Note that the root and its right subtree is greater than #1 while the whole root's left subtree is less than #1. splay-insert-right2 = We simply make #1 the new root, link the current root right and it's left subtree left. splay-lower = Key #1 is not in the tree. We splay #2, the biggest lower key in the tree, instead. splay-root = There is no grandparent; we just rotate. splay-start = We start by splaying #1. This will bring #1 to the root. If #1 is not in the tree the smallest higher or the biggest lower key is splayed. splay-zig-zag-left = Zig-zag case (#1 is a left son, but #2 is a right son): we rotate #1 twice. splay-zig-zag-right = Zig-zag case (#1 is a right son, but #2 is a left son): we rotate #1 twice. splay-zig-zig-left = Zig-zig case (both #1 and #2 are left sons of their fathers): we first rotate #2 and then #1. splay-zig-zig-right = Zig-zig case (both #1 and #2 are right sons of their fathers): we first rotate #2 and then #1. splaydelete = We delete the root, splay the right subtree for minimum. splaydeleteleft = The root has no right subtree; we just delete it and make the left child the new root. splaydeletelink = The minimum of the right tree will be the new root; since minimum has no left son, we can just link the left tree. splaydeleteright = The root has no left subtree; we just delete it and make the right child the new root. splayinroot = Now our key, smallest bigger or biggest smaller is in the root. splaytree = Splay tree stringology = Stringology suffixtree = Suffix Tree suffixtree-found = Each leaf in this subtree corresponds to a suffix beginning with "#1" and stores its position. We have found #2 occurence(s). sum = sum sumimum = Sum of the interval is #1. sxbaftersecondrule = We continue appending. sxbcontinue = We start extending vertices on working path by the letter '#1'. sxbdownwalk = We find the place to append the letter '#1'. sxbdownwalkedge = We continue searching. sxbexplicit = We transform the tree to explicit form. sxbfind = We find the string '#1'. sxbfirstrule = We extend all vertices from first rule with the letter '#1'. sxbphase = We step into #1. phase. sxbsecondrule = We divide the edge and append a letter '#1'. sxbslink = We use suffix link. sxbstart = We start inserting the word. sxbthirdrule = Third rule is applied here. We are finished with this phase. sxbupwalk = We go to the nearest node upward. text = Text treap = Treap treapbubbledown = We bubble the node down. treapbubbleup = We bubble the node up until its parent has greater priority. treapdeletecase1 = Now the node is a leaf and we can simply delete it. trie = Trie triea = Stringology triedelete = Delete "#1" triedeletedbdb = We delete a letter. triedeletedbend = The dead branch is deleted. triedeletefindunsu = We simply cannot delete a word which is not in the tree. triedeletenote1 = First, we have to find the given word. triedeletenote2 = Now, we delete an "end of a word" mark and then we delete a "dead branch", that is all nodes hanging, not determined by end of a word. triedeletewodb = Now, it's about time to delete the dead branch. triefind = Find "#1" triefindending1 = A letter '#1' is not appended to this node. So, the tree does not contain the given word! triefindending2 = We read the whole given word, but in the tree no word ends here. So, the tree does not contain the given word! triefindmovedown = We move down to a letter '#1'. triefindnote = We traverse the tree through edges with letters from a given word. When whole word is read and we are in a node marked by end-of-word symbol, the tree contains the given word. triefindsucc = We read the whole given word and there is also a "end of a word" mark here. So, the tree contains the given word! triei = Trie trieinsert = Insert "#1" trieinserteow = We have inserted the whole word. Now, it's time to mark an end of the word. trieinsertneow = The word is in the tree. trieinsertnote = We divide a given word into single letters which then append in sequental order. If a letter is already appended we don't append it but simple move down to it. trieinsertwch = We move down to a letter '#1'. trieinsertwoch = Append a letter '#1'. trierootstart = We start in the root. uf-byrank = by rank uf-compresion = path compression uf-find-heuristic = Find: uf-find-start = Start searching for the representative. uf-found-root = This is the representative of the set containing #1. uf-go-old-parent = Move to the former parent. uf-go-up = Move toward root. uf-halving = path halving uf-link = Link #1 directly under #2. uf-none = na\u00EFve uf-path-halved = Note that the path from #1 to the root halved. uf-path-split = Note how the path from #1 to the root split. uf-same-set = Elements are in the same set, no linking needed. uf-splitting = path splitting uf-union-heuristic = Union: ufa = Union Find ufcompression = Let's compress the marked path. ufdown = We are going down. ufdownstart = We go back and link all elements to the representative. uffind = Find a representative ufi = Union Find ufunion = Union ufunionfirstsecond = This node has higher rank, so we link #2 under #1. ufunionsamerank = Both representatives have the same rank. So we choose to link #2 under #1 and increment #1's rank. ufunionsecondfirst = This node has higher rank, so we link #1 under #2. ufunionsimple = Link second representative to first one.\u0009 ufupspecial = We link grandchild. zoomio = Zoom in/out