首页 > 编程学习 > 【数据结构】查找— —树表的查找(二叉排序树、平衡二叉树)

查找之二:树表

    • 1 二叉排序树(Binary Sort Tree,BST)
      • 1.1 BST的定义
      • 1.2 BST的查找
      • 1.3 BST的插入
      • 1.4 BST的构造
      • 1.5 BST的删除
      • 1.6 BST的查找效率
    • 2 平衡二叉树(AVL)
      • 2.1 AVL的定义
      • 2.2 AVL的插入

1 二叉排序树(Binary Sort Tree,BST)

1.1 BST的定义

也叫二叉查找树,可以为空。中序遍历可以得到一个递增的有序序列。
具有以下特性:

  • 若左子树非空,左子树所有结点均小于根结点;
  • 若右子树非空,右子树所有结点均大于根结点;
  • 左、右子树仍为一棵二叉排序树。
    二叉排序树

1.2 BST的查找

从根结点开始,沿某个分支逐层向下比较的过程。若相等,则查找成功;若不相等,如果小于根结点的关键字,则在根结点的左子树上查找,否则,在根结点的右子树上查找。(递归)

1.3 BST的插入

新插入的结点一定是叶子结点,且是查找失败时查找路径上访问的最后一个结点的左孩子或者右孩子。

  • 若二叉排序树为空,直接插入节点;
  • 若关键字 key 小于根结点,则插入到左子树;
  • 若关键字 key 大于根结点,则插入到右子树中;
int BST_Insert(BiTree &T,KeyType k){
	if(T == NULL)
	{
		T = (BiTree)malloc(sizeof(BSTNode));
		T->data = k;
		T->lchild = T->rchild = NULL;
		return 1;
	}
	else if(K == T->data)
		return 0;
	else if(K < T->data)
		return BST_Insert(T->lchild,k);
	else 
		return BST_Insert(T->rchid,k);
}

1.4 BST的构造

不同序列可能得到同款二叉排序树,也可能得不到。
相同关键字可能得到不同的二叉排序树。

1.5 BST的删除

  • 如果是叶子结点,直接删
  • 若结点 z 只有一颗子树,忽略 z ,让其子树代替 z 。
  • 若结点 z 有左右两颗子树,
    令 z 的直接前驱代替 z
    令 z 的直接后继代替 z ,这里有一个巧方法,可以在 z 结点附近进行中序遍历,z 结点后的元素代替 z 即可。

1.6 BST的查找效率

取决于树高
二叉排序树只需要满足中序遍历有序即可,树可以是平衡二叉树,平均执行时间:O(log n)「此时树宽宽的,胖胖的」;也可以是只有左(右)孩子的单支树,平均执行时间:O(n)「此时树像一条线,又细又长」。

2 平衡二叉树(AVL)

2.1 AVL的定义

  • 平衡二叉树可以为空。
  • 在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,这样的二叉树被称为平衡二叉树。
  • 平衡因子:左子树与右子树的高度差。平衡二叉树的平衡因子只能为-1、0、1
  • 查找时间复杂、最大深度:O(log n)

2.2 AVL的插入

1)当平衡二叉树为空,插入新元素作为根结点,且树的深度加1;
2)当插入的新元素 = 根结点的关键字,不进行插入;
3)当插入的新元素 < 根结点的关键字,且左子树中不存在相同的关键字,则插在左子树上,且深度加1,分情况调整二叉树使之保持平衡;
4)当插入的新元素 > 根结点的关键字,且右子树中不存在相同的关键字,则插在右子树上,且深度加1,分情况调整二叉树使之保持平衡。

调整的规律可归纳为下列四种情况:

  • LL型(右单旋):因在结点A的左子树结点的左孩子插入结点,引起的不平衡,需要进行一次右旋操作。
    LL
  • RR型(左单旋):因在结点A的右子树结点的左孩子插入结点,引起的不平衡,需要进行一次左旋操作。
    RR
  • LR型(先左后右双旋转):LR
  • RL型(先右后左双旋转):RL
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式