当前位置：首页 > news >正文

二叉搜索树与B树引入

news 2026/3/26 18:19:07

二叉树的引入：

在一个链表之中，我们已知它的时间复杂度是O(N),。对于一个数组，我们可以通过二分搜索，来将寻找一个元素的时间复杂度降低为O(logN), 那么树的建立实际上就是对于链表进行的一个二分搜索。

我们要做的就是引入中间节点，以O(1)的复杂度到达链表中间；再翻转节点的指针，是能够遍历到左右两部分。

若将这个结构垂直拉伸，那么你就会发现你得到了一个树。

故有结论：带有递归中间指针的链表就是二叉树。

BST Definitions：

我们对于二叉树引入新的property约束：

对于二叉搜索树中的每一个节点Node X，

·左侧子树中的每一个值都小于X的值；

·右侧子树中的每一个值都大于X的值；

代码表现：

private class BST<Key> {private key;private BST left;private BST right;public BST(Key key, BST left, BST right){this.key = key;this.left = left;this.right = right;}public BST(key){this.key = key;}
}

BST Operation:

Search

递归写法：

假设我们正在寻找的元素是X，从根节点开始，若X大于root，则寻找root的右子树；若X小于root，则寻找root的左子树。递归地重复这一操作，直到找到该元素，或是到达一个叶节点；

static BST find(BST T, Key sk){if(T == null){return null;}if (sk == T){return T}else if (sk < T.key){return find(T.left, sk);}else return find(T.right, sk);}

如果搜索的是一个bushy tree，则时间复杂度为O(logN), 即为树的最大height。

Insert：

由搜索的性质可知，

我们在树中搜索该节点，若已经找到该节点，则什么都不做；若未找到，则我们此时已经来到了恰当的叶节点处，将新元素添加到叶子的左侧或右侧即可。

static BST find(BST T, Key sk){if(T == null){return new BST(sk);}if(sk < T.key){T.left = insert(T, sk);}else{T.right = insert(T, sk);}return T;}

Delete：

删除操作需要分为四种情况讨论：

· 该节点无child，为叶节点：

仅删除它的父指针，再释放它即可。

· 被删节点右子树为空，左子树非空：

用这个节点的左子女节点代替它的位置，即可。

· 被删节点左子树为空，右子树非空：

用右子女节点代替它的位置即可。

· 被删节点左右子树都不为空：

在右子树中寻找中序下的第一个节点，来取代他的位置——

满足是右子树中最小的，且大于左子树所有点。

代码实现：

bool remove(int target, Node ptr){if(ptr != null){if(target < ptr->data){remove(target, ptr->left);}else if(target > ptr->data){remove(target, ptr->right);}else if(ptr->left != null && ptr->right != null){Node tmp = ptr;while(tmp->left) tmp = tmp->left;ptr->data = tmp->data;remove(ptr->data, ptr->right);}else{  //只有一个非空或为叶节点tmp = ptr;if(ptr->left == null){ptr = ptr->right;}else if(ptr->right == null){ptr = ptr->left;}delete tmp;   //释放老节点空间return true;}return false;}
}

AVL树：

定义：

左右子树均为AVL树。
左右子树高度差不超过1，高度之差称为该节点的平衡因子，即平衡因子只能取-1， 0， 1。

平衡化旋转：

主要包括两类——单旋转，双旋转。
执行时机：每插入一个新节点时，均需从当前位置向root回溯，检查路径上的平衡因子。

二叉查找树的扩展：

类比于线索二叉树——将每个节点扩展为：左子结点，键值，右子节点，左子结点标签，右子节点标签五个属性。

左子结点标签：若左子结点确实存在，标签为1；若左子结点为空，则指针指向比当前节点小一个的节点。

右子节点标签：若右子结点确实存在，标签为1；若右子结点为空，则指针指向比当前节点大一个的节点。

形如：

基于上述结构，对BST的搜索方法进行改造：

两个基本函数next和previous：

Node next(Node now){Node tmp;if(now->rightid = 0) return now->right;else{tmp = now->right;while(tmp->left) tmp = tmp->left;return tmp;}
}

Node previous(Node now){Node tmp;if(now->leftid == 0) return now->left;else{tmp = now-> left;while(tmp-right) tmp = tmp->right;return tmp;}
}

//基于next实现遍历由小到大
void search(Node root){Node tmp = root;while(tmp->leftid != 0) tmp = tmp->left;cout<<tmp>data;while(tmp){tmp = next(tmp);if(tmp) cout<<tmp>data;}
}