Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Balanced Search Trees

    Uploaded by

    Anna Tabuashvili

    Copyright:

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

    Balanced Search Trees

    Uploaded by

    Anna Tabuashvili
    4 views4 pages

    Original Title

    Balanced search trees

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Balanced Search Trees

    Uploaded by

    Anna Tabuashvili

    Copyright:

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

    1. Balanced search trees.

    A binary tree is balanced if the height of the tree is O(Log n) where n is the
    number of nodes. For Example, the AVL tree maintains O(Log n) height by
    making sure that the difference between the heights of the left and right subtrees
    is at most 1. Red-Black trees maintain O(Log n) height by making sure that the
    number of Black nodes on every root-to-leaf path is the same and that there are
    no adjacent red nodes. Balanced Binary Search trees are performance-wise good
    as they provide O(log n) time for search, insert and delete.

    A balanced binary tree is a binary tree that follows the 3 conditions:

     The height of the left and right tree for any node does not differ by more
    than 1.
     The left subtree of that node is also balanced.
     The right subtree of that node is also balanced.
    A single node is always balanced. It is also referred to as a height-balanced
    binary tree.
    Application of Balanced Binary Tree:
     AVL Trees
     Red Black Tree
     Balanced Binary Search Tree
    Advantages of Balanced Binary Tree:
     Non Destructive updates are supported by a Balanced Binary Tree with
    the same asymptotic effectiveness.
     Range queries and iteration in the right sequence are made feasible by
    the balanced binary tree.

    2. AVL trees.
    AVL trees are a type of self-balancing binary search tree (BST) named after their inventors,
    Adelson-Velsky and Landis. They maintain a balanced structure to ensure that operations such as
    search, insertion, and deletion can be performed in O(log⁡n)O(\log n)O(logn) time, where nnn is
    the number of nodes in the tree. Here are the key concepts and characteristics you need to
    understand about AVL trees:
    Key Characteristics of AVL Trees:

    1. Balance Factor:
    o The balance factor of a node in an AVL tree is the difference in height between its
    left and right subtrees.
    o Balance Factor = Height(Left Subtree) - Height(Right Subtree).
    o For an AVL tree, the balance factor of every node must be -1, 0, or 1.
    2. Height:
    o The height of an AVL tree with nnn nodes is O(log⁡n)O(\log n)O(logn), ensuring
    efficient operations.
    o This height is maintained by the balancing operations performed during insertions
    and deletions.
    3. Rotations:
    o To maintain the balance factor within the allowed range, AVL trees use rotations.
    o There are four types of rotations used to rebalance the tree:
    1. Left Rotation (LL Rotation): Used when a node is inserted into the right
    subtree of the right subtree.
    2. Right Rotation (RR Rotation): Used when a node is inserted into the left
    subtree of the left subtree.
    3. Left-Right Rotation (LR Rotation): Used when a node is inserted into
    the right subtree of the left subtree.
    4. Right-Left Rotation (RL Rotation): Used when a node is inserted into
    the left subtree of the right subtree.

    Important Operations:

    1. Insertion:
    o When inserting a node, you perform the standard BST insertion.
    o After insertion, update the height of the affected nodes and check the balance
    factor.
    o If the balance factor of any node becomes -2 or 2, perform the necessary rotations
    to restore balance.
    2. Deletion:
    o Perform the standard BST deletion.
    o After deletion, update the height and check the balance factor of the affected
    nodes.
    o If the balance factor becomes unbalanced, perform the necessary rotations to
    restore balance.
    3. B+ trees.
    4. Representations of graphs.
    5. Adjacency lists and adjacency matrices.
    6. Breadth first search.
    7. Shortest paths in unweighted graphs.
    8. Depth first search.
    9. Discovery and finishing times.
    10. Classification of edges.
    11. Connected and strongly connected graphs.
    12. Directed acyclic graphs.
    13. Topological ordering.
    14. Shortest paths in weighted graphs.
    15. Dijkstra algorithm.
    16. Bellman-Ford algorithm.
    17. Negative cycles.
    18. Minimum spanning trees.
    19. Prim algorithm.
    20. Kruskal algorithm.
    21. Union-find data structure.

    You might also like