二叉树,红黑树

问题引入

问题引入

二叉搜索树

特点,简介

二叉搜索树特点,简介

代码简单功能实现

  • 二叉搜索树代码简单实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    public class BinarySearchTree
    {
    int data;
    BinarySearchTree left;
    BinarySearchTree right;

    public BinarySearchTree(int data)
    {
    this.data = data;
    }

    void insert(BinarySearchTree root, int data)
    {
    if (data < root.data)// 左插入
    {
    if (root.left == null)
    {
    root.left = new BinarySearchTree(data);
    } else
    {
    insert(root.left, data);
    }
    } else// 右插入
    {
    if (root.right == null)
    {
    root.right = new BinarySearchTree(data);
    } else
    {
    insert(root.right, data);
    }
    }
    }

    void in(BinarySearchTree root)
    {
    if (root != null)
    {
    in(root.left);
    System.out.print(root.data + " ");
    in(root.right);
    }
    }

    public static void main(String[] args)
    {
    int[] nums = {4, 12, 4, 58, 19, 0, 98, 23, 5, 0, 123};
    BinarySearchTree root = new BinarySearchTree(nums[0]);
    for (int i = 1; i < nums.length; i++)
    {
    root.insert(root, nums[i]);
    }
    // 从小到大依次输出
    root.in(root);
    }
    }

弊端

二叉搜索树的弊端

红黑树

性质

红黑树的性质

构建,变换方式

红黑树的构建,变换方式

左旋

左旋

右旋

右旋

旋转和颜色变换规则

红黑树-旋转和颜色变换规则
1-2
3-4

部分功能代码实现

  • 红黑树部分代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    public class Node
    {
    int data;
    Node left;
    Node right;
    Node parent;
    Boolean R;

    public Node(int data)
    {
    this.data = data;
    this.R = true;
    }

    // 查找根节点
    Node root()
    {
    for (Node root = this; ; )
    {
    if (root.parent == null)
    {
    return root;
    }
    root = root.parent;
    }
    }

    void insert(int data)
    {
    Node root = root();
    {
    root = new Node(data);
    root.R = false;
    } else
    {
    Node temp = root;
    while (true)
    {
    if (data < temp.data)// 左插入
    {
    if (temp.left == null)
    {
    temp.left = new Node(data);
    temp.left.parent = temp;
    break;
    } else
    {
    temp = temp.left;
    }
    } else// 右插入
    {
    if (temp.right == null)
    {
    temp.right = new Node(data);
    temp.right.parent = temp;
    break;
    } else
    {
    temp = temp.right;
    }
    }
    }
    }


    // 变色,左旋,右旋
    }

    // 左旋
    // 情况:父红,叔黑,是右子树
    // 旋转规则:以父亲左旋
    void RotateLeft(Node node)
    {
    Node right = node.right;

    right.left.parent = node;
    node.right = right.left;
    if (node.parent == null)// 根节点
    {
    right.parent = null;
    } else
    {
    right.parent = node.parent;
    if (right.data < node.parent.data)// 左
    {
    node.parent.left = right;
    } else// 右
    {
    node.parent.right = right;
    }
    }
    right.left = node;
    node.parent = right;
    }

    }