做网站广告哪家好/外贸推广平台有哪几个

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

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

二叉搜索树的定义

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

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] 为例。

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

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

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

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

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

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

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

这就引出了 平衡二叉树

to be continued