二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质:

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

查找的时候总是从根节点进行比较然后逐级往下进行。

由于它是一种树形结构,所以相对于顺序存储结构来说,进行插入或者删除操作的时候效率较高,但是其查找性能是是不确定的(依赖于书的形状),例如如果每个节点都只有左孩子而没有右,则查找相当于从头找到尾,而如果每个节点的左右孩子深度差不多相等,则相当于二分查找。

鉴于上述原因,则需要在构造树的形状时尽量左右平衡,以提高查找效率,所以就出现了平衡二叉树(AVL树)

平衡二叉树或为空树,或为如下性质的二叉排序树:

(1)左右子树深度之差的绝对值不超过1;

(2)左右子树仍然为平衡二叉树.

平衡因子BF=左子树深度-右子树深度.

平衡二叉树每个结点的平衡因子只能是1,0,-1。若其绝对值超过1,则该二叉排序树就是不平衡的。

最小不平衡子树:距离插入结点最近,且平衡因子的绝对值大于1的结点为根的子树。

平衡二叉树的构造思想:

构建的过程中,每插入一个结点,先检查是否因为插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树的前提下,调整最小不平衡子树中各个结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。

程序的具体实现方法可以参见《大话数据结构》一书

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

求二叉树的深度和宽度

题目: 输入一个二叉树的根节点,求该树的深度。从根节点到叶子节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度包含的节点数为为树的深度,即二...

1892
来自专栏小文博客

小文’s blog — 平衡二叉树构造方法

1043
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

4356
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。 分析:本题是一道典型的“分治法”。要...

3055
来自专栏菩提树下的杨过

数据结构C#版笔记--树与二叉树

                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以...

2598
来自专栏程序生活

二叉树的深度

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 代码实现 递归实现 # ...

2544
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

2358
来自专栏曾大稳的博客

树(Tree)以及二叉树的遍历

树(tree) 是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次...

1711
来自专栏有趣的Python

12-玩转数据结构-AVL

我们之前实现的那个二叉树在最差情况下会退化成链表,在现有二分搜索树基础上添加一定的机制,使得二分搜索树可以维持平衡二叉树性质。AVL树就是一种经典的平衡二叉树。

1582
来自专栏kevindroid

leetcode110 Balanced Binary Tree

1465

扫码关注云+社区