Loading...
Please wait, while we are loading the content...
Similar Documents
16 Scapegoat and Splay Trees 16 . 1 Definitions ÆÆÆ
| Content Provider | Semantic Scholar |
|---|---|
| Copyright Year | 2014 |
| Abstract | I’ll assume that everyone is already familiar with the standard terminology for binary search trees—node, search key, edge, root, internal node, leaf, right child, left child, parent, descendant, sibling, ancestor, subtree, preorder, postorder, inorder, etc.—as well as the standard algorithms for searching for a node, inserting a node, or deleting a node. Otherwise, consult your favorite data structures textbook. For this lecture, we will consider only full binary trees—where every internal node has exactly two children—where only the internal nodes actually store search keys. In practice, we can represent the leaves with null pointers. Recall that the depth of a node is its distance from the root, and its height is the distance to the farthest leaf in its subtree. The height (or depth) of the tree is just the height of the root. The size of a node is the number of nodes in its subtree. The size n of the whole tree is just the total number of nodes. A tree with height h has at most 2h leaves, so the minimum height of an n-leaf binary tree is dlg ne. In the worst case, the time required for a search, insertion, or deletion to the height of the tree, so in general we would like keep the height as close to lg n as possible. The best we can possibly do is to have a perfectly balanced tree, in which each subtree has as close to half the leaves as possible, and both subtrees are perfectly balanced. The height of a perfectly balanced tree is dlg ne, so the worst-case search time is O(log n). However, even if we started with a perfectly balanced tree, a malicious sequence of insertions and/or deletions could make the tree arbitrarily unbalanced, driving the search time up to Θ(n). To avoid this problem, we need to periodically modify the tree to maintain ‘balance’. There are several methods for doing this, and depending on the method we use, the search tree is given a different name. Examples include AVL trees, red-black trees, height-balanced trees, weight-balanced trees, bounded-balance trees, path-balanced trees, B-trees, treaps, randomized |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www-tcs.cs.uni-sb.de/media/lectures/W1617/L-AlgorithmsandDataStructures18(BlockCourse)/scapegoat-splay.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
