Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 36 views

    Red Black Trees: Erin Keith

    Uploaded by

    maya fisher
    This document provides an overview of red black trees. It begins by discussing balanced search trees and their properties. It then reviews other balanced binary search trees like AVL trees, 2-3 trees, and 2-3-4 trees. It introduces red black trees as a way to represent 2-3-4 trees using a binary search tree structure while requiring less storage. The key properties of red black trees are described, including that the root is black, red nodes have black parents, red nodes have black children, and all paths from the root to a leaf contain the same number of black nodes.

    Copyright:

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

    Red Black Trees: Erin Keith

    Uploaded by

    maya fisher
    36 views24 pages
    This document provides an overview of red black trees. It begins by discussing balanced search trees and their properties. It then reviews other balanced binary search trees like AVL trees, 2-3 trees, and 2-3-4 trees. It introduces red black trees as a way to represent 2-3-4 trees using a binary search tree structure while requiring less storage. The key properties of red black trees are described, including that the root is black, red nodes have black parents, red nodes have black children, and all paths from the root to a leaf contain the same number of black nodes.

    Original Description:

    CS 302 - Data Structures Notes

    Original Title

    19_Red_Black_Tree

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an overview of red black trees. It begins by discussing balanced search trees and their properties. It then reviews other balanced binary search trees like AVL trees, 2-3 trees, and 2-3-4 trees. It introduces red black trees as a way to represent 2-3-4 trees using a binary search tree structure while requiring less storage. The key properties of red black trees are described, including that the root is black, red nodes have black parents, red nodes have black children, and all paths from the root to a leaf contain the same number of black nodes.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    36 views24 pages

    Red Black Trees: Erin Keith

    Uploaded by

    maya fisher
    This document provides an overview of red black trees. It begins by discussing balanced search trees and their properties. It then reviews other balanced binary search trees like AVL trees, 2-3 trees, and 2-3-4 trees. It introduces red black trees as a way to represent 2-3-4 trees using a binary search tree structure while requiring less storage. The key properties of red black trees are described, including that the root is black, red nodes have black parents, red nodes have black children, and all paths from the root to a leaf contain the same number of black nodes.

    Copyright:

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

    Red Black Trees

    ERIN KEITH

    19_RED_BLACK_TREE 1
    Topics
    1. Balanced Search Trees
    2. Red Black Trees

    19_RED_BLACK_TREE 2
    Balanced Search Tree
    a tree that automatically keeps its height small (guaranteed to be
    logarithmic) for a sequence of insertions and deletions.

    19_RED_BLACK_TREE 3
    Balanced Search Tree
    a tree that automatically keeps its height small (guaranteed to be
    logarithmic) for a sequence of insertions and deletions.
    • There is a relationship between efficiency and the height of a
    tree
    • In general, the time complexity of searching is O(h) where h is
    height of BST

    19_RED_BLACK_TREE 4
    Balanced
    Search Tree
    a tree that automatically
    keeps its height small
    (guaranteed to be
    logarithmic) for a
    sequence of insertions
    and deletions.

    19_RED_BLACK_TREE 5
    Linked Implementation
    template<class ItemType>
    bool LinkedBTree<ItemType>::add(const ItemType& newData){
    LinkedBTreeNode<ItemType>* newNodePtr = new LinkedBTreeNode<ItemType>(newData);
    rootPtr = balancedAdd(rootPtr, newNodePtr);
    return true;
    }

    19_RED_BLACK_TREE 6
    AVL Search Tree
    a balanced tree where rotations restore balance.

    19_RED_BLACK_TREE 7
    AVL Search Tree
    a balanced tree where rotations restore balance.

    19_RED_BLACK_TREE 8
    2-3 Search Tree
    • Interior nodes are either 2-nodes or 3-nodes
    • 2-node has one data item and two children
    • 3-node has two data items and three children
    • Are never taller than minimum-height binary tree
    • A 2-3 tree with n nodes never has height greater than log2 (𝑛 +
    1)

    19_RED_BLACK_TREE 9
    2-3 Search Tree

    19_RED_BLACK_TREE 10
    2-3 Search Tree
    • To traverse a 2-3 Tree, perform the analogue of an in-order
    traversal
    • Leftmost subtree
    • Left value
    • Center subtree
    • Right value
    • Rightmost subtree
    • Searching a 2-3 tree is as efficient as searching the shortened
    binary tree (with the same values)
    • 𝑂(log2𝑛)

    19_RED_BLACK_TREE 11
    2-3 Search Tree

    19_RED_BLACK_TREE 12
    2-3-4 Search
    Tree
    If a 2-3 search tree is good
    then a 2-3-4 search tree is
    even better?
    ◦ More efficient addition
    and removal operations
    than a 2-3 tree

    19_RED_BLACK_TREE 13
    2-3-4 Search Tree
    where r is a node that contains one to three data
    items and TL, TML, TMR and TR are 2-3-4 trees of
    height h-1.
    In this case: smallest item in r must be greater
    than each item in TL and smaller than each item in
    TML. The middle item in r must be greater than
    each in TML and smaller than each item in TMR.
    The largest item in r must be greater than each
    item in TMR and smaller than TR.

    19_RED_BLACK_TREE 14
    2-3-4 Search Tree
    ◦ A 2-node must contain a single data item that satisfies the relationships
    as in a 2-3 tree.
    ◦ A 3-node must contain two data items that satisfy the relationships as in
    a 2-3 tree.
    ◦ A 4-node must contain three data items S, M, and L that satisfy the
    following relationships: S is greater than the left child’s item(s) and less
    than the middle-left child’s item(s); M is greater than the middle-left
    child’s item(s) and less than the middle-right child’s item(s); L is greater
    than the middle-right child’s item(s) and less than the right child’s
    item(s).
    ◦ A leaf may contain either one, two, or three data items.

    19_RED_BLACK_TREE 15
    2-3-4 Search
    Tree
    If a 2-3 search tree is good
    then a 2-3-4 search tree is
    even better?
    ◦ More efficient addition
    and removal operations
    than a 2-3 tree
    BUT!
    ◦ Has greater storage
    requirements due to the
    additional data members
    in its 4-nodes

    19_RED_BLACK_TREE 16
    Red Black Tree
    Represent any 2-3-4 tree as a BST
    Has the advantages of a 2-3-4 tree but requires less
    storage
    ◦ Red pointers link 2-nodes that now contain values that were in
    a 3-node or a 4-node
    ◦ A red pointer references a red node
    ◦ A black pointer references a black node
    ◦ Use “internal” red edges for 3- and 4-nodes

    19_RED_BLACK_TREE 17
    Red Black Tree

    19_RED_BLACK_TREE 18
    Red Black Tree

    19_RED_BLACK_TREE 19
    Red Black Tree
    Properties of a Red Black Tree:
    ◦ The root is black
    ◦ Every red node has a black parent
    ◦ Any children of a red node are black
    ◦ a red node cannot have red children
    ◦ Every path from the root to a leaf contains the same number of
    black nodes

    19_RED_BLACK_TREE 20
    Red Black
    Tree
    The root is black
    All leaves (nil) are black

    19_RED_BLACK_TREE 21
    Red Black
    Tree
    All red nodes have black
    children

    19_RED_BLACK_TREE 22
    Red Black
    Tree
    All paths from a node to its
    leaf(nil) descendants
    contain the same number of
    black nodes

    19_RED_BLACK_TREE 23
    Next Class
    Red Black Trees
    Textbook:
    • Chapters 19.4
    Internet:
    •https://www.autonomousrobotslab.com/uploads/5/8
    /4/4/58449511/cs302-123-red-black-trees.pdf

    19_RED_BLACK_TREE 24

    You might also like