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://www.bilibili.com/video/BV1iJ411E7xW?t=756&p=86
平衡树
平衡二叉树(AVL)的特点:
- 二叉树左右两个子树的高度差不超过 1
- 任意节点的左右两个子树都是一颗平衡二叉树
平衡二叉树旋转:
-
旋转触发时机:当添加一个节点之后,该树不再是一颗平衡二叉树
-
平衡二叉树和二叉查找树对比结构图

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

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

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