Scribd Logo
Upload

Welcome to Scribd!

  • 50 views

    Splay Trees

    Uploaded by

    Avinash Alla
    The document discusses different types of self-balancing binary search trees including AVL trees, splay trees, and red-black trees. It provides information on deletion, search, and traversal operations for AVL trees. For splay trees, it explains that each operation rearranges the tree to place the accessed element at the root, and describes different rotation operations used for splaying. Red-black trees are defined as binary search trees where each node is colored red or black, and properties such as the root being black and no adjacent red nodes are outlined.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Splay Trees

    Uploaded by

    Avinash Alla
    50 views4 pages
    The document discusses different types of self-balancing binary search trees including AVL trees, splay trees, and red-black trees. It provides information on deletion, search, and traversal operations for AVL trees. For splay trees, it explains that each operation rearranges the tree to place the accessed element at the root, and describes different rotation operations used for splaying. Red-black trees are defined as binary search trees where each node is colored red or black, and properties such as the root being black and no adjacent red nodes are outlined.

    Original Title

    SPLAY TREES

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses different types of self-balancing binary search trees including AVL trees, splay trees, and red-black trees. It provides information on deletion, search, and traversal operations for AVL trees. For splay trees, it explains that each operation rearranges the tree to place the accessed element at the root, and describes different rotation operations used for splaying. Red-black trees are defined as binary search trees where each node is colored red or black, and properties such as the root being black and no adjacent red nodes are outlined.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    50 views4 pages

    Splay Trees

    Uploaded by

    Avinash Alla
    The document discusses different types of self-balancing binary search trees including AVL trees, splay trees, and red-black trees. It provides information on deletion, search, and traversal operations for AVL trees. For splay trees, it explains that each operation rearranges the tree to place the accessed element at the root, and describes different rotation operations used for splaying. Red-black trees are defined as binary search trees where each node is colored red or black, and properties such as the root being black and no adjacent red nodes are outlined.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    Try this Example

    Construct an AVL Tree with the following sequence of elements.


    25, 7, 5,20,13,11,9,24,50,17,43

    Deletion operation in AVL Tree:


     The deletion operation in AVL Tree is similar to deletion operation in BST.
     But after every deletion operation we need to check with the Balance Factor condition.
     If the tree is balanced after deletion go for next operation otherwise perform suitable rotation
    to make the tree Balanced.

    Search opeartion in AVL Tree:


     We perform search operation on AVL Tree as standard BST search operation.
     Search operation on AVL Tree does not need any rotation.
    Tree traversing Tecniques:
     Tree traversing techniques on AVL Tree are same as BST traversing techniques.
     The tree traversing techniques are inorder, preorder and postorder.

    ---------------------------------------------Splay Tree------------------------------------------

    Splay Tree is a self - adjusted Binary Search Tree in which every operation on an element
    rearranges the tree so that the element is placed at the root position of the tree.

    In a splay tree, every operation is performed at root of the tree. All the operations on a splay tree are
    involved with a common operation called "Splaying".

    Splaying an element is the process of bringing it to the root position by performing suitable rotation
    operations.

    In a splay tree, splaying an element rearrange all the elements in the tree so that splayed element is
    placed at root of the tree.

    With the help of splaying an element we can bring most frequently used element closer to the root
    of the tree so that any operation on those element performed quickly. That means the splaying
    operation automatically brings more frequently used elements closer to the root of the tree.

    Every operation on a splay tree performs the splaying operation. For example, the insertion
    operation first inserts the new element as it inserted into the binary search tree, after insertion the
    newly inserted element is splayed so that it is placed at root of the tree. The search operation in a
    splay tree is search the element using binary search process then splay the searched element so that
    it placed at the root of the tree.
    In a splay tree, to splay any element we use the following rotation operations...

    Rotations in Splay Tree


     1. Zig Rotation
     2. Zag Rotation
     3. Zig - Zig Rotation
     4. Zag - Zag Rotation
     5. Zig - Zag Rotation
     6. Zag - Zig Rotation

    Examples
    Zig Rotation
    The Zig Rotation in a splay tree is similar to the single right rotation in AVL Tree rotations. In zig
    rotation every node moves one position to thr righ from its current position. Consider the following
    example...

    Zag Rotation

    The Zag Rotation in a splay tree is similar to the single left rotation in AVL Tree rotations. In zag
    rotation every node moves one position to the left from its current position. Consider the following
    example...

    Zig-Zig Rotation
    The Zig-Zig Rotation in a splay tree is a double zig rotation. In zig-zig rotation every node moves
    two position to the right from its current position. Consider the following example...
    Zag-Zag Rotation
    The Zag-Zag Rotation in a splay tree is a double zag rotation. In zag-zag rotation every node
    moves two position to the left from its current position. Consider the following example...

    Zig-Zag Rotation
    The Zig-Zag Rotation in a splay tree is a sequence of zig rotation followed by zag rotation. In zig-
    zag rotation every node moves one position to the right followed by one position to the left from its
    current position. Consider the following example...

    Zag-Zig Rotation
    The Zag-Zig Rotation in a splay tree is a sequence of zag rotation followed by zig rotation. In zag-
    zig rotation every node moves one position to the left followed by one position to the right from its
    current position. Consider the following example...

    Every Splay tree must be a binary search tree but it is need not to be balanced tree.

    Try this Example: Construct a splay tree with following elements.


    12,25,7,5,15,24
    Applications of Splay Trees:
     Splay trees have become the most widely used basic data structure because they’re the
    fastest type of balanced search tree for many applications.
     Splay trees are used in Windows NT (in the virtual memory, networking, and file system
    code).
     In the gcc compiler and GNU C++ library, the sed string editor.
     In Fore Systems network routers, the most popular implementation of Unix malloc, Linux
    loadable kernel modules, and in much other software.

    RED-BLACK TREES
    Red-Black Tree is a self-balancing Binary Search Tree in which every node is colored either RED
    or BLACK.
    In Red Black Tree, the color of a node is decided based on the properties of Red Black Tree.

    Properties of Red Black Tree

     Property #1: Red - Black Tree must be a Binary Search Tree.


     Property #2: The ROOT node must be colored BLACK.
    Type your text
     Property #3: The children of Red colored node must be colored BLACK. (There should not
    be two consecutive RED nodes).
     Property #4: In all the paths of the tree, there should be same number of BLACK colored
    nodes.
     Property #5: Every new node must be inserted with RED color.

    Why Red-Black Trees?


     Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where
    h is the height of the BST.

     The cost of these operations may become O(n) for a skewed Binary tree.

     If we make sure that height of the tree remains O(logn) after every insertion and deletion,
    then we can guarantee an upper bound of O(logn) for all these operations.

     The height of a Red-Black tree is always O(logn) where n is the number of nodes in the tree.

     Comparison with AVL Tree


    The AVL trees are more balanced compared to Red-Black Trees, but they may cause more
    rotations during insertion and deletion.

    You might also like