A Beveled Tree or Splay Tree [1] is a self-balancing binary search Tree, with the additional property that recently accessed elements will be accessed more quickly on subsequent accesses. It performs basic operations such as insertion, search and deletion in a time of the order of O (log n). For many non-uniform sequences of operations, the bevel tree performs better than other search trees, even when the specific pattern of the sequence is unknown. This data structure was invented by Robert Tarjan and Daniel Sleator .
All the normal operations of a binary search tree are combined with a basic operation, called chamfering. This operation consists of rearranging the tree for a certain element, placing it at the root . One way to do this is to first do a binary search of the tree to find the item in question, and then use tree rotations in a specific way to bring the item to the top. Alternatively, a “top-down” algorithm can combine searching and tree reorganization in one step.
Summary
[ hide ]
- 1 Advantages and disadvantages
- 2 Operations
- 1 Search
- 2 Insertion
- 3 Disposal
- 3 Chamfering operation
- 1 Upward beveling
- 2 Downward bevel
- 4 Yield theorems
- 1 Balance theorem
- 2 Dynamic Optimality Conjecture
- 5 References
- 6 Sources
Advantages and disadvantages
The good performance of a beveled shaft [2] depends on the fact that it is self-balancing, and it is also automatically optimized. The most frequently accessed nodes will move closer to the root where they can be accessed more quickly. This is an advantage for almost all applications, and is particularly useful for implementing caches and garbage collection algorithms; however, it is important to note that for uniform access, the performance of a beveled tree will be considerably worse than a simple balanced binary search tree .
Bevel trees also have the advantage of being considerably simpler to implement than other self-balancing binary search trees, such as Red-Black trees or AVL trees, while their performance in the average case is just as efficient. Furthermore, beveled trees do not need to store any additional information other than the data itself, thus minimizing memory requirements. However, these additional data structures provide worst-case guarantees, and may be more efficient in practice for uniform access.
One of the worst cases for the algorithmbasic of the beveled tree is the sequential access to all the elements of the tree in an ordered way. This leaves the tree completely unbalanced (n accesses are required, each of which is on the order of O (log n) operations). Accessing the first element again triggers an operation that takes the order of O (n) operations to re-balance the tree before returning this first element. This is a significant delay for that final operation, although the performance pays off if we consider the entire sequence, which is on the order of O (log n). However, recent research shows that if we randomly re-balance the tree we can avoid this imbalance effect and give a similar performance to other auto-balancing algorithms.
Unlike other types of self-balancing trees, beveled trees work well with nodes that contain identical keys. Even with identical keys, the performance remains amortized on the order of O (log n). All tree operations preserve the order of identical nodes within the tree, which is a property similar to the stability of sort algorithms.
Operations
Search
Searching for [3] a key value in a beveled tree has the particular characteristic that it modifies the structure of the tree . Descent is done in the same way as a binary search tree, but if a node is found whose key value matches the one searched for, a bevel of that node is performed. If not found, the bevel node will be the one we visited last before discarding the search. Thus, the root will contain a successor or predecessor of the searched node .
Insertion
It is the same as in the binary search tree with the exception that a bevel is performed on the inserted node . Also, if the key value to insert already exists in the tree , the node containing it is beveled .
Elimination
This operation requires two bevels. First the node that contains the key value to extract is searched . If it is not found, the tree is beveled at the last node examined and no further action is taken. If found, the node is beveled and removed. With this, the tree is separated into two halves, so you have to select a node to act as the root. As it is a binary search tree and all the key values are ordered, we can choose as root the highest value of the left subtree or the lowest key value of the right.
Chamfering operation
This operation moves a node x, which is the accessed node, to the root . To perform this operation we must rotate the tree so that in each rotation the node x is closer to the root . Each bevel performed on the node of interest keeps the tree partially balanced and also the recently accessed nodes are in the immediate vicinity of the root . In this way, we amortize the time used to perform the beveling. We could distinguish 3 general cases:
- Case 1: x is the left or right child of the root, p.
- Case 2: x is the left child of p and this in turn is the left child of q or both are right children.
- Case 3: x is the left child of p and this in turn is the right child of q or vice versa.
CASE 1: If x is a left child of p then we will perform a simple right rotation. In case x is the right, the rotation that we must make is simple left.
CASE 2: If x is the left child and grandchild of p and q, respectively. Then we must perform double rotation to the right, in case x is the right child and grandchild of p and q, the rotation will be double left.
CASE 3: In case x is the left child of p and the right grandchild of q, we will perform a simple right rotation on the edge between x and p and another simple left between x and q. Otherwise, x is the right child and the left grandchild of q, the simple rotations will be left and then right.
Upward bevel
OP operations [4] are performed in a similar way to a binary search tree. Then a bevel operation is performed on a node . In a search, the node that contains the searched value is returned , or the parent of the sheet if it cannot be found. In an insert, the node on which the bevel operation is applied is the one with the same value as the one sought, if it already existed; or the new node if it was not in the tree . In ascending bevel, it is required to descend from the root to the node to which the bevel operation will be applied. Then the rotations are made as you ascend.
In other words, the tree is traversed twice. Starting from the node , to which the operation will be applied, it is promoted until the grandfather is found, and the corresponding double rotation is carried out; if there is no grandfather, but there is a father, simple rotation is performed.
Downward bevel
It consists of splitting the tree into two subtrees, one with keys smaller than the one sought and the other with keys greater than the one sought, and as it descends, the rotations are carried out. When the node is found at the root of the central subtree, the subtrees are joined, leaving the node as the root . Every time it descends from a node x, by a left link, then x and its right subtree will be greater than the node (that will be inserted or that is searched). In this way a subtree can be formed, with x and its right subtree, this subtree being DER.
The symmetric case, which occurs when a right link is followed, makes it possible to identify the left subtree of the new root , be this subtree called LEFT. As it is traveled only once, it takes up half the time of the ascendant. Pointers are kept to LEFT and RIGHT, and pointers to insertion points of new nodes in LEFT and RIGHT; these are the right child of the highest element of LEFT; and the left child of the least element of DER. These variables avoid the need to traverse LEFT and RIGHT; nodes and subtrees that are added to LEFT or RIGHT, do not change their positions in LEFT or RIGHT. Starting from the root, one descends until a possible grandson is found, the operation is carried out by passing the grandfather and the father to the LEFT and RIGHT subtrees; the grandson remains at the rootof the central tree . If the node is found , a final join is made.
Yield theorems
Balance theorem
The cost of performing the access sequence S is of the order of O (m (logn + 1) + nlogn). In other words, beveled trees perform as well as statically balanced binary search trees in sequences of at least n accesses.
Dynamic Optimality Conjecture
In addition to the proven guarantees of the performance of beveled shafts, in the original paper by Sleator and Tarjan there is an unproven conjecture of great interest. This conjecture is known as the Dynamic Optimality Conjecture, and it basically argues that beveled trees behave as well as any other binary tree search algorithm up to a constant factor.
Let A be any binary tree search algorithm that accesses an element x traversing the path from the root to x, at a cost of d (x) + 1, and that between the accesses it can make any rotation in the tree at a cost of 1 per rotation. Let A (S) be the cost for A to perform the sequence S of accesses. Then the cost of making the same accesses for a beveled tree is of the order O (n + A (S)).
There are several corollaries of the Dynamic Optimality Conjecture that remain unproven:
Cross Conjecture: Let T1 and T2 be twobeveled trees that contain the same elements. Let S be the sequence obtained after visiting the elements of T2 in preorder. The total cost to carry out the sequence S of accesses in T1 is of the order of O (n). Deque conjecture: Let S be a sequence of m doubly terminated queue operations (push, pop, inject, eject). Then the cost for carrying out this sequence of operations S in abeveled tree is of the order of O (m + n).
Split conjecture: Let S be any permutation of the elements of the beveled tree . Then the cost of removing the elements in the order S is of the order of O (n).
