前端进阶算法11：二叉查找树（BST树）

[sisterAn]

一、二叉查找树（BST树）

有的笔者也称它为二叉搜索树，都是一个意思。

二叉树本身没有多大的意义，直到有位大佬提出一个 trick。

如果我们规定一颗二叉树上的元素拥有顺序，所有比它小的元素在它的左子树，比它大的元素在它的右子树，那么我们不就可以很快地查找某个元素了吗？

不得不说这是一个非常天才的想法，于是，二叉查找树诞生了。

所以，二叉查找树与二叉树不同的是，它在二叉树的基础上，增加了对二叉树上节点存储位置的限制：二叉搜索树上的每个节点都需要满足：

• 左子节点值小于该节点值
• 右子节点值大于等于该节点值

在二叉树中，所有子节点值都是没有固定规律的，所以使用二叉树存储结构存储数据时，查找数据的时间复杂度为 O(n)，因为它要查找每一个节点。

而使用二叉查找树就不同了，例如上图，我们如果要查找 6 ，先从根节点 10 比较，6 比 10 小，则查找左子树，再与 8 比较，6 比 8 小，继续查找 8 的左子树，也就是 6，我们找到了元素，结束。

二、代码实现

function BinarySearchTree() {
 let Node = function (key) {
 this.key = key
 this.left = null
 this.right = null
 }
 let root = null
 
 // 插入
 this.insert = function(key){}
 
 // 查找
 this.search = function(key){}
 
 // 删除
 this.remove = function(key){}
 
 // 最大值
 this.max = function(){}
 
 // 最小值
 this.min = function(){}
 
 // 中序遍历
 this.inOrderTraverse = function(){}
 
 // 先序遍历
 this.preOrderTraverse = function(){}
 
 // 后序遍历
 this.postOrderTraverse = function(){}
}

插入：

• 首先创建一个新节点
• 判断树是否为空，为空则设置插入的节点为根节点，插入成功，返回
• 如果不为空，则比较该节点与根结点，比根小，插入左子树，否则插入右子树

function insert(key) {
 // 创建新节点
 let newNode = new Node(key)
 // 判断是否为空树
 if(root === null) {
 root = newNode
 } else {
 insertNode(root, newNode)
 }
}

// 将 insertNode 插入到 node 子树上
function insertNode(node, newNode) {
 if(newNode.key < node.key) {
 // 插入 node 左子树
 if(node.left === null) {
 node.left = newNode
 } else {
 insertNode(node.left, newNode)
 }
 } else {
 // 插入 node 右子树
 if(node.right === null) {
 node.right = newNode
 } else {
 insertNode(node.right, newNode)
 }
 }
}

最值：

最小值：树最左端的节点

最大值：树最右端的节点

// 最小值
function min() {
 let node = root
 if(node) {
 while(node && node.left !== null) {
 node = node.left
 }
 return node.key
 }
 return null
}

// 最大值
function max() {
 let node = root
 if(node) {
 while(node && node.right !== null) {
 node = node.right
 }
 return node.key
 }
 return null
}

查找：

function search(key) {
 return searchNode(root, key)
}

function searchNode(node, key) {
 if(node === null) 
 return false
 if(key < node.key) {
 return searchNode(node.left, key)
 } else if(key > node.key) {
 return searchNode(node.right, key)
 } else {
 return true
 }
}

删除：

function remove(key) {
 root = removeNode(root, key)
}

function removeNode(node, key) {
 if(node === null) 
 return null
 if(key < node.key) {
 return removeNode(node.left, key)
 } else if(key > node.key) {
 return removeNode(node.right, key)
 } else {
 // key = node.key 删除
 //叶子节点
 if(node.left === null && node.right === null) {
 node = null
 return node
 }
 // 只有一个子节点
 if(node.left === null) {
 node = node.right
 return node
 }
 if(node.right === null) {
 node = node.left
 return node
 }
 // 有两个子节点
 // 获取右子树的最小值替换当前节点
 let minRight = findMinNode(node.right)
 node.key = minRight.key
 node.right = removeNode(node.right, minRight.key)
 return node
 }
}

// 获取 node 树最小节点
function findMinNode(node) {
 if(node) {
 while(node && node.right !== null) {
 node = node.right
 }
 return node
 }
 return null
}

中序遍历：

顾名思义，中序遍历就是把根放在中间的遍历，即按先左节点、然后根节点、最后右节点（左根右）的遍历方式。

由于BST树任意节点都大于左子节点值小于等于右子节点值的特性，所以 中序遍历其实是对🌲进行排序操作 ，并且是按从小到大的顺序排序。

function inOrderTraverse(callback) {
 inOrderTraverseNode(root, callback)
}

function inOrderTraverseNode(node, callback) {
 if(node !== null) {
 // 先遍历左子树
 inOrderTraverseNode(node.left, callback)
 // 然后根节点
 callback(node.key)
 // 再遍历右子树
 inOrderTraverseNode(node.right, callback)
 }
}

// callback 每次将遍历到的结果打印到控制台
function callback(key) {
 console.log(key)
}

先序遍历：

已经实现的中序遍历，先序遍历就很简单了，它是按根左右的顺序遍历

function preOrderTraverse() {
 preOrderTraverseNode(root, callback)
}

function preOrderTraverseNode(node, callback) {
 if(node !== null) {
 // 先根节点
 callback(node.key)
 // 然后遍历左子树
 preOrderTraverseNode(node.left, callback)
 // 再遍历右子树
 preOrderTraverseNode(node.right, callback)
 }
}

// callback 每次将遍历到的结果打印到控制台
function callback(key) {
 console.log(key)
}

后序遍历：

后序遍历按照左右根的顺序遍历，实现也很简单。

function postOrderTraverse() {
 postOrderTraverseNode(root, callback)
}

function postOrderTraverseNode(node, callback) {
 if(node !== null) {
 // 先遍历左子树
 postOrderTraverseNode(node.left, callback)
 // 然后遍历右子树
 postOrderTraverseNode(node.right, callback)
 // 最后根节点
 callback(node.key)
 }
}

// callback 每次将遍历到的结果打印到控制台
function callback(key) {
 console.log(key)
}

三、BST树的局限

在理想情况下，二叉树每多一层，可以存储的元素都增加一倍。也就是说 n 个元素的二叉搜索树，对应的树高为 O(logn)。所以我们查找元素、插入元素的时间也为 O(logn)。

当然这是理想情况下，但在实际应用中，并不是那么理想，例如一直递增或递减的给一个二叉查找树插入数据，那么所有插入的元素就会一直出现在一个树的左节点上，数型结构就会退化为链表结构，时间复杂度就会趋于 O(n)，这是不好的。

而我们上面的平衡树就可以很好的解决这个问题，所以平衡二叉查找树（AVL树）由此诞生。

[zhongshankaka]

findMinNode写错了吧，应该要查左子节点

// 获取 node 树最小节点
function findMinNode(node) {
 if(node) {
 while(node && node.left !== null) {
 node = node.left
 }
 return node
 }
 return null
}

[L-T-G]

removeNode 写错了，没有更新父节点

function removeNode(node, key){
 if(node === null) 
 return null


 if(key < node.key){
 node.left=removeNode(node.left, key)
return node
 } else if(key > node.key){
 node.right=removeNode(node.right, key)
return node
 } else{
 // key = node.key 删除
 //叶子节点
 if(node.left === null && node.right === null){
 node = null
 return node
 }
 // 只有一个子节点
 if(node.left === null){
 node = node.right
 return node
 }
 if(node.right === null){
 node = node.left
 return node
 }
 // 有两个子节点
 // 获取右子树的最小值替换当前节点
 let minRight = findMinNode(node.right)
 node.key = minRight.key
 node.right = removeNode(node.right, minRight.key)
 return node
 }
}