币圈印象
二叉查找树的解读和实现
作者：ytao
https://ytao.top/2019/11/03/5_bst/
二叉查找树是将一组无序的数据构建成一颗有序数据的树，其设计思想与二分法类似。很好的提高了海量数据查找效率，使得由从头遍历到尾的方式转为二分查找的方式，时间复杂度从 O(n) 降低为 O(log(n))。
概念
-
结点：树上的每个元素。
-
根结点：没有父结点的结点。
-
父结点：结点的上一级结点。
-
子结点：结点的下一级结点。
-
叶子结点：没有子结点的结点。
-
兄弟结点：拥有同一父结点的相邻结点。
-
结点的度：一个结点中拥有子结点的个数。
-
树的度：树上最大结点的度。
-
结点的层次：以根结点为 1，每深入一个子结点层次加 1。
-
树的高度：树中最大的结点的层次。
特性
-
左子树所有的结点值均小于，等于根结点值或为空。
-
右子树所有的结点值均大于，等于根结点值或为空。
-
左、右子树也分别为二叉排序树。
-
没有键值相等的结点。
构建
构建二叉查找树，主要把握几条原则，小于当前结点的在左边，大于的在右边，相等的不予处理。但是情况下结合实际业务需求，也可在相等时放在左结点或右结点，但是必须统一规则，不能左右都存在相等的。创建结点对象：
[code] 1. package com.ytao.bst;
2. 3. /** 4. * Created by YANGTAO on 2019/11/3 0003. 5. */ 6. public class Node { 7. 8. private Integer value; 9. 10. private Node leftChildren; 11. 12. private Node rightChildren; 13. 14. public Integer getValue() { 15. return value; 16. } 17. 18. public void setValue(Integer value) { 19. this.value = value; 20. } 21. 22. public Node getLeftChildren() { 23. return leftChildren; 24. } 25. 26. public void setLeftChildren(Node leftChildren) { 27. this.leftChildren = leftChildren; 28. } 29. 30. public Node getRightChildren() { 31. return rightChildren; 32. } 33. 34. public void setRightChildren(Node rightChildren) { 35. this.rightChildren = rightChildren; 36. } 37. 38. public Node(Integer value) { 39. this.value = value; 40. } 41. }
[/code]
创建树的实现：
[code] 1. package com.ytao.bst;
2. 3. /** 4. * Created by YANGTAO on 2019/11/3 0003. 5. */ 6. public class BuildBST { 7. 8. private Node rootNode = null; 9. 10. public Node build(int[] vals){ 11. // 遍历所有数据，每次都需从根结点开始寻找左或右子节点为空的位置添加 12. for (int val : vals) { 13. this.assemble(rootNode, val); 14. } 15. 16. return rootNode; 17. } 18. 19. private void assemble(Node node, int val){ 20. // 创建根结点 21. if (node == null){ 22. rootNode = new Node(val); 23. }else{ 24. // 根据左小右大特性判断 25. if (val < node.getValue()){ 26. Node leftNode = node.getLeftChildren(); 27. // 如果左子结点为空，就添加为当前结点的左结点，否则继续递归下去 28. if (leftNode == null){ 29. node.setLeftChildren(new Node(val)); 30. }else{ 31. this.assemble(node.getLeftChildren(), val); 32. } 33. }else{ 34. Node rightNode = node.getRightChildren(); 35. // 如果右子结点为空，就添加为当前结点的右结点，否则继续递归下去 36. if (rightNode == null){ 37. node.setRightChildren(new Node(val)); 38. }else{ 39. this.assemble(rightNode, val); 40. } 41. } 42. 43. } 44. 45. } 46. 47. }
[/code]
使用 [7,5,9,2,11,6] 测试是否满足我们创建树的要求：
[code] 1. public static void main(String[] args) {
2. int[] vals = {7,5,9,2,11,6}; 3. Node node = new BuildBST().build(vals); 4. System.out.println(new Gson().toJson(node)); 5. }
[/code]
测试结果满足我们要求
[code] 1. {
2. "value": 7, 3. "leftChildren": { 4. "value": 5, 5. "leftChildren": { 6. "value": 2 7. }, 8. "rightChildren": { 9. "value": 6 10. } 11. }, 12. "rightChildren": { 13. "value": 9, 14. "rightChildren": { 15. "value": 11 16. } 17. } 18. }
[/code]
查找
假设从一百万个数字中获取值为 88 的数据，如果我们使用遍历的方式，最糟的情况就是排在第一百万个位置的时候，需要我们遍历一百万次才能获取到数据，这就是我们最不想遇到的情况。这时将一百万个数据构建成二叉查找树，我们就可通过树快速找到我们想要的数据。由于设定一百万个数据比较多，这里我们举例当前拥有数据 [7,5,9,2,11,6], 我们要找出其中的 6。使用循环遍历所有数据的方法，我们需要 6 次遍历 7->5->9->2->11->6。使用二叉查找树查找时，首先构建好的二叉查找树的结构如图：
从根结点开始查找；
获取根结点 7，不等于 6，且 6<7，所以继续找左子结点；
获取到结点 5，不等于 6，且 6>5，所以继续找右子节点；
最终获取到结点 6，满足我们需要的条件。所遍历的数据为 7->5->6。代码实现查找：
[code] 1. package com.ytao.bst;
2. 3. /** 4. * Created by YANGTAO on 2019/11/3 0003. 5. */ 6. public class SearchBST { 7. 8. public Node search(Node node, int val){ 9. // 如果结点为空，说明是没有了符合的结点 10. if (node == null) 11. return null; 12. 13. int nodeVal = node.getValue(); 14. 15. // 如果结点上的键值相等，就是我们需要找的结点 16. if (val == nodeVal){ 17. return node; 18. }else if (val < nodeVal){ // 如果小于结点的值，那么一定在结点的左子树中 19. return this.search(node.getLeftChildren(), val); 20. }else{ 21. return this.search(node.getRightChildren(), val); 22. } 23. 24. } 25. 26. 27. }
[/code]
插入
二叉查找树的插入规则，必须是要插入后的结点是作为叶子结点。现在向上面的树中插入 10，根据上面所分析到的规则，为确保二叉查找树的完整性，最终的插入流程为 7->9->11->10：
代码实现：
[code] 1. package com.ytao.bst;
2. 3. /** 4. * Created by YANGTAO on 2019/11/3 0003. 5. */ 6. public class InsertBST { 7. 8. public void inesrt(Node node, int newVal){ 9. // 当结点为空是，说明是作为根结点 10. if (node == null){ 11. node = new Node(newVal); 12. } 13. 14. int nodeVal = node.getValue(); 15. 16. // 如果小于结点的值，插入到左子树中，大于就插入右子树中 17. if (newVal < nodeVal){ 18. Node leftNode = node.getLeftChildren(); 19. // 为空时，说明为叶子结点，可插入 20. if (leftNode == null){ 21. node.setLeftChildren(new Node(newVal)); 22. }else { 23. this.inesrt(leftNode, newVal); 24. } 25. }else if (newVal > nodeVal){ 26. Node rightNode = node.getRightChildren(); 27. if (rightNode == null){ 28. node.setRightChildren(new Node(newVal)); 29. }else { 30. this.inesrt(rightNode, newVal); 31. } 32. }else { 33. // todo 相等时，可根据具体业务处理，放弃，或在左右树中选择一个 34. } 35. 36. } 37. 38. }
[/code]
删除
删除结点分为多种情况，其中主要分析的：
叶子结点
删除叶子结点，将所要删除的叶子结点直接删除便可，比如删除结点 6。
单子结点的结点
被删除结点，如果只有一个子结点，那么被删除结点删除后，该结点的子结点补上其位置，比如删除结点 9。
存在左右子结点的结点
为了更加清楚表达删除存在左右结点的结点，先向树中多添加 3 个结点 8，10，15。然后删除结点 9。这里的解决方法就是，删除 9 后，可以用前驱结点或后继结点补上。前驱结点为左子树中最大的结点，后继结点为右子树中最小的结点。现在以后继结点补上的方案为：
后继结点补上删除后的结点：
完成删除，后继结点补充上后：
代码实现：
[code] 1. package com.ytao.bst;
2. 3. /** 4. * Created by YANGTAO on 2019/11/3 0003. 5. */ 6. public class DeleteBST { 7. 8. 9. public Node delete(Node node, int delVal) { 10. // 为空时，代表叶子结点 11. if (node == null){ 12. return node; 13. } 14. 15. int nodeVal = node.getValue(); 16. Node leftNode = node.getLeftChildren(); 17. Node rightNode = node.getRightChildren(); 18. 19. // 删除的结点，与遍历到的当前结点做比较，小于，大于或等于 20. if (delVal < nodeVal){ 21. Node tempLeftNode = delete(leftNode, delVal); 22. node.setLeftChildren(tempLeftNode); 23. } else if(delVal > nodeVal){ 24. Node tempRightNode = delete(rightNode, delVal); 25. node.setRightChildren(tempRightNode); 26. } else { 27. // 删除的结点与当前遍历到的结点相等时 28. // 并且左结点为空时，返回右结点去补上删除的位置，反则返回左结点补上 29. // 说明删除结点为单子结点的情况 30. if (leftNode == null){ 31. return rightNode; 32. } else if (rightNode == null){ 33. return leftNode; 34. } 35. 36. // 通过查询最小右结点，获取后继结点 37. Node minNode = minNode(rightNode); 38. int minNodeValue = minNode.getValue(); 39. node.setValue(minNodeValue); 40. // 删除后继结点 41. Node tempRightNode = delete(rightNode, minNodeValue); 42. node.setRightChildren(tempRightNode); 43. } 44. return node; 45. } 46. 47. private Node minNode(Node node) { 48. // 一直寻找最小值，知道左子节点为空为止 49. Node leftNode = node.getLeftChildren(); 50. if (leftNode != null) 51. return minNode(leftNode); 52. return node; 53. } 54. 55. }
[/code]
至此上面三中情况都予满足。
总结
上面对二叉查找树的操作都已介绍，但是正真使用中，是要结合实际业务进行相关调整来满足自己的需求，不然，一切的优化手段都是假把式。二叉查找树虽然好用，但是它也是有一定要求，在数据量不大的情况下，使用遍历的方式，更加符合我们的要求，所以它使用场景一般是在海量数据的查询，用来提查询效率。
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：juu3644。
