chapter_tree/avl_tree/ #85
Replies: 66 comments 87 replies
-
这部分确实是有点难度 |
Beta Was this translation helpful? Give feedback.
-
K神有时间可以更新一章红黑树的区别吗?想看看它们的区别和各自的应用场景,感谢! |
Beta Was this translation helpful? Give feedback.
-
您好,请问python的会更新吗 |
Beta Was this translation helpful? Give feedback.
-
K神会更新图数据结构嘛 ? |
Beta Was this translation helpful? Give feedback.
-
大佬,请问这一节中哪些函数归在private,哪些函数归在public中,这方面有什么考量吗?比如为什么要将 height 函数和 updateHeight 函数 分别放在 public 和 private 中呢? |
Beta Was this translation helpful? Give feedback.
-
有个疑问,我看右旋操作是处理失衡节点node、child、grandchild之间的关系,那node的父级和node原来的连接不需要维护吗?右旋操作后岂不是断掉了? |
Beta Was this translation helpful? Give feedback.
-
k神,这部分还会介绍红黑树吗? |
Beta Was this translation helpful? Give feedback.
-
大佬,想问一下,updateHeight()方法里为啥要 + 1 操作? |
Beta Was this translation helpful? Give feedback.
-
/* 右旋操作 */ |
Beta Was this translation helpful? Give feedback.
-
讲的不错,经过你的讲解感觉AVL树只有红黑树10%的难度 |
Beta Was this translation helpful? Give feedback.
-
复刻了一下 感觉可以的 |
Beta Was this translation helpful? Give feedback.
-
大佬,先左旋再右旋那张图,child.left=node, node.left=null也可以达到平衡吧,只是破坏了二叉搜索树的规则,这种做法属于左旋吗?左旋的时候child既可以取node左子节点也可以取右子节点吧,右旋同理 |
Beta Was this translation helpful? Give feedback.
-
if t.balanceFactor(node.Left) >= 0 { 为什么判断条件是 >= 0,是不是 > 0 也可以,因为左右高度差不可能为 0 |
Beta Was this translation helpful? Give feedback.
-
为什么不用 updateHeight(grandChild) 呀? |
Beta Was this translation helpful? Give feedback.
-
这里讲的真好,清楚易懂 |
Beta Was this translation helpful? Give feedback.
-
Btree Rtree 红黑树什么时候考虑加上呀 |
Beta Was this translation helpful? Give feedback.
-
在作者还没有开辟红黑树之前,这里先给出C++版本的红黑树哈 //红黑树不带删除
#include <iomanip>
#include <iostream>
using namespace std;
enum RBTColor { RED, BLACK };
template <class T>
class RBTNode {
public:
RBTColor color; // 颜色
T key; // 关键字(键值)
RBTNode* left; // 左孩子
RBTNode* right; // 右孩子
RBTNode* parent; // 父结点
RBTNode(T value, RBTColor c, RBTNode* p, RBTNode* l, RBTNode* r) :
key(value), color(c), parent(), left(l), right(r) {}
~RBTNode()
{
cout << "delete : " << key << endl;
}
};
template <class T>
class RBTree {
private:
RBTNode<T>* mRoot; // 根结点
public:
RBTree();
~RBTree();
// 前序遍历"红黑树"
void preOrder();
// 中序遍历"红黑树"
void inOrder();
// 后序遍历"红黑树"
void postOrder();
// (递归实现)查找"红黑树"中键值为key的节点
RBTNode<T>* search(T key);
// (非递归实现)查找"红黑树"中键值为key的节点
RBTNode<T>* iterativeSearch(T key);
// 查找最小结点:返回最小结点的键值。
T minimum();
// 查找最大结点:返回最大结点的键值。
T maximum();
// 找结点(x)的后继结点。即,查找"红黑树中数据值大于该结点"的"最小结点"。
RBTNode<T>* successor(RBTNode<T>* x);
// 找结点(x)的前驱结点。即,查找"红黑树中数据值小于该结点"的"最大结点"。
RBTNode<T>* predecessor(RBTNode<T>* x);
// 将结点(key为节点键值)插入到红黑树中
void insert(T key);
// 销毁红黑树
void destroy();
// 打印红黑树
void print();
private:
// 前序遍历"红黑树"
void preOrder(RBTNode<T>* tree) const;
// 中序遍历"红黑树"
void inOrder(RBTNode<T>* tree) const;
// 后序遍历"红黑树"
void postOrder(RBTNode<T>* tree) const;
// (递归实现)查找"红黑树x"中键值为key的节点
RBTNode<T>* search(RBTNode<T>* x, T key) const;
// (非递归实现)查找"红黑树x"中键值为key的节点
RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;
// 查找最小结点:返回tree为根结点的红黑树的最小结点。
RBTNode<T>* minimum(RBTNode<T>* tree);
// 查找最大结点:返回tree为根结点的红黑树的最大结点。
RBTNode<T>* maximum(RBTNode<T>* tree);
// 左旋
void leftRotate(RBTNode<T>*& root, RBTNode<T>* x);
// 右旋
void rightRotate(RBTNode<T>*& root, RBTNode<T>* y);
// 插入函数
void insert(RBTNode<T>*& root, RBTNode<T>* node);
//void insert(RBTNode<T>*& root, RBTNode<T>* node);
// 插入修正函数
void insertFixUp(RBTNode<T>*& root, RBTNode<T>* node);
// 销毁红黑树
void destroy(RBTNode<T>*& tree);
// 打印红黑树
void print(RBTNode<T>* tree, T key, int direction);
#define rb_parent(r) ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r) ((r)->color==RED)
#define rb_is_black(r) ((r)->color==BLACK)
#define rb_set_black(r) do { (r)->color = BLACK; } while (0)
#define rb_set_red(r) do { (r)->color = RED; } while (0)
#define rb_set_parent(r,p) do { (r)->parent = (p); } while (0)
#define rb_set_color(r,c) do { (r)->color = (c); } while (0)
};
/*
* 构造函数
*/
template <class T>
RBTree<T>::RBTree() :mRoot(NULL)
{
mRoot = NULL;
}
/*
* 析构函数
*/
template <class T>
RBTree<T>::~RBTree()
{
destroy();
}
/*
* 前序遍历"红黑树"
*/
template <class T>
void RBTree<T>::preOrder(RBTNode<T>* tree) const
{
if (tree != NULL)
{
cout << tree->key << " ";
preOrder(tree->left);
preOrder(tree->right);
}
}
template <class T>
void RBTree<T>::preOrder()
{
preOrder(mRoot);
}
/*
* 中序遍历"红黑树"
*/
template <class T>
void RBTree<T>::inOrder(RBTNode<T>* tree) const
{
if (tree != NULL)
{
inOrder(tree->left);
cout << tree->key << " ";
inOrder(tree->right);
}
}
template <class T>
void RBTree<T>::inOrder()
{
inOrder(mRoot);
}
/*
* 后序遍历"红黑树"
*/
template <class T>
void RBTree<T>::postOrder(RBTNode<T>* tree) const
{
if (tree != NULL)
{
postOrder(tree->left);
postOrder(tree->right);
cout << tree->key << " ";
}
}
template <class T>
void RBTree<T>::postOrder()
{
postOrder(mRoot);
}
/*
* (递归实现)查找"红黑树x"中键值为key的节点
*/
template <class T>
RBTNode<T>* RBTree<T>::search(RBTNode<T>* x, T key) const
{
if (x == NULL || x->key == key)
return x;
if (key < x->key)
return search(x->left, key);
else
return search(x->right, key);
}
template <class T>
RBTNode<T>* RBTree<T>::search(T key)
{
search(mRoot, key);
}
/*
* (非递归实现)查找"红黑树x"中键值为key的节点
*/
template <class T>
RBTNode<T>* RBTree<T>::iterativeSearch(RBTNode<T>* x, T key) const
{
while ((x != NULL) && (x->key != key))
{
if (key < x->key)
x = x->left;
else
x = x->right;
}
return x;
}
template <class T>
RBTNode<T>* RBTree<T>::iterativeSearch(T key)
{
iterativeSearch(mRoot, key);
}
/*
* 查找最小结点:返回tree为根结点的红黑树的最小结点。
*/
template <class T>
RBTNode<T>* RBTree<T>::minimum(RBTNode<T>* tree)
{
if (tree == NULL)
return NULL;
while (tree->left != NULL)
tree = tree->left;
return tree;
}
template <class T>
T RBTree<T>::minimum()
{
RBTNode<T>* p = minimum(mRoot);
if (p != NULL)
return p->key;
return (T)NULL;
}
/*
* 查找最大结点:返回tree为根结点的红黑树的最大结点。
*/
template <class T>
RBTNode<T>* RBTree<T>::maximum(RBTNode<T>* tree)
{
if (tree == NULL)
return NULL;
while (tree->right != NULL)
tree = tree->right;
return tree;
}
template <class T>
T RBTree<T>::maximum()
{
RBTNode<T>* p = maximum(mRoot);
if (p != NULL)
return p->key;
return (T)NULL;
}
/*
* 找结点(x)的后继结点。即,查找"红黑树中数据值大于该结点"的"最小结点"。
*/
template <class T>
RBTNode<T>* RBTree<T>::successor(RBTNode<T>* x)
{
// 如果x存在右孩子,则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
if (x->right != NULL)
return minimum(x->right);
// 如果x没有右孩子。则x有以下两种可能:
// (01) x是"一个左孩子",则"x的后继结点"为 "它的父结点"。
// (02) x是"一个右孩子",则查找"x的最低的父结点,并且该父结点要具有左孩子",找到的这个"最低的父结点"就是"x的后继结点"。
RBTNode<T>* y = x->parent;
while ((y != NULL) && (x == y->right))
{
x = y;
y = y->parent;
}
return y;
}
/*
* 找结点(x)的前驱结点。即,查找"红黑树中数据值小于该结点"的"最大结点"。
*/
template <class T>
RBTNode<T>* RBTree<T>::predecessor(RBTNode<T>* x)
{
// 如果x存在左孩子,则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
if (x->left != NULL)
return maximum(x->left);
// 如果x没有左孩子。则x有以下两种可能:
// (01) x是"一个右孩子",则"x的前驱结点"为 "它的父结点"。
// (01) x是"一个左孩子",则查找"x的最低的父结点,并且该父结点要具有右孩子",找到的这个"最低的父结点"就是"x的前驱结点"。
RBTNode<T>* y = x->parent;
while ((y != NULL) && (x == y->left))
{
x = y;
y = y->parent;
}
return y;
}
/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋):
* px px
* / /
* x y
* / \ --(左旋)--> / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
template <class T>
void RBTree<T>::leftRotate(RBTNode<T>*& root, RBTNode<T>* x)
{
// 设置x的右孩子为y
RBTNode<T>* y = x->right;
// 将 “y的左孩子” 设为 “x的右孩子”;
// 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲”
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y->parent = x->parent;
if (x->parent == NULL)
{
root = y; // 如果 “x的父亲” 是空节点,则将y设为根节点
}
else
{
if (x->parent->left == x)
x->parent->left = y; // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
else
x->parent->right = y; // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y->left = x;
// 将 “x的父节点” 设为 “y”
x->parent = y;
}
/*
* 对红黑树的节点(y)进行右旋转
*
* 右旋示意图(对节点y进行左旋):
* py py
* / /
* y x
* / \ --(右旋)--> / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
template <class T>
void RBTree<T>::rightRotate(RBTNode<T>*& root, RBTNode<T>* y)
{
// 设置x是当前节点的左孩子。
RBTNode<T>* x = y->left;
// 将 “x的右孩子” 设为 “y的左孩子”;
// 如果"x的右孩子"不为空的话,将 “y” 设为 “x的右孩子的父亲”
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x->parent = y->parent;
if (y->parent == NULL)
{
root = x; // 如果 “y的父亲” 是空节点,则将x设为根节点
}
else
{
if (y == y->parent->right)
y->parent->right = x; // 如果 y是它父节点的右孩子,则将x设为“y的父节点的右孩子”
else
y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x->right = y;
// 将 “y的父节点” 设为 “x”
y->parent = x;
}
/*
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡),再调用该函数;
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明:
* root 红黑树的根
* node 插入的结点 // 对应《算法导论》中的z
*/
template <class T>
void RBTree<T>::insertFixUp(RBTNode<T>*& root, RBTNode<T>* node)
{
RBTNode<T>* parent, * gparent;
// 若“父节点存在,并且父节点的颜色是红色”
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
gparent = rb_parent(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent->left)
{
// Case 1条件:叔叔节点是红色
{
RBTNode<T>* uncle = gparent->right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2条件:叔叔是黑色,且当前节点是右孩子
if (parent->right == node)
{
RBTNode<T>* tmp;
leftRotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件:叔叔是黑色,且当前节点是左孩子。
rb_set_black(parent);
rb_set_red(gparent);
rightRotate(root, gparent);
}
else//若“z的父节点”是“z的祖父节点的右孩子”
{
// Case 1条件:叔叔节点是红色
{
RBTNode<T>* uncle = gparent->left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2条件:叔叔是黑色,且当前节点是左孩子
if (parent->left == node)
{
RBTNode<T>* tmp;
rightRotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件:叔叔是黑色,且当前节点是右孩子。
rb_set_black(parent);
rb_set_red(gparent);
leftRotate(root, gparent);
}
}
// 将根节点设为黑色
rb_set_black(root);
}
/*
* 将结点插入到红黑树中
*
* 参数说明:
* root 红黑树的根结点
* node 插入的结点 // 对应《算法导论》中的node
*/
template <class T>
void RBTree<T>::insert(RBTNode<T>*& root, RBTNode<T>* node)
{
RBTNode<T>* y = NULL;
RBTNode<T>* x = root;
// 1. 将红黑树当作一颗二叉查找树,将节点添加到二叉查找树中。
while (x != NULL)
{
y = x;
if (node->key < x->key)
x = x->left;
else
x = x->right;
}
node->parent = y;
if (y != NULL)
{
if (node->key < y->key)
y->left = node;
else
y->right = node;
}
else
root = node;
// 2. 设置节点的颜色为红色
node->color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(root, node);
}
/*
* 将结点(key为节点键值)插入到红黑树中
*
* 参数说明:
* tree 红黑树的根结点
* key 插入结点的键值
*/
template <class T>
void RBTree<T>::insert(T key)
{
RBTNode<T>* z = NULL;
// 如果新建结点失败,则返回。
if ((z = new RBTNode<T>(key, BLACK, NULL, NULL, NULL)) == NULL)
return;
insert(mRoot, z);
}
/*
* 销毁红黑树
*/
template <class T>
void RBTree<T>::destroy(RBTNode<T>*& tree)
{
if (tree == NULL)
return;
if (tree->left != NULL)
destroy(tree->left);
if (tree->right != NULL)
destroy(tree->right);
delete tree;
tree = NULL;
}
template <class T>
void RBTree<T>::destroy()
{
destroy(mRoot);
}
/*
* 打印"二叉查找树"
*
* key -- 节点的键值
* direction -- 0,表示该节点是根节点;
* -1,表示该节点是它的父结点的左孩子;
* 1,表示该节点是它的父结点的右孩子。
*/
template <class T>
void RBTree<T>::print(RBTNode<T>* tree, T key, int direction)
{
if (tree != NULL)
{
if (direction == 0) // tree是根节点
cout << setw(2) << tree->key << "(B) is root" << endl;
else // tree是分支节点
cout << setw(2) << tree->key << (rb_is_red(tree) ? "(R)" : "(B)") << " is " << setw(2) << key << "'s " << setw(12) << (direction == 1 ? "right child" : "left child") << endl;
print(tree->left, tree->key, -1);
print(tree->right, tree->key, 1);
}
}
template <class T>
void RBTree<T>::print()
{
if (mRoot != NULL)
print(mRoot, mRoot->key, 0);
}
int main()
{
system("chcp 65001");
int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };
int check_insert = 1; // "插入"动作的检测开关(0,关闭;1,打开)
int check_remove = 0; // "删除"动作的检测开关(0,关闭;1,打开)
int i;
int ilen = (sizeof(a)) / (sizeof(a[0]));
RBTree<int>* tree = new RBTree<int>();
cout << "== 原始数据: ";
for (i = 0; i < ilen; i++)
cout << a[i] << " ";
cout << endl;
for (i = 0; i < ilen; i++)
{
tree->insert(a[i]);
// 设置check_insert=1,测试"添加函数"
if (check_insert)
{
cout << "== 添加节点: " << a[i] << endl;
cout << "== 树的详细信息: " << endl;
tree->print();
cout << endl;
}
}
cout << "== 前序遍历: ";
tree->preOrder();
cout << "\n== 中序遍历: ";
tree->inOrder();
cout << "\n== 后序遍历: ";
tree->postOrder();
cout << endl;
cout << "== 最小值: " << tree->minimum() << endl;
cout << "== 最大值: " << tree->maximum() << endl;
cout << "== 树的详细信息: " << endl;
tree->print();
// 销毁红黑树
tree->destroy();
delete tree;
}
/*
*/ |
Beta Was this translation helpful? Give feedback.
-
有关红黑树和一些算法导论中的数据结构的内容可以查看我的项目 https://github.com/whoamiR/the-Algorithms-on-Introduction-to-Algorithms/tree/main/Advanced_Data_Structure |
Beta Was this translation helpful? Give feedback.
-
感觉挺清楚的,期待加入红黑树 |
Beta Was this translation helpful? Give feedback.
-
我个人对平衡二叉树旋转的理解: |
Beta Was this translation helpful? Give feedback.
-
使失衡节点重新恢复平衡, 应该是使得 不平衡节点 恢复平衡? |
Beta Was this translation helpful? Give feedback.
-
有个问题,自己运行的时候。。会报错,然后删了如TreeNode | None 这些注释,就可以了 |
Beta Was this translation helpful? Give feedback.
-
在“图 7-27 有 grand_child 的右旋操作”示意图中,节点5应该不是不平衡节点吧,它的平衡因子应该是1吧 |
Beta Was this translation helpful? Give feedback.
-
def update_height(self, node: TreeNode | None): |
Beta Was this translation helpful? Give feedback.
-
"我们需要从这个节点开始,自底向上执行旋转操作,使所有失衡节点恢复平衡",在插入和删除的时候,这句话没有看懂,rotate(TreeNode node) 里面是往下去检查子节点的平衡因子? |
Beta Was this translation helpful? Give feedback.
-
这段可以修改为return child吗,因为我觉得只有一个子节点时不需要再更新子节点的高度和平衡了 |
Beta Was this translation helpful? Give feedback.
-
求教各位,图 7-26 中节点“4” 和节点“3”都是失衡节点都是2,都是为什么执行节点“3”的右旋而不是节点“4”的右旋呢? |
Beta Was this translation helpful? Give feedback.
-
删除节点的代码: /* 递归删除节点(辅助方法) */
TreeNode removeHelper(TreeNode node, int val) {
if (node == null)
return null;
/* 1. 查找节点并删除 */
if (val < node.val)
node.left = removeHelper(node.left, val);
else if (val > node.val)
node.right = removeHelper(node.right, val);
else {
if (node.left == null || node.right == null) {
TreeNode child = node.left != null ? node.left : node.right;
// 子节点数量 = 0 ,直接删除 node 并返回
if (child == null)
return null;
// 子节点数量 = 1 ,直接删除 node
else
node = child;
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
TreeNode temp = node.right;
while (temp.left != null) {
temp = temp.left;
}
node.right = removeHelper(node.right, temp.val);
node.val = temp.val;
}
}
updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
} 子节点数为0或1的时候,应该都可以直接返回吧,不需要执行后序的旋转操作。 if(node.left == null) {
return node.right;
}
if(node.right == null) {
return node.left;
} |
Beta Was this translation helpful? Give feedback.
-
大家好,我是之前提问过有关二叉树概念的盲人。 稍微叠个甲,当然如果有其他盲人小伙伴看到,不要介意我总是提起这点,实在是因为如果不说,其他小伙伴就不太好针对我的提问进行有效的回答。 之前学习数据结构,到树开始,就有点一知半解了,我其实很不喜欢这种感觉。我很希望能搞懂它。 不得不说,很多时候,图解真的可以让我们少走许多弯路。例如我之前理解树的前序遍历、中序遍历、后序遍历,我读到类似“先便利左子树,然后便利根节点,最后便利右子树”,或者“先便利根节点,然后便利左子树,然后是右子树”时,脑子里总是很混乱。 昨天突然在看使用递归方式进行前中后序遍历的代码时发现,使用递归和自相似性的思想理解二叉树便利会更好。 好了,废话完毕,今天的问题是有关如何理解树的旋转的。主要是想让大家看看我的理解是否正确。 我根据表 7-3 脑补了如下失衡二叉树,由于我不太好用纯文本画二叉树,用语言描述可能啰嗦,我就写成数组形式:
其实,这就是一个退化的链表。此时,根节点的平衡因子是 根据代码,有: /* 左旋操作 */
TreeNode *leftRotate(TreeNode *node) { // 本例中为根节点 1
TreeNode *child = node->right; // 本例中为节点 2
TreeNode *grandChild = child->left; // nullptr
// 以 child 为原点,将 node 向左旋转
child->left = node; // 1
// 此时,child 已经成为一个结构为 [2,1,3] 的二叉树
// 且此时 node->right->left <=> child->left <=> node
node->right = grandChild; // nullptr
// 更新节点高度
updateHeight(node); // 2 -> 0
updateHeight(child); // 1 -> 1
// 返回旋转后子树的根节点
return child;
} 不知道理解有没有问题,但还是感觉有点没明白。 |
Beta Was this translation helpful? Give feedback.
-
chapter_tree/avl_tree/
Your first book to learn Data Structure And Algorithm.
https://www.hello-algo.com/chapter_tree/avl_tree/
Beta Was this translation helpful? Give feedback.
All reactions