数据结构与算法-BST二叉搜索树(二叉排序树)【十九】

╰半夏微凉° 2022-12-06 12:53 208阅读 0赞

线性表在添加和删除的效率较低，所以我们考虑特殊的树,考虑这种存储结构，提高查找效率，以及动态添加和删除的效率。

这时会引入 【二叉搜索树】

> #### 二叉搜索树的定义 ####

定义【仍然是递归定义】：

1.  左子树为空，那么左子树上的所有值一定是小于根节点的值。
2.  右子树不为空，那么右子树上的所有值一定是大于等于根节点的值。
3.  左右子树也是一颗二叉搜索树。

二叉搜索树 也称为二叉排序树

例子：

5         第一层                                       
         /   \                                                
        0      9     第二层                                  
       / \    / \                                           
      -1  3  7   12  第三层

> #### 二叉树节点定义 ####

// Definition for a binary tree node.
      function TreeNode(val) { 
          this.val = val;
          this.left = this.right = null;
      }

> ##### 二叉搜索树的查找 #####

leetcode -700

var searchBST = function(root, val) { 
        if (!root || root.val === val) {  return root }
        if (val < root.val) { 
            return searchBST(root.left, val)
        }
        if (val >= root.val) { 
            return searchBST(root.right, val)
        }
    }

> #### 二叉搜索树的插入 ####

tips: 二叉搜索树插入的节点一定在叶子节点上。【不是父亲节点一定是叶子节点，而是插入的节点本身一定是叶子节点。】

leetcode-701

var insertIntoBST = function(root, val) { 
        if (!root) return new TreeNode(val);
        if (val < root.val) { 
            if (root.left) { 
                insertIntoBST(root.left, val)
            }else if (!root.left) { 
                root.left = new TreeNode(val)        
            }
        }
        if (val >= root.val) { 
            if (root.right) { 
                insertIntoBST(root.right, val)
            } else if (!root.right) {         
                root.right = new TreeNode(val)
            }
        }
        return root
        
    }

> #### 二叉搜索树的平均查找长度 ####

咱们以上面的有限序列`[-1, 0, 3, 5, 7, 9, 12]` 为例。

`最好`的情况下就是这个有序序列的判定树：

查找成功的情况下，查找次数为所在的层数; 这时候的平均查找长度为 `log2 (n + 1) - 1`

`最坏`的情况下就是层数达到最大：

-1                                             
             \                                                
               0                                     
                \                                           
    	  		  3 
    			    \
    			      5
    				    \ 
    				      7
    				       \ 
    				        9
    				          \ 
    				           12

查找成功的情况下，查找次数也为所在的层数，此时平均查找长度为`(n + 1) / 2`

--------------------

在最差的情况下，和线性表的查找是相同效率的。所以我们需要尽量将二叉搜索树“平衡”一下，至少层数不要那么极端的深。

这就引出了 [平衡二叉树][Link 1]

to be continued

[Link 1]: https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E6%A0%91