【数据结构】二叉搜索树

数据结构系列五：Map与Set(三)

二叉搜索树

一、搜索原理（有序维护）

1.插入

2.删除

2.1单子树节点

2.2双子树节点

二、搜索性能

1.排成完全二叉树

2.排成链表

二叉搜索树

每个节点都经过整体搜索比较排维护组成的有序树是二叉排序树，即二叉搜索树

一、搜索原理（有序维护）

依据维护成的整体有序性左右分位判相对位置对整体搜完来确定序位，进而持续维护有序树的整体有序性，具体要求在：

1.插入

插入元素时，要搜索确定完在路径下的所有节点的相对位置后再插入，才可确保插入在整体下的有序维护性，所以所有的元素插入都是插到路径末整体树的子叶节点空位置进行的

插入代码

    public boolean insert(int val) {TreeNode node = new TreeNode(val);if(root == null) {root = node;return true;}TreeNode cur = root;TreeNode parent = null;//搜索到 路径末叶节点 空位置上 插入，确保能维护 元素插入的整体有序while (cur != null) {if(cur.val <val) {parent = cur;cur = cur.right;}else if(cur.val > val) {parent = cur;cur = cur.left;}else {return false;}}if(parent.val < val) {parent.right = node;}else {parent.left = node;}return true;}

2.删除

删除节点，要维护节点删完后节点的子树在整体里能重新有序性：

2.1单子树节点

如果删除节点只有一棵子树，直接绕删此节点连其子树，删除后是维护着子树进整体重新有序的

2.2双子树节点

如果删除节点有两棵子树，找到子树中的最上最端的最值单子树节点，(左子树最右端最大，右子树最左端最小）用子树的最值往上覆盖掉以删掉节点值，接着用单子树直接绕删的方式删此已重复值的单子树节点 完成节点删除后两子树重新能融整体有序维护的删除

删除代码

    public void remove(int val) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val <val) {parent = cur;cur = cur.right;}else if(cur.val > val) {parent = cur;cur = cur.left;}else {//删除的逻辑removeNode(parent,cur);return;}}}private void removeNode(TreeNode parent,TreeNode cur) {//本质 ——> 单子树节点的删除，直接 绕删转去连 它的那棵单子树就行了//处理本质 绕删连都是相同的，但在具体操作时 面对的情况上 有点不同，要分着处理//1.删除单子树节点//1.1要删的单子树节点 左边没有树if(cur.left == null) {//1.1.1要删除的单子树节点 没有父母parent==null，在操作上有点不同，父节点空情况要防空 分开来处理操作if(cur == root) {root = cur.right;//1.1.2要删除的单子树节点 有父母 在父节点左边，要用父节点的左边去绕连}else if(cur == parent.left) {parent.left = cur.right;//1.1.3要删除的单子树节点 有父母 在父节点右边，要用父节点的右边去绕连}else {parent.right = cur.right;}//1.2要删的单子树节点 右边没有树}else if(cur.right == null) {//1.2.1要删除的单子树节点 没有父节点，父节点空情况 分着处理它if(cur == root) {root = cur.left;//1.2.2要删除的单子树节点 在父节点左边，要用父节点左边去绕连}else if(cur == parent.left) {parent.left = cur.left;//1.2.3要删处的单子树节点 在父节点右边，要用父节点右边去绕连}else {parent.right = cur.left;}//其实往一边找替罪羊去删的删法 也同样适用于 单子树节点的删除，往对应节点 对应的单子树那边 找替罪羊去删 同样也能完成，不过这里选择将它们分开来处理了//2.删除双子树节点}else {//统一用 往右子树找替罪羊的删法:TreeNode targetParent = cur;TreeNode target = cur.right;//2.1target.left==null，找到替罪羊while (target.left != null) {targetParent = target;target = target.left;}//2.2最值往上覆盖删掉 要删除节点的值:cur.val = target.val;//2.3把替罪羊节点删除://2.3.1如果替罪羊一上来 就直接在 要删除节点的右首节点，分成的情况就是 替罪羊节点在其父节点的右边的情况，要用父节点的右边去绕连删if(target == targetParent.right) {targetParent.right = target.right;}else {//2.3.2替罪羊在要删除节点 首个右节点之后的，分成的情况就是 替罪羊在其父节点的左边 的一般情况，要用父节点的左边去绕连删targetParent.left = target.right;}}}