Scribd Logo
Upload

Welcome to Scribd!

  • 152 views

    AVL Tree Assignment

    Uploaded by

    ishqi92
    1) An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. 2) A 2-3 tree is a tree where each internal node has either 2 children and 1 data element, or 3 children and 2 data elements. Leaf nodes have 1 or 2 data elements but no children. 3) A 2-3-4 tree is a self-balancing data structure similar to a B-tree that is used to implement dictionaries. It has equivalent functionality to a red-black tree but can be more difficult to implement.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd

    AVL Tree Assignment

    Uploaded by

    ishqi92
    152 views2 pages
    1) An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. 2) A 2-3 tree is a tree where each internal node has either 2 children and 1 data element, or 3 children and 2 data elements. Leaf nodes have 1 or 2 data elements but no children. 3) A 2-3-4 tree is a self-balancing data structure similar to a B-tree that is used to implement dictionaries. It has equivalent functionality to a red-black tree but can be more difficult to implement.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1) An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. 2) A 2-3 tree is a tree where each internal node has either 2 children and 1 data element, or 3 children and 2 data elements. Leaf nodes have 1 or 2 data elements but no children. 3) A 2-3-4 tree is a self-balancing data structure similar to a B-tree that is used to implement dictionaries. It has equivalent functionality to a red-black tree but can be more difficult to implement.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    152 views2 pages

    AVL Tree Assignment

    Uploaded by

    ishqi92
    1) An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. 2) A 2-3 tree is a tree where each internal node has either 2 children and 1 data element, or 3 children and 2 data elements. Leaf nodes have 1 or 2 data elements but no children. 3) A 2-3-4 tree is a self-balancing data structure similar to a B-tree that is used to implement dictionaries. It has equivalent functionality to a red-black tree but can be more difficult to implement.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 2

    AVL Tree

    Adelson-Velskii and Landis were the two persons who developed this
    technique that is why it was named after their names (AVL). They
    developed this technique to make tree balanced. AVL tree is almost
    identical to a BST but the following are the two differences:-
    1) - At most the height of left and right sub tree may differ by 1.
    2) - Empty tree’s is defined to be -1.

    2-3 Tree

    This is a tree in which each node with internal nodes has:-


    i) Two children and one data element viz. 2-nodes OR
    ii) 3-Children and 2-Data elements viz. 3-nodes
    The nodes which are on the outside of the tree i.e. leaf nodes, does not
    have any children and usually have one or two data elements.

    2-3-4 Tree

    It is also called a 2-4 tree. It is a self-balancing data structure and mostly


    it is used to implement dictionaries. These are B-trees and their order is
    2. Similar to B-trees they usually take O(Log-n) time in searching,
    inserting or deleting. External nodes in 2-3-4 tree are at same depth.

    Furthermore they are an isometry of red black trees. It means that red-
    black trees and 2-3-4 tress are equivalent data structures. So, for every
    2-3-4-tree at there is one re-black-tree exists with having data elements
    in the same order.
    Moreover, insertion and deletion operations on 2-3-4 trees that cause
    node expansions, splits and merges are equivalent to the color-flipping
    and rotations in red-black trees. Introductions to red-black trees usually
    introduce 2-3-4 trees first, because they are conceptually simpler. 2-3-4
    trees, however, can be difficult to implement in most programming
    languages because of the large number of special cases involved in
    operations on the tree. Red-black trees are simpler to implement, so
    tend to be used instead.

    Skip List

    A skip list is a data structure for storing a sorted list of items, using a
    hierarchy of linked lists that connect increasingly sparse subsequences
    of the items. These auxiliary lists allow item lookup with efficiency
    comparable to balanced binary search trees (that is, with number of
    probes proportional to log n instead of n).

    Each link of the sparser lists skips over many items of the full list in one
    step, hence the structure's name. These forward links may be added in
    a randomized way with a geometric / negative binomial distribution [1].
    Insert, search and delete operations are performed in logarithmic
    expected time. The links may also be added in a non-probabilistic way
    so as to guarantee amortized (rather than merely expected) logarithmic
    cost.

    You might also like