Scribd Logo
Upload

Welcome to Scribd!

  • 84 views

    20mca105 Advanced Data Structures: Module-1 Note-4

    Uploaded by

    jack sparrow
    A tree is a nonlinear hierarchical data structure consisting of nodes connected by edges. Different tree structures allow for quicker access to data as trees are nonlinear. Key aspects of trees include nodes, edges, the root node, height and depth of nodes, degree of nodes, and types of trees including binary trees, binary search trees, AVL trees, and B-trees.

    Copyright:

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

    20mca105 Advanced Data Structures: Module-1 Note-4

    Uploaded by

    jack sparrow
    84 views12 pages
    A tree is a nonlinear hierarchical data structure consisting of nodes connected by edges. Different tree structures allow for quicker access to data as trees are nonlinear. Key aspects of trees include nodes, edges, the root node, height and depth of nodes, degree of nodes, and types of trees including binary trees, binary search trees, AVL trees, and B-trees.

    Original Title

    DS4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    A tree is a nonlinear hierarchical data structure consisting of nodes connected by edges. Different tree structures allow for quicker access to data as trees are nonlinear. Key aspects of trees include nodes, edges, the root node, height and depth of nodes, degree of nodes, and types of trees including binary trees, binary search trees, AVL trees, and B-trees.

    Copyright:

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

    20mca105 Advanced Data Structures: Module-1 Note-4

    Uploaded by

    jack sparrow
    A tree is a nonlinear hierarchical data structure consisting of nodes connected by edges. Different tree structures allow for quicker access to data as trees are nonlinear. Key aspects of trees include nodes, edges, the root node, height and depth of nodes, degree of nodes, and types of trees including binary trees, binary search trees, AVL trees, and B-trees.

    Copyright:

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

    20MCA105 ADVANCED DATA

    STRUCTURES
    Module-1
    Note-4
    Tree Data Structure
    A tree is a nonlinear hierarchical data structure that consists of
    nodes connected by edges.
    Different tree data structures allow quicker and easier access to the
    data as it is a non-linear data structure.
    Tree Terminologies
    Node
    A node is an entity that contains a key or value and pointers to its child
    nodes.
    The last nodes of each path are called leaf nodes or external
    nodes that do not contain a link/pointer to child nodes.
    The node having at least a child node is called an internal node.
    Edge
    It is the link between any two nodes.
    Root
    It is the topmost node of a tree.

    Height of a Node
    The height of a node is the number of edges
    from the node to the deepest leaf (ie. the
    longest path from the node to a leaf node).

    Depth of a Node

    The depth of a node is the number of edges


    from the root to the node.

    Height of a Tree
    The height of a Tree is the height of the root
    node or the depth of the deepest node.
    Degree of a Node
    The degree of a node is the total number of branches of that node.
    Forest
    A collection of disjoint trees is called a forest.

    Types of Tree
    Binary Tree
    Binary Search Tree
    AVL Tree
    B-Tree
    Binary Tree
    A binary tree is a tree data structure in which each parent node can have
    at most two children. Each node of a binary tree consists of three items:
    •data item
    •address of left child
    •address of right child
    Binary Search Tree(BST)

    Binary search tree is a data structure that quickly allows us to


    maintain a sorted list of numbers.

    It is called a binary tree because each tree node has a maximum of


    two children.
    It is called a search tree because it can be used to search for the
    presence of a number in O(log(n)) time.
    The properties that separate a binary search tree from a regular binary tree is
    1.All nodes of left subtree are less than the root node
    2.All nodes of right subtree are more than the root node
    3.Both subtrees of each node are also BSTs i.e. they have the above two properties
    AVL Tree
    AVL tree is a self-balancing binary search tree in which each
    node maintains extra information called a balance factor
    whose value is either -1, 0 or +1.
    AVL tree got its name after its inventor Georgy Adelson-
    Velsky and Landis.

    Tree is said to be balanced if balance factor of each node is in between -1 to 1,


    otherwise, the tree will be unbalanced and need to be balanced.
    Balance Factor (k) = height (left(k)) - height (right(k))
    B Tree
    B Tree is a specialized m-way tree. B-Tree of order m
    can have at most m-1 keys and m children. One of the
    main reason of using B tree is its capability to store
    large number of keys in a single node
    B-Tree properties :
    •Every node in B-Tree will hold maximum m children
    •Every node except root and leaves, can hold at least m/2
    children
    •The root nodes must have at least two children.
    •All leaf nodes must be at same level

    You might also like