• 树（二叉查找树BST、二叉平衡树AVL、红黑树R-B）

    目录

    一、二叉树

    二、二叉排序树(BST)

    性质：

    插入规则：

    删除规则：

    二叉查找树代码实现：

    三、完全二叉树

    判断一棵树是否是完全二叉树的思路

    层次遍历代码(Java)---leetCode102:

    四、平衡二叉树（AVL）

    性质：

    旋转：

    概念：

    插入步骤：

    删除规则：

    JAVA实现平衡二叉树的插入、删除等等操作以及测试代码

    五、红黑树(R-B Tree)

    性质：

    旋转：

    红黑树的插入步骤：

     红黑树插入实现(Java)

    一、二叉树

    每个节点最多有两个叶子节点的树是二叉树。

    二、二叉排序树(BST)

    也叫二叉查找树和二叉搜索树

    性质：

    1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    3. 它的左、右子树也分别为二叉排序树

    插入规则：

    比父节点小的值放左边，比父节点大的值，放右边，一个父节点最多只能有两个子节点

    删除规则：

    1. 删除叶子节点，直接删除
    2. 删除只有左子树或者是有右子树的节点，删除节点，左子树或者右子树直接接上
    3. 删除有左子树和右子树的节点P，找到删除节点的直接后继节点H，节点H替换节点P，删除原来的P节点

    （PS：直接后继节点：中序遍历，在删除节点P后一位的节点为直接后继节点）

    二叉查找树代码实现：

    1. /**
    2.  * @author Admin
    3.  */
    4. public class BSTTree {
    5. 	/**
    6.      * 定义二叉树
    7.      */
    8.     class Node{
    9.         public int iData;
    10.         public double dData;
    11.         public Node leftNode;
    12.         public Node rightNode;
    13.         public void showNode(){
    14.             System.out.println("{"+iData+","+dData+"}");
    15.         }
    16.     }
    17.  
    18.     private Node root;
    19.  
    20.     /**
    21.      * 插入节点
    22.      * 规则：比父节点小的值放左边，比父节点大的值，放右边，一个父节点最多只能有两个子节点
    23.      * @param iData
    24.      * @param dData
    25.      */
    26.     public void insert(int iData,double dData){
    27.         Node newNode = new Node();
    28.         newNode.iData = iData;
    29.         newNode.dData = dData;
    30.         if(root==null){
    31.             root = newNode;
    32.         }else{
    33.             Node current = root;
    34.             Node parent;
    35.             while (true){
    36.                 parent = current;
    37.                 //插入左节点
    38.                 if(iData< current.iData){
    39.                     current=current.leftNode;
    40.                     if(current==null){
    41.                         parent.leftNode=newNode;
    42.                         return;
    43.                     }
    44.                 }else{//插入右节点
    45.                     current=current.rightNode;
    46.                     if(current==null){
    47.                         parent.rightNode = newNode;
    48.                         return;
    49.                     }
    50.                 }
    51.             }
    52.         }
    53.     }
    54.  
    55.     /**
    56.      * 查找节点
    57.      * @param key
    58.      * @return
    59.      */
    60.     public Node find(int key){
    61.         Node current = root;
    62.         if(current==null){
    63.             return new Node();
    64.         }
    65.         while(current.iData!=key){
    66.             if(current.iData>key){
    67.                 current=current.leftNode;
    68.             }else{
    69.                 current=current.rightNode;
    70.             }
    71.             if(current==null){
    72.                 return new Node();
    73.             }
    74.         }
    75.         return current;
    76.     }
    77.  
    78.     /**
    79.      * 规则:
    80.      * 1、删除叶子节点，直接删除
    81.      * 2、删除只有左子树或者是有右子树的节点，删除节点，左子树或者右子树直接接上
    82.      * 3、删除有左子树和右子树的节点P，找到删除节点的直接后继节点H，节点H替换节点P，删除原来的P节点
    83.      * 直接后继节点：中序遍历，在节点P后一位的节点为直接后继节点
    84.      * @param key
    85.      */
    86.     public void delete(int key){
    87.         //找到需要删除的节点
    88.         Node current = find(key);
    89.         Node parent = current==null?null:current.parentNode;
    90.         if(current!=null){
    91.             //删除节点的左子树不为空
    92.             if(current.leftNode != null && current.rightNode != null){
    93.                 //查询待删除节点的直接后继节点
    94.                 Node successorNode = getSuccessorNode(current);
    95.                 //保存节点数据，便于后面的替换
    96.                 int iData = successorNode.iData;
    97.                 double dData = successorNode.dData;
    98.                 //删除该后继节点
    99.                 delete(successorNode.iData);
    100.                 //替换节点
    101.                 current.iData = iData;
    102.                 current.dData = dData;
    103.             }else if(current.leftNode != null || current.rightNode != null){
    104.                 //删除含有左子树或者右子树的节点,将删除节点的父节点直接连接删除节点的左子树或者右子树
    105.                 if(current.leftNode!=null){
    106.                     current.leftNode.parentNode = parent;
    107.                 }else{
    108.                     current.rightNode.parentNode = parent;
    109.                 }
    110.                 if(parent!=null){
    111.                     if(parent.iData>current.iData){
    112.                         parent.leftNode = current.leftNode != null?current.leftNode:current.rightNode;
    113.                     }else{
    114.                         parent.rightNode = current.leftNode != null?current.leftNode:current.rightNode;
    115.                     }
    116.                 }else{
    117.                     //删除节点为根节点，直接将根节点替换为下一个节点
    118.                     if(current.leftNode!=null){
    119.                         root = current.leftNode;
    120.                     }else{
    121.                         root = current.rightNode;
    122.                     }
    123.                 }
    124.             }else{
    125.                 //删除叶子节点
    126.                 if(parent==null){
    127.                     //根节点，直接将树置空
    128.                     root = null;
    129.                 }else{
    130.                     //删除叶子节点,直接置空
    131.                     if(parent.iData>current.iData){
    132.                         parent.leftNode = null;
    133.                     }else{
    134.                         parent.rightNode = null;
    135.                     }
    136.                 }
    137.             }
    138.         }
    139.     }
    140.  
    141.     /**
    142.      * 获取节点的直接后继节点
    143.      * @param node
    144.      * @return
    145.      */
    146.     public Node getSuccessorNode(Node node){
    147.         Node current = node==null?null:node.rightNode;
    148.         if(current==null){
    149.             return null;
    150.         }
    151.         while(current.leftNode!=null){
    152.             current = current.leftNode;
    153.         }
    154.         return current;
    155.     }
    156.  
    157.     /**
    158.      * 查找树最小值和最大值
    159.      * @return
    160.      */
    161.     public Node[] mVal(){
    162.         Node current = root;
    163.         Node maxCurrent = current;
    164.         Node minCurrent = current;
    165.         Node[] minAndMaxVal = new Node[2];
    166.         while(minCurrent.leftNode!=null){
    167.             minCurrent = minCurrent.leftNode;
    168.         }
    169.         minAndMaxVal[0]=minCurrent;
    170.         while(maxCurrent.rightNode!=null){
    171.             maxCurrent = maxCurrent.rightNode;
    172.         }
    173.         minAndMaxVal[1]=maxCurrent;
    174.         return minAndMaxVal;
    175.     }
    176. }

    测试二叉查找树代码

    1. public static void main(String[] args) {
    2. 	// write your code here
    3.         BSTTree treeTest = new TreeTest();
    4.         treeTest.insert(3,3.03);
    5.         treeTest.insert(5,5.05);
    6.         treeTest.insert(1,1.01);
    7.         treeTest.insert(2,2.02);
    8.         treeTest.insert(4,4.04);
    9.         treeTest.insert(6,6.06);
    10.     	//查找节点3
    11.         BSTTree.Node node = treeTest.find(5);
    12.         if(node == null){
    13.             System.out.println("can not find it");
    14.         }else{
    15.             node.showNode();
    16.         }
    17.         BSTTree.Node[] temp = treeTest.mVal();
    18.         temp[0].showNode();
    19.         temp[1].showNode();
    20.     	//删除节点3
    21.         treeTest.delete(5);
    22.     	//再次查找
    23.         BSTTree.Node node1 = treeTest.find(5);
    24.         if(node1 == null){
    25.             System.out.println("can not find it");
    26.         }else{
    27.             node1.showNode();
    28.         }
    29.     }

    结果：

    三、完全二叉树

    叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

    性质：

    1、具有n个结点的完全二叉树的深度[log2n]+1

    2、如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) 有:

    • 如果i=1, 则结点i是二叉树的根, 无双亲;如果i>1, 则其双亲parent (i) 是结点[i/2].
    • 如果2i>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i;
    • 如果2i+1>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+1.

    判断一棵树是否是完全二叉树的思路

    1、如果树为空，则直接返回错

    2、如果树不为空：层序遍历二叉树

    2.1、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；

    2.1、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；

    2.2、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树；

    层次遍历代码(Java)---leetCode102:

    1. static class TreeNode{
    2.     int val;
    3.     TreeNode left;
    4.     TreeNode right;
    5.     TreeNode(){}
    6.     TreeNode(int val){
    7.         this.val = val;
    8.     }
    9.     TreeNode(int val,TreeNode left,TreeNode right){
    10.         this.val = val;
    11.         this.left = left;
    12.         this.right = right;
    13.     }
    14.     public void showNode(){
    15.         System.out.println("{"+val+":"+((left==null)?null:left.val)+":"+((right==null)?null:right.val)+"}");
    16.     }
    17. }
    18.  
    19. public static void main(String[] args) {
    20.     TreeNode tree1 = new TreeNode(9);
    21.     TreeNode tree2 = new TreeNode(15);
    22.     TreeNode tree3 = new TreeNode(7);
    23.     TreeNode tree4 = new TreeNode(20,tree2,tree3);
    24.     TreeNode tree5 = new TreeNode(3,tree1,tree4);
    25.     List> res = new ArrayList<>();
    26.     Queue queue = new LinkedList<>();
    27.     queue.add(tree5);
    28.     while (!queue.isEmpty()){
    29.         int count = queue.size();
    30.         List list = new ArrayList<>();
    31.         while (count > 0) {
    32.             TreeNode node = queue.poll();
    33.             list.add(node==null?null:node.val);
    34.             if(node!=null && node.left!=null){
    35.                 queue.add(node.left);
    36.             }
    37.             if(node!=null && node.right!=null){
    38.                 queue.add(node.right);
    39.             }
    40.             count--;
    41.         }
    42.         res.add(list);
    43.     }
    44.     for (List re : res) {
    45.         System.out.println(re);
    46.     }
    47. }

    四、平衡二叉树（AVL）

    性质：

    1、是二叉排序树

    2、每个节点的左子树和右子树的高度之差至多等于1，大于1则失衡，需要旋转纠正

    旋转：

    1、左旋

    • 旧根节点为新根节点的左子树
    • 新根节点的左子树为旧根节点的右子树

    2、右旋

    • 旧根节点为新根节点的右子树
    • 新根节点的右子树为旧根节点的左子树

    概念：

    平衡因子(BF)：节点的左子树高度减右子树高度

    最小不平衡子树：往平衡二叉树中插入新的节点，从插入点由下往上，依次遍历插入点的各个祖先节点，记录第一个遍历到的平衡因子的绝对值 |BF| >1的祖先节点，以该节点为根节点的子树，即为这棵树的最小不平衡子树。

    4 种「旋转」纠正类型（只需纠正最小不平衡子树即可，最小不平衡子树是距离插入节点最近的，并且BF的绝对值大于1的节点为根节点的子树）：

    1. LL 型(关注BF=2,BF=1)：插入左孩子的左子树，右旋（BF为平衡因子，即左子树高度减右子树高度）
    2. RR 型(关注BF=-2,BF=-1)：插入右孩子的右子树，左旋
    3. LR 型(关注BF=2,BF=-1)：插入左孩子的右子树，先左旋，再右旋
    4. RL 型(关注BF=-2,BF=1)：插入右孩子的左子树，先右旋，再左旋

    下图中，单个节点第一个值为节点数据，第二个是平衡因子BF

    第一种：右旋，2为新根节点，3为2的右子树

    第二种：先左旋，变为LL型（如下图），再右旋，2为新根节点，3为2的右子树

    第三种：左旋，2为新根节点，1为2的左子树

    第四种：先右旋，变成RR型（如下图），再左旋，2为新根节点，1为2的左子树

    插入步骤：

    1. 生成二叉查找树
    2. 计算平衡因子，判断是否需要调整，以及如何调整（需要调整的情况就是上面列的四种类型）

    删除规则：

    1. 删除节点为叶子节点时，更新该节点的父节点高度，以及往上所有父节点高度；
    2. 删除节点只有左子树或者右子树时，该删除节点下的左子树或右子树接上，并且更新原删除节点的父节点高度；
    3. 删除节点有左子树和右子树时，将该删除节点替换为删除节点的直接后继节点，并且回调本方法删除该后继节点；
    4. 删除后，需要从根节点往下，依次计算平衡因子，判断是否失衡，并调整

    例题：{3,2,1,4,5,6,7,10,9,8}构造平衡二叉树

    （以下只列了最难的一步转换，图中的节点，第一个数为保存的数据，第二个数为平衡因子）：

    节点8插入过程

     失衡，找到最小不平衡子树｛6,5,9,7,10,8｝，RL型（先右旋，再左旋），节点{6,9,7}右旋，7的右子树变为9的左子树如下图

    节点｛6,7,9｝左旋，节点6变为节点7的左子树，得到结果

     d43154d33ee3348ad51ea8ca72eda399.png

    JAVA实现平衡二叉树的插入、删除等等操作以及测试代码

    1. package com.examply;
    2.  
    3. import java.util.*;
    4.  
    5. /**
    6.  * @author :叙
    7.  */
    8. public class AVLtree {
    9.  
    10.     static class Tree {
    11.         int height;
    12.         Tree leftTree;
    13.         Tree rightTree;
    14.         Tree parent;
    15.         int data;
    16.         //无参构造方法
    17.         Tree() {
    18.         }
    19.  
    20.         Tree(int data) {
    21.             this.data = data;
    22.             //默认高度为1
    23.             this.height = 1;
    24.         }
    25.     }
    26.  
    27.     /**
    28.      * 计算平衡因子
    29.      *
    30.      * @param tree
    31.      * @return
    32.      */
    33.     public int countBF(Tree tree) {
    34.         if (tree == null || tree.leftTree == null && tree.rightTree == null) {
    35.             return 0;
    36.         }
    37.         if (tree.leftTree == null) {
    38.             return -tree.rightTree.height;
    39.         } else if (tree.rightTree == null) {
    40.             return tree.leftTree.height;
    41.         } else {
    42.             return tree.leftTree.height - tree.rightTree.height;
    43.         }
    44.     }
    45.  
    46.     /**
    47.      * 计算高度
    48.      *
    49.      * @param tree
    50.      */
    51.     public void countHeight(Tree tree) {
    52.         if (tree != null) {
    53.             if (tree.leftTree != null || tree.rightTree != null) {
    54.                 //左右子树最高的高度，加一为当前节点高度
    55.                 tree.height = Math.max(tree.rightTree == null ? 0 : tree.rightTree.height, tree.leftTree == null ? 0 : tree.leftTree.height) + 1;
    56.             } else {
    57.                 tree.height = 1;
    58.             }
    59.         }
    60.     }
    61.  
    62.     /**
    63.      * 右旋
    64.      * ● 旧根节点为新根节点的右子树
    65.      * ● 新根节点的右子树为旧根节点的左子树
    66.      *
    67.      * @param tree
    68.      */
    69.     public void rightRotate(Tree tree) {
    70.         Tree oldTree = tree;
    71.         Tree newTree = tree.leftTree;
    72.         Tree parent = tree.parent;
    73.         if (parent != null) {
    74.             //确定旧根节点在父类的位置，放入新根节点
    75.             if (oldTree.parent.data > oldTree.data) {
    76.                 parent.leftTree = newTree;
    77.             } else {
    78.                 parent.rightTree = newTree;
    79.             }
    80.         }
    81.         //修改新根节点的父节点为旧根节点的父节点
    82.         newTree.parent = parent;
    83.         //新根节点的右子树为旧根节点的左子树
    84.         oldTree.leftTree = newTree.rightTree;
    85.         if (newTree.rightTree!=null){
    86.             //新根节点的右子树的父节点为旧根节点
    87.             newTree.rightTree.parent = oldTree;
    88.         }
    89.         //新根节点的右子树为旧根节点
    90.         newTree.rightTree = oldTree;
    91.         //修改旧根节点的父节点为新根节点
    92.         oldTree.parent = newTree;
    93.         //修改高度
    94.         countHeight(oldTree);
    95.         countHeight(newTree);
    96.     }
    97.  
    98.     /**
    99.      * 左旋
    100.      * ● 旧根节点为新根节点的左子树
    101.      * ● 新根节点的左子树为旧根节点的右子树
    102.      *
    103.      * @param tree
    104.      */
    105.     public void leftRotate(Tree tree) {
    106.         Tree oldTree = tree;
    107.         Tree newTree = tree.rightTree;
    108.         Tree parent = tree.parent;
    109.         if (parent != null) {
    110.             //确定旧根节点在父类的位置，放入新根节点
    111.             if (oldTree.parent.data > oldTree.data) {
    112.                 parent.leftTree = newTree;
    113.             } else {
    114.                 parent.rightTree = newTree;
    115.             }
    116.         }
    117.         //修改新根节点的父节点为旧根节点的父节点
    118.         newTree.parent = parent;
    119.         //新根节点的左子树为旧根节点的右子树
    120.         oldTree.rightTree = newTree.leftTree;
    121.         if(newTree.leftTree!=null){
    122.             //新根节点的左子树的父节点为旧根节点
    123.             newTree.leftTree.parent = oldTree;
    124.         }
    125.         //修改新根节点的右子树的父节点为旧根节点
    126.         newTree.leftTree = oldTree;
    127.         //修改旧根节点的父节点为新根节点
    128.         oldTree.parent = newTree;
    129.         //修改高度
    130.         countHeight(oldTree);
    131.         countHeight(newTree);
    132.     }
    133.  
    134.     private Tree root;
    135.  
    136.     /**
    137.      * 插入节点（递归）
    138.      * @param root
    139.      * @param data
    140.      */
    141.     public void insert(Tree root, int data) {
    142.         //小于根节点，则插入到左边
    143.         if (data < root.data) {
    144.             if (root.leftTree != null) {
    145.                 insert(root.leftTree, data);
    146.             } else {
    147.                 root.leftTree = new Tree(data);
    148.                 root.leftTree.parent = root;
    149.             }
    150.         } else {
    151.             //大于根节点，则插入到右边
    152.             if (root.rightTree != null) {
    153.                 insert(root.rightTree, data);
    154.             } else {
    155.                 root.rightTree = new Tree(data);
    156.                 root.rightTree.parent = root;
    157.             }
    158.         }
    159.         //左子树高则右旋
    160.         if(countBF(root) == 2){
    161.             //左孩子节点的右子树高则先左旋
    162.             if(countBF(root.leftTree) == -1){
    163.                 leftRotate(root.leftTree);
    164.             }
    165.             rightRotate(root);
    166.         }
    167.         //右子树高则左旋
    168.         if(countBF(root) == -2){
    169.             //右孩子节点的左子树高则先右旋
    170.             if(countBF(root.rightTree) == 1){
    171.                 rightRotate(root.rightTree);
    172.             }
    173.             leftRotate(root);
    174.         }
    175.         //调整之后重新计算节点的高度
    176.         countHeight(root);
    177.     }
    178.  
    179.     /**
    180.      * 插入
    181.      * @param data
    182.      */
    183.     public Tree insert(int data){
    184.         //初始数据
    185.         if(root ==null){
    186.             root = new Tree(data);
    187.         }else{
    188.             //刷新root,使root始终为根节点
    189.             while(root.parent!=null){
    190.                 root = root.parent;
    191.             }
    192.             insert(root,data);
    193.         }
    194.         return root;
    195.     }
    196.  
    197.     /**
    198.      * 层次遍历树
    199.      * @param tree
    200.      */
    201.     public void showTree(Tree tree){
    202.         List> res = new ArrayList<>();
    203.         Queue queue = new LinkedList<>();
    204.         queue.add(tree);
    205.         while (!queue.isEmpty()){
    206.             int count = queue.size();
    207.             List list = new ArrayList<>();
    208.             while (count > 0) {
    209.                 Tree node = queue.poll();
    210.                 list.add("{当前节点："+node.data+"，父节点："+(node.parent==null?null:node.parent.data)+"}");
    211.                 if(node!=null && node.leftTree!=null){
    212.                     queue.add(node.leftTree);
    213.                 }
    214.                 if(node!=null && node.rightTree!=null){
    215.                     queue.add(node.rightTree);
    216.                 }
    217.                 count--;
    218.             }
    219.             res.add(list);
    220.         }
    221.         for (List re : res) {
    222.             System.out.println(re);
    223.         }
    224.     }
    225.  
    226.     /**
    227.      * 删除
    228.      * 1、删除节点为叶子节点时，更新该节点的父节点高度，以及往上所有父节点高度；
    229.      * 2、删除节点只有左子树或者右子树时，该删除节点下的左子树或右子树接上，并且更新原删除节点的父节点高度；
    230.      * 3、删除节点有左子树和右子树时，将该删除节点替换为删除节点的直接后继节点，并且回调本方法删除该后继节点；
    231.      * 4、删除后，需要从根节点往下，依次计算平衡因子，判断是否失衡，并调整
    232.      */
    233.     public Tree delete(Tree root,int key){
    234.         //找到需要删除的节点
    235.         Tree current = find(root,key);
    236.         Tree parent = current==null?null:current.parent;
    237.         if(current!=null){
    238.             //删除节点的左子树不为空
    239.             if(current.leftTree != null && current.rightTree != null){
    240.                 //查询待删除节点的直接后继节点
    241.                 Tree successorNode = getSuccessorNode(current);
    242.                 //保存节点数据，便于后面的替换
    243.                 int data = successorNode.data;
    244.                 //删除该后继节点
    245.                 delete(root,successorNode.data);
    246.                 //替换节点
    247.                 current.data = data;
    248.             }else if(current.leftTree != null || current.rightTree != null){
    249.                 //删除含有左子树或者右子树的节点,将删除节点的父节点直接连接删除节点的左子树或者右子树
    250.                 if(current.leftTree!=null){
    251.                     current.leftTree.parent = parent;
    252.                 }else{
    253.                     current.rightTree.parent = parent;
    254.                 }
    255.                 if(parent!=null){
    256.                     if(parent.data>current.data){
    257.                         parent.leftTree = current.leftTree != null?current.leftTree:current.rightTree;
    258.                     }else{
    259.                         parent.rightTree = current.leftTree != null?current.leftTree:current.rightTree;
    260.                     }
    261.                     //更新高度
    262.                     updateHeight(parent);
    263.                 }else{
    264.                     //删除节点为根节点，直接将根节点替换为下一个节点
    265.                     if(current.leftTree!=null){
    266.                         root = current.leftTree;
    267.                     }else{
    268.                         root = current.rightTree;
    269.                     }
    270.                 }
    271.             }else{
    272.                 //删除叶子节点
    273.                 if(parent==null){
    274.                     //根节点，直接将树置空
    275.                     root = null;
    276.                 }else{
    277.                     //删除叶子节点,直接置空
    278.                     if(parent.data>current.data){
    279.                         parent.leftTree = null;
    280.                     }else{
    281.                         parent.rightTree = null;
    282.                     }
    283.                     //更新高度
    284.                     updateHeight(parent);
    285.                 }
    286.             }
    287.             return update(root,key);
    288.         }
    289.         return null;
    290.     }
    291.  
    292.     /**
    293.      * 从tree节点开始，一直往上更新节点高度
    294.      * @param tree
    295.      */
    296.     public void updateHeight(Tree tree){
    297.         Tree parent = tree;
    298.         while(parent!=null){
    299.             //修改父节点高度
    300.             countHeight(parent);
    301.             parent = parent.parent;
    302.         }
    303.     }
    304.  
    305.     /**
    306.      * 查找节点
    307.      * @param root
    308.      * @param key
    309.      * @return
    310.      */
    311.     public Tree find(Tree root,int key){
    312.         if(root == null){
    313.             return null;
    314.         }
    315.         Tree current = root;
    316.         while(current.data!=key){
    317.             if(current.data>key){
    318.                 current = current.leftTree;
    319.             }else{
    320.                 current = current.rightTree;
    321.             }
    322.             if(current==null){
    323.                 break;
    324.             }
    325.         }
    326.         return current;
    327.     }
    328.  
    329.     /**
    330.      * 获取tree的后继节点
    331.      * @param tree
    332.      * @return
    333.      */
    334.     public Tree getSuccessorNode(Tree tree){
    335.         Tree current = tree==null?null:tree.rightTree;
    336.         if(current==null){
    337.             return null;
    338.         }
    339.         while(current.leftTree != null){
    340.             current = current.leftTree;
    341.         }
    342.         return current;
    343.     }
    344.  
    345.     /**
    346.      * 递归调整二叉树
    347.      * @param root
    348.      * @param key
    349.      */
    350.     public void updateTree(Tree root,int key){
    351.         Tree current = root;
    352.         //左子树高则右旋
    353.         if(countBF(current) == 2){
    354.             //左孩子节点的右子树高则先左旋
    355.             if(countBF(current.leftTree) == -1){
    356.                 leftRotate(current.leftTree);
    357.             }
    358.             rightRotate(current);
    359.         }
    360.         //右子树高则左旋
    361.         if(countBF(current) == -2){
    362.             //右孩子节点的左子树高则先右旋
    363.             if(countBF(current.rightTree) == 1){
    364.                 rightRotate(current.rightTree);
    365.             }
    366.             leftRotate(current);
    367.         }
    368.         //调整之后重新计算节点的高度
    369.         countHeight(root);
    370.         if(key
    371.             if(current.leftTree == null){
    372.  
    373.             }else{
    374.                 updateTree(current.leftTree,key);
    375.             }
    376.         }else{
    377.             if(current.rightTree == null){
    378.  
    379.             }else{
    380.                 updateTree(current.rightTree,key);
    381.             }
    382.         }
    383.     }
    384.  
    385.     /**
    386.      * 调整二叉树为平衡二叉树
    387.      * @param tree
    388.      * @param data 删除节点
    389.      * @return
    390.      */
    391.     public Tree update(Tree tree,int data){
    392.         //初始数据
    393.         if(tree ==null){
    394.             tree = new Tree(data);
    395.         }else{
    396.             //刷新tree,使tree始终为根节点
    397.             while(tree.parent!=null){
    398.                 tree = tree.parent;
    399.             }
    400.             updateTree(tree,data);
    401.         }
    402.         //刷新tree，使tree为根节点
    403.         while(tree.parent!=null){
    404.             tree = tree.parent;
    405.         }
    406.         return tree;
    407.     }
    408.  
    409.     /**
    410.      * 测试
    411.      * @param args
    412.      */
    413.     public static void main(String[] args) {
    414.         AVLtree avLtree = new AVLtree();
    415.         avLtree.insert(3);
    416.         avLtree.insert(2);
    417.         avLtree.insert(1);
    418.         avLtree.insert(4);
    419.         avLtree.insert(5);
    420.         avLtree.insert(6);
    421.         avLtree.insert(7);
    422.         avLtree.insert(10);
    423.         avLtree.insert(9);
    424.         Tree tree = avLtree.insert(8);
    425.         avLtree.showTree(tree);
    426.         System.out.println("-----------------");
    427.         Tree tree5 = avLtree.delete(tree,5);
    428.         avLtree.showTree(tree5);
    429.         System.out.println("-----------------");
    430.         Tree tree6 = avLtree.delete(tree,6);
    431.         avLtree.showTree(tree6);
    432.     }
    433.  
    434. }

    结果：

    五、红黑树(R-B Tree)

    介绍：

    红黑树，其节点分为两类，一类被标记为红色，另一类被标记为黑色；红黑树是一棵不完整的平衡二叉查找树树，

    性质：

    • 根节点是黑色
    • 叶子节点不存储数据，并且是黑色
    • 任何相邻的节点不能同时为红色，必须使用黑色节点隔开
    • 对于单个节点，该节点到叶子节点的所有路径中都包含相同数目的黑色节点

    旋转：

    • 左旋
      • 旧根节点的右子树为新根节点的左子树
      • 新根节点的左子树为旧根节点
      • 交换新根节点和旧根节点的颜色，新黑旧红
    • 右旋
      • 旧根节点的左子树为新根节点的右子树
      • 新根节点的右子树为旧根节点
      • 交换新根节点和旧根节点的颜色，新黑旧红

    红黑树的插入步骤：

    1. 生成二叉查找树
    2. 令插入点为红色
    3. 判断是否需要旋转调整，以及如何调整

    判断情况如下：

    情况一：插入点为根节点，违反了性质1，直接令其为黑色

    情况二：插入点的父节点为红色，违反了性质3，需要进行调整

    父节点为红色的情况需要再细分为以下几种：

    父节点为红色，父节点的兄弟节点为黑色，插入点位于父节点的左子树，如下图，需要先右旋，然后左旋，并交换祖父节点和插入节点的颜色

     父节点为红色，父节点的兄弟节点为黑色，插入点位于父节点的右子树，如下图，需要先左旋，然后右旋，并交换祖父节点和插入节点的颜色

     父节点为红色，父节点的兄弟节点也为红色，如下图，需要把父节点和父节点的兄弟节点全变为黑色，并将祖父节点变为红色，再将祖父节点当作插入点，递归重复判断是否需要调整（PS：若最后把根节点变成了红色，直接将根节点改成黑色即可，如下图第三张）

     例子：假设需要顺序插入{2,4,3,5,6,8,7,9}，生成一棵红黑树，以下列出了推导过程图。

     红黑树插入实现(Java)

    1. package com.examply;
    2.  
    3. import java.util.*;
    4.  
    5. /**
    6.  * 红黑树
    7.  */
    8. public class RBTree {
    9.  
    10.     static class RBNode{
    11.         int data;
    12.         RBNode leftNode;
    13.         RBNode rightNode;
    14.         RBNode parent;
    15.         int color;//颜色，0红色1黑色
    16.         //无参构造方法
    17.         RBNode() {
    18.         }
    19.  
    20.         RBNode(int data) {
    21.             this.data = data;
    22.             //默认颜色为红色
    23.             this.color = 0;
    24.         }
    25.     }
    26.  
    27.     //红色
    28.     private static final int RED_NODE = 0;
    29.     //黑色
    30.     private static final int BLACK_NODE = 1;
    31.  
    32.     /**
    33.      * 左旋
    34.      * @param node
    35.      */
    36.     public void leftRotate(RBNode node){
    37.         if(node==null){
    38.             return;
    39.         }
    40.         RBNode oldNode = node.parent;
    41.         RBNode parent = oldNode.parent;
    42.         RBNode newNode = node;
    43.         //新根节点的父节点为旧根节点的父节点
    44.         newNode.parent = parent;
    45.         if(parent!=null){
    46.             if(parent.data
    47.                 parent.rightNode = newNode;
    48.             }else{
    49.                 parent.leftNode = newNode;
    50.             }
    51.         }
    52.         if(newNode.leftNode!=null){
    53.             //新根节点的左子树的父节点为旧根节点
    54.             newNode.leftNode.parent = oldNode;
    55.         }
    56.         //旧根节点的右子树为新根节点的左子树
    57.         oldNode.rightNode = newNode.leftNode;
    58.         //新根节点的左子树为旧根节点
    59.         newNode.leftNode = oldNode;
    60.         //旧根节点的父节点为新根节点
    61.         oldNode.parent = newNode;
    62.     }
    63.  
    64.     /**
    65.      * 右旋
    66.      * @param node
    67.      */
    68.     public void rightRotate(RBNode node){
    69.         if(node==null){
    70.             return;
    71.         }
    72.         RBNode oldNode = node.parent;
    73.         RBNode parent = oldNode.parent;
    74.         RBNode newNode = node;
    75.         //新根节点的父节点为旧根节点的父节点
    76.         newNode.parent = parent;
    77.         if(parent!=null){
    78.             if(parent.data
    79.                 parent.rightNode = newNode;
    80.             }else{
    81.                 parent.leftNode = newNode;
    82.             }
    83.         }
    84.         if(newNode.rightNode!=null){
    85.             //新根节点的右子树的父节点为旧根节点
    86.             newNode.rightNode.parent = oldNode;
    87.         }
    88.         //旧根节点的左子树为新根节点的右子树
    89.         oldNode.leftNode = newNode.rightNode;
    90.         //新根节点的右子树为旧根节点
    91.         newNode.rightNode = oldNode;
    92.         //旧根节点的父节点为新根节点
    93.         oldNode.parent = newNode;
    94.     }
    95.  
    96.     /**
    97.      * 插入数据
    98.      * @param root
    99.      * @param data
    100.      */
    101.     public void insert(RBNode root,int data){
    102.         if(root==null){
    103.             return;
    104.         }
    105.         RBNode current = root;
    106.         //插入数据
    107.         if(root.data>data){
    108.             if(root.leftNode!=null){
    109.                 current = root.leftNode;
    110.                 insert(current,data);
    111.                 return;
    112.             }else{
    113.                 root.leftNode = new RBNode(data);
    114.                 root.leftNode.parent = root;
    115.                 current = root.leftNode;
    116.             }
    117.         }else{
    118.             if(root.rightNode!=null){
    119.                 current = root.rightNode;
    120.                 insert(current,data);
    121.                 return;
    122.             }else{
    123.                 root.rightNode = new RBNode(data);
    124.                 root.rightNode.parent = root;
    125.                 current = root.rightNode;
    126.             }
    127.         }
    128.         fixRBTree(current);
    129.     }
    130.  
    131.     /**
    132.      * 调整红黑树
    133.      * @param current
    134.      */
    135.     public void fixRBTree(RBNode current){
    136.         //根节点，直接变黑色
    137.         if(current.parent==null){
    138.             current.color = BLACK_NODE;
    139.         }else{
    140.             RBNode parent = current.parent;
    141.             //判断父节点为红色
    142.             if(parent.color == RED_NODE){
    143.                 //判断插入点位于左子树还是右子树
    144.                 if(current.data>parent.data){
    145.                     //判断父节点的兄弟节点位置
    146.                     if(parent.parent.data
    147.                         //RR型
    148.                         //判断父节点的兄弟节点是否为红色
    149.                         if(parent.parent.leftNode!=null && parent.parent.leftNode.color==RED_NODE){
    150.                             //令父节点的兄弟节点为黑色
    151.                             parent.parent.leftNode.color = BLACK_NODE;
    152.                             //令父节点为黑色
    153.                             parent.color = BLACK_NODE;
    154.                             //令祖父节点为红色
    155.                             parent.parent.color = RED_NODE;
    156.                             //递归祖父节点
    157.                             fixRBTree(parent.parent);
    158.                         }else{
    159.                             //左旋
    160.                             leftRotate(current.parent);
    161.                             //新根节点为黑色
    162.                             current.parent.color = BLACK_NODE;
    163.                             //旧根节点为红色
    164.                             if(current.parent.leftNode!=null){
    165.                                 current.parent.leftNode.color = RED_NODE;
    166.                             }
    167.                         }
    168.                     }else{
    169.                         //LR型
    170.                         if(parent.parent.rightNode!=null && parent.parent.rightNode.color==RED_NODE){
    171.                             //令父节点的兄弟节点为黑色
    172.                             parent.parent.rightNode.color = BLACK_NODE;
    173.                             //令父节点为黑色
    174.                             parent.color = BLACK_NODE;
    175.                             //令祖父节点为红色
    176.                             parent.parent.color = RED_NODE;
    177.                             //递归祖父节点
    178.                             fixRBTree(parent.parent);
    179.                         }else{
    180.                             //左旋
    181.                             leftRotate(current);
    182.                             //右旋
    183.                             rightRotate(current);
    184.                             //新根节点为黑色
    185.                             current.color = BLACK_NODE;
    186.                             //旧根节点为红色
    187.                             current.rightNode.color = RED_NODE;
    188.                         }
    189.                     }
    190.                 }else{
    191.                     //RL型
    192.                     if(parent.parent.data
    193.                         if(parent.parent.leftNode!=null && parent.parent.leftNode.color==RED_NODE){
    194.                             //令父节点的兄弟节点为黑色
    195.                             parent.parent.leftNode.color = BLACK_NODE;
    196.                             //令父节点为黑色
    197.                             parent.color = BLACK_NODE;
    198.                             //令祖父节点为红色
    199.                             parent.parent.color = RED_NODE;
    200.                             //递归祖父节点
    201.                             fixRBTree(parent.parent);
    202.                         }else{
    203.                             //右旋
    204.                             rightRotate(current);
    205.                             //左旋
    206.                             leftRotate(current);
    207.                             //新根节点为黑色
    208.                             current.color = BLACK_NODE;
    209.                             //旧根节点为红色
    210.                             current.leftNode.color = RED_NODE;
    211.                         }
    212.                     }else{
    213.                         //LL型
    214.                         if(parent.parent.rightNode!=null && parent.parent.rightNode.color==RED_NODE){
    215.                             //令父节点的兄弟节点为黑色
    216.                             parent.parent.rightNode.color = BLACK_NODE;
    217.                             //令父节点为黑色
    218.                             parent.color = BLACK_NODE;
    219.                             //令祖父节点为红色
    220.                             parent.parent.color = RED_NODE;
    221.                             //递归祖父节点
    222.                             fixRBTree(parent.parent);
    223.                         }else{
    224.                             //右旋
    225.                             rightRotate(current.parent);
    226.                             //新根节点为黑色
    227.                             current.parent.color = BLACK_NODE;
    228.                             //旧根节点为红色
    229.                             current.parent.rightNode.color = RED_NODE;
    230.                         }
    231.                     }
    232.                 }
    233.             }
    234.         }
    235.     }
    236.  
    237.     private RBNode root;
    238.  
    239.     public RBNode insert(int data){
    240.         //初始数据
    241.         if(root ==null){
    242.             root = new RBNode(data);
    243.             root.color = BLACK_NODE;
    244.         }else{
    245.             //刷新root,使root始终为根节点
    246.             while(root.parent!=null){
    247.                 root = root.parent;
    248.             }
    249.             insert(root,data);
    250.         }
    251.         return root;
    252.     }
    253.  
    254.     /**
    255.      * 层次遍历树
    256.      * @param tree
    257.      */
    258.     public void showTree(RBNode tree){
    259.         //使tree指向根节点
    260.         while(tree.parent!=null){
    261.             tree = tree.parent;
    262.         }
    263.         List> res = new ArrayList<>();
    264.         Queue queue = new LinkedList<>();
    265.         queue.add(tree);
    266.         while (!queue.isEmpty()){
    267.             int count = queue.size();
    268.             List list = new ArrayList<>();
    269.             while (count > 0) {
    270.                 RBNode node = queue.poll();
    271.                 list.add("{当前节点："+node.data+"颜色为："+(node.color==0?"红色":"黑色")+"，父节点："+(node.parent==null?null:node.parent.data)+"}");
    272.                 if(node!=null && node.leftNode!=null){
    273.                     queue.add(node.leftNode);
    274.                 }
    275.                 if(node!=null && node.rightNode!=null){
    276.                     queue.add(node.rightNode);
    277.                 }
    278.                 count--;
    279.             }
    280.             res.add(list);
    281.         }
    282.         for (List re : res) {
    283.             System.out.println(re);
    284.         }
    285.     }
    286.  
    287.     public static void main(String[] args) {
    288.         RBTree tree = new RBTree();
    289.         tree.insert(2);
    290.         tree.insert(4);
    291.         tree.insert(3);
    292.         tree.insert(5);
    293.         tree.insert(6);
    294.         tree.insert(8);
    295.         tree.insert(7);
    296.         RBNode root = tree.insert(9);
    297.         tree.showTree(root);
    298.     }
    299.  
    300. }

     结果：

     以上就是全部内容，不足之处，请多指教

  • 相关阅读:
    【Harmony OS】【ArkUI】ets开发 创建视图与构建布局
    【SpringCloud】Nacos的安装、Nacos注册、Nacos服务多级存储模型
    vr展厅开发流程
    Android Startup启动优化
    为什么国外程序员的创造力比中国程序员强？
    【JavaEE进阶系列 | 从小白到工程师】正则表达式的语法&使用
    【无标题】H5页面解决点击页面处关闭键盘，触发了页面的事件的问题
    CentOS Linux 系统镜像
    stable-diffusion 电商领域prompt测评集合
    pip install paramiko出错的解决方案
  • 原文地址：https://blog.csdn.net/qq_49721447/article/details/127403465