← 返回学习路线

SYSTEM

排序树

Java基础排序树system
src/content/notes/system/排序树.md

排序树

存储结构

二叉排序树(BST),又称二叉查找树或者二叉搜索树

  • 每一个节点上最多有两个子节点
  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值
  • 不存在重复的节点
二叉查找树

代码实现

  • 节点类:

    private static class TreeNode {
        int key;
        TreeNode left;  //左节点
        TreeNode right; //右节点
    
        private TreeNode(int key) {
            this.key = key;
        }
    }
  • 查找节点:

     // 递归查找
    private static TreeNode search(TreeNode root, int key) {
        //递归结束的条件
        if (root == null) {
            return null;
        }
        if (key == root.key) {
            return root;
        } else if (key > root.key) {
            return search(root.right, key);
        } else {
            return search(root.left, key);
        }
    }
    
    // 非递归
    private static TreeNode search1(TreeNode root, int key) {
        while (root != null) {
            if (key == root.key) {
                return root;
            } else if (key > root.key) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        return null;
    }
  • 插入节点:

    private static int insert(TreeNode root, int key) {
        if (root == null) {
            root = new TreeNode(key);
            root.left = null;
            root.right = null;
            return 1;
        } else {
            if (key == root.key) {
                return 0;
            } else if (key > root.key) {
                return insert(root.right, key);
            } else {
                return insert(root.left, key);
            }
        }
    }
  • 构造函数:

    // 构造函数,返回根节点
    private static TreeNode createBST(int[] arr) {
        if (arr.length > 0) {
            TreeNode root = new TreeNode(arr[0]);
            for (int i = 1; i < arr.length; i++) {
                insert(root, arr[i]);
            }
            return root;
        }
        return null;
    }
  • 删除节点:要删除节点12,先找到节点19,然后移动并替换节点12

    代码链接:https://leetcode-cn.com/submissions/detail/190232548/

参考视频:https://www.bilibili.com/video/BV1iJ411E7xW?t=756&p=86

图片来源:https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/tu-jie-yi-dong-jie-dian-er-bu-shi-xiu-ga-edtn/


平衡树

平衡二叉树(AVL)的特点:

  • 二叉树左右两个子树的高度差不超过 1
  • 任意节点的左右两个子树都是一颗平衡二叉树

平衡二叉树旋转:

  • 旋转触发时机:当添加一个节点之后,该树不再是一颗平衡二叉树

  • 平衡二叉树和二叉查找树对比结构图

平衡二叉树和二叉查找树对比

  • 左旋:将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点

    平衡二叉树左旋

  • 右旋:将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点

    平衡二叉树右旋

推荐文章:https://pdai.tech/md/algorithm/alg-basic-tree-balance.html