The following are several operations on a AA-tree:
1. Searching: Searching is done using an algorithm which is similar to the search algorithm of a binary search tree.
2. Insertion: The insertion procedure always starts from the bottom level. However, whereas performing this function, either of the two troubles can occur:
(a) Two consecutive horizontal links (right side)
(b) Left horizontal link.
Whereas studying the properties of AA-tree, we said that conditions (a) and (b) must not be satisfied. Therefore, in order to eliminate conditions (a) and (b), we employ two new functions namely skew ( ) & split( ) depend on the rotations of the node, so that all the properties of AA-trees are retained.
The condition that (a) two consecutive horizontal links in an AA-tree can be eliminated by a left rotation by split( ) while the condition (b) can be eliminated by right rotations through function show( ). Either of these functions can eliminate this condition, but can also arise the other condition. Let us show it with an example. Imagine, in the AA-tree of Figure, we have to insert node 50.
According to the condition, the node 50 will be added at the bottom level in such a way that it satisfies Binary Search tree property also
Now, we have to be aware as to how this left rotation is performed. Keep in mind, that rotation is introduced in Red-black tree and these rotations (left and right) are the similar as we performed in a Red-Black tree. Now, again split ( ) has removed its condition although has created skew conditions. Thus, skew ( ) function will now be called again and again till a complete AA-tree with a no false condition is obtained.
A skew problem arises since node 90 is two-level lower than its parent 75 and thus in order to avoid this, we call skew / split function again.
Therefore, introducing horizontal left links, to avoid left horizontal links and making them right horizontal links, we make three calls to skew and then two calls to split to remove consecutive horizontal links
A Treap is another kind of Binary Search tree and has one property distinct from other types of trees. Each of the nodes in the tree stores an item, a left & right pointer and a priority that is randomly assigned while the node is created. Whereas assigning the priority, it is essential that the heap order priority has to be maintained: node's priority must be at least as large as its parent's. A treap is both binary search tree with respect to node elements and a heap with respect to node priorities.