数据结构 (一), BST 二叉搜索树，高级程序员面试题

if (root.data == num) {return root;} else if (root.data > num) {return doSearch(root.left

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

, num);} else if (root.data < num) {return doSearch(root.right, num);}return null;}

2. 插入

• 比对根节点, 小于就往左节点比对, 大于就往右节点比对

• 直到需要比对的节点为空, 而这个空就是你需要插入的位置

算法时间复杂度:

• 最优 f(n) = 需要比对的次数 = 二叉树的层数 ~= O(logn)

• 最差 f(n) = 需要查找的次数 = 二叉树的层数 = n = O(n)

public void insert(int num) {root = doInsert(root, num);}

private Node doInsert(Node parent, int num) {if (parent == null) {parent = new Node(num);} else if (num > parent.data) {parent.right = doInsert(parent.right, num);} else if (num < parent.data) {parent.left = doInsert(parent.left, num);}

return parent;}

3. 删除

• 先查找到目标节点

• 若: 目标左子树为空, 则, 用目标右子树根节点替换目标

• 若: 目标右子树为空, 则, 用目标左子树根节点替换目标

• 若: 都不为空, 则, 选取左子树值最大节点或者右子树最小节点替换目标, 并, 递归删除替换目标的节点

public void remove(int num) {root = doRemove(root, num);}

private Node doRemove(Node parent, int num) {

if (parent == null) {return null;}

if (num > parent.data) {parent.right = doRemove(parent.right, num);} else if (num < parent.data) {parent.left = doRemove(parent.left, num);}// 找出左子树最大的值或者右子树最小的值替换, 这里选择前者来实现 else if (parent.left != null && parent.right != null) {

// 找到左子树最大值替换 parent.data = findMax(parent.left).data;// 删除左子树中用于替换的节点 parent.left = doRemove(parent.left, parent.data);}// 左子树为空, 直接用右子树根节点替换被删除的节点 else if (parent.left == null) {parent = parent.right;}// 右子树为空, 直接用左子树根节点替换被删除的节点 else if (parent.right == null) {parent = parent.left;}

return parent;}

private Node findMax(Node node) {if (node == null) {return node;}while (node.right != null) {node = node.right;}return node;}算法复杂度:

• 最优 f(n) = 需要比对的次数 = 查找到目标比对次数 + 递归查找替换目标的节点的替换节点的比对次数 = 二叉树层数 = O(logn)

• 

• 最差 f(n) = ... = 二叉树层数 = n = O(n)