数据结构笔记：二叉搜索树

概述

二叉搜索树
AVL

小试牛刀

存在由（）个节点的AVL，所有内部节点平衡因子都不为零

A. 32
B. 33
C. 34
D. 35

答案：B

{0，1，2，3，4，5，6，7，8}九个关键码构成的真二叉搜索树的种类有（）种

A. 14
B. 16
C. 512
D. 4862


答案：14

一棵二叉搜索树有8个叶节点，且内部节点平衡因子都是+1，则共有（）个节点

答案：

有序性

单调性

BST模板类 && 接口

What's the difference between a binary search tree and a regular binary tree?二叉搜索树之区别于普通的二叉树在于：A

A. Each node is less than or equal to the nodes in its right sub-tree, while being greater than or equal to the nodes in its left sub-tree. 任意节点均不大于其右子树中的节点，不小于其左子树中的节点
B. Each node is less than or equal to its right child, while being greater than or equal to its left child 任意节点均不大于其右孩子，不小于其左孩子
C. Each node (except the root) is less than or equal to its parent 除了根节点外所有节点均不大于其父亲
D. The keys are comparable 关键码可以比较

BST查找

BST插入

实现

Consider inserting a target element e into a BST. when it fails to be found during the search, which node does _hot correspond to?
对BST进行插入操作，对待插入的目标元素e进行查找后，若查找失败，_hot指向的节点为：B

A. The node to be inserted 待插入的节点
B. The parent of e after the insertion e被插入后的父亲
C. The left-child of e after the insertion e被插入后的左孩子
D. The root 根节点

BST删除

单分支

待删除节点至多有一个孩子

实现

双分支

实现

复杂度

当欲删除的节点v在BST中的度为2时，实际被删除的节点为：C

A. v's direct predecessor in the in-order sequence v在中序遍历下的直接前驱
B. v's direct successor in the pre-order sequence v在先序遍历下的直接后继
C. the last node in the left branch of v's right sub-tree v的右子树中左侧分支的最后一个节点
D. v's parent v的父亲