【数据结构】二叉搜索树_二叉搜索树的构造

数据结构系列五：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.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.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; } } }

二、搜索性能

1.排成完全二叉树

以左右均匀分配地 有序排 建成的搜索树，每次的分查 都能排掉区域一半的数据，搜索性能高，当分配均匀成 完全二叉树时，搜索的次数为 树的高度log(n) 就能查到数据

2.排成链表

以单分支分配地 有序排成的搜索树 退化成链表，每次的分查 都不能排额外数据，搜索性能低下，搜索的次数为 树的高度 为链表的长度n