Search

6: Binary Trees
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/06%3A_Binary_Trees
In illustrations, binary trees are usually drawn from the root downward, with the root at the top of the drawing and the left and right children respectively given by left and right positions in the d...In illustrations, binary trees are usually drawn from the root downward, with the root at the top of the drawing and the left and right children respectively given by left and right positions in the drawing (Figure $\PageIndex{1}$ ). Because binary trees are so important, a certain terminology has developed for them: The depth of a node, $\mathtt{u}$ , in a binary tree is the length of the path from $\mathtt{u}$ to the root of the tree.
2: Array-Based Lists
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/02%3A_Array-Based_Lists
Adding or removing an element near the middle of a list means that a large number of elements in the array need to be shifted to make room for the newly added element or to fill in the gap created by ...Adding or removing an element near the middle of a list means that a large number of elements in the array need to be shifted to make room for the newly added element or to fill in the gap created by the deleted element. When the number of elements in the data structure exceeds the size of the backing array, a new array needs to be allocated and the data from the old array needs to be copied into the new array.
11.1: Comparison-Based Sorting
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/11%3A_Sorting_Algorithms/11.01%3A_Comparison-Based_Sorting
Quicksort then recursively sorts the beginning of the array and the end of the array, while the random binary search tree recursively inserts smaller elements in the left subtree of the root and large...Quicksort then recursively sorts the beginning of the array and the end of the array, while the random binary search tree recursively inserts smaller elements in the left subtree of the root and larger elements in the right subtree of the root.
12.4: Discussion and Exercises
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/12%3A_Graphs/12.04%3A_Discussion_and_Exercises
Then the following theorem is a more precise statement of the running times of the breadth-first-search and depth-first-search algorithms. (This more refined statement of the running time is useful in...Then the following theorem is a more precise statement of the running times of the breadth-first-search and depth-first-search algorithms. (This more refined statement of the running time is useful in some of the applications of these algorithms outlined in the exercises.)
11.3: Discussion and Exercises
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/11%3A_Sorting_Algorithms/11.03%3A_Discussion_and_Exercises
Quicksort is an in-place algorithm and is a close second in terms of the number of comparisons, but is randomized, so this running time is not always guaranteed. Show that, for any implementation of \...Quicksort is an in-place algorithm and is a close second in terms of the number of comparisons, but is randomized, so this running time is not always guaranteed. Show that, for any implementation of $\mathtt{quickSort(a,i,n,c)}$ that chooses a pivot deterministically, without first looking at any values in $\mathtt{a[i]},\ldots,\mathtt{a[i+n-1]}$ , there exists an input array of length $\mathtt{n}$ that causes this implementation to perform $\binom{\mathtt{n}}{2}$ comparisons.
Bibliography
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/zz%3A_Back_Matter/02%3A_Bibliography
Applications of the theory of records in the study of random trees. Reischuk, editors, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 199...Applications of the theory of records in the study of random trees. Reischuk, editors, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in Computer Science, pages 567-580. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 483-491, New York, NY, USA, 2001.
13.2: XFastTrie - Searching in Doubly-Logarithmic Time
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/13%3A_Data_Structures_for_Integers/13.02%3A_XFastTrie_-_Searching_in_Doubly-Logarithmic_Time
For an example, refer to Figure $\PageIndex{1}$ ; in this figure the last node, $\mathtt{u}$ , on search path for 14 (whose binary representation is 1110) is the node labelled $11{\star\star}$ at ...For an example, refer to Figure $\PageIndex{1}$ ; in this figure the last node, $\mathtt{u}$ , on search path for 14 (whose binary representation is 1110) is the node labelled $11{\star\star}$ at level 2 because there is no node labelled $111{\star}$ at level 3. Then, the node $\mathtt{u}$ we are searching for would be at or below level $\mathtt{i}$ if and only if there is a node at level $\mathtt{i}$ whose label matches the highest-order $\mathtt{i}$ bits of $\mathtt{x}$ .
8: Scapegoat Trees
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/08%3A_Scapegoat_Trees
void rebuild(Node<T> u) { int ns = size(u); Node<T> p = u.parent; Node<T>[] a = (Node<T>[]) Array.newInstance(Node.class, ns); packIntoArray(u, a, 0); if (p == nil) { r = buildBalanced(a, 0, ns); r.pa...void rebuild(Node<T> u) { int ns = size(u); Node<T> p = u.parent; Node<T>[] a = (Node<T>[]) Array.newInstance(Node.class, ns); packIntoArray(u, a, 0); if (p == nil) { r = buildBalanced(a, 0, ns); r.parent = nil; } else if (p.right == u) { p.right = buildBalanced(a, 0, ns); p.right.parent = p; } else { p.left = buildBalanced(a, 0, ns); p.left.parent = p; } } int packIntoArray(Node<T> u, Node<T>[] a, int i) { if (u == nil) { return i; } i = packIntoArray(u.left, a, i); a[i++] = u; return packInto…
4.3: SkiplistList - An Efficient Random-Access List
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/04%3A_Skiplists/4.03%3A_SkiplistList_-_An_Efficient_Random-Access_List
T remove(int i) { if (i < 0 || i > n-1) throw new IndexOutOfBoundsException(); T x = null; Node u = sentinel; int r = h; int j = -1; // index of node u while (r >= 0) { while (u.next[r] != null && j+u...T remove(int i) { if (i < 0 || i > n-1) throw new IndexOutOfBoundsException(); T x = null; Node u = sentinel; int r = h; int j = -1; // index of node u while (r >= 0) { while (u.next[r] != null && j+u.length[r] < i) { j += u.length[r]; u = u.next[r]; } u.length[r]--; // for the node we are removing if (j + u.length[r] + 1 == i && u.next[r] != null) { x = u.next[r].x; u.length[r] += u.next[r].length[r]; u.next[r] = u.next[r].next[r]; if (u == sentinel && u.next[r] == null) h--; } r--; } n--; ret…
10.1: BinaryHeap - An Implicit Binary Tree
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/10%3A_Heaps/10.01%3A_BinaryHeap_-_An_Implicit_Binary_Tree
In this way, the root is stored at position 0, the root's left child is stored at position 1, the root's right child at position 2, the left child of the left child of the root is stored at position 3...In this way, the root is stored at position 0, the root's left child is stored at position 1, the root's right child at position 2, the left child of the left child of the root is stored at position 3, and so on.
6.1: BinaryTree - A Basic Binary Tree
https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Open_Data_Structures_-_An_Introduction_(Morin)/06%3A_Binary_Trees/6.01%3A_BinaryTree_-_A_Basic_Binary_Tree
int size2() { Node u = r, prev = nil, next; int n = 0; while (u != nil) { if (prev == u.parent) { n++; if (u.left != nil) next = u.left; else if (u.right != nil) next = u.right; else next = u.parent; ...int size2() { Node u = r, prev = nil, next; int n = 0; while (u != nil) { if (prev == u.parent) { n++; if (u.left != nil) next = u.left; else if (u.right != nil) next = u.right; else next = u.parent; } else if (prev == u.left) { if (u.right != nil) next = u.right; else next = u.parent; } else { next = u.parent; } prev = u; u = next; } return n; }

Search

Text Color

Text Size

Margin Size

Font Type

Support Center

How can we help?